{"id":"9899c5d4-17e7-455a-98d9-aead93320869","arxiv_id":"2411.12917","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For graphs on n vertices whose complement is bipartite with at most n-3 edges, two distinct eigenvalues are always achievable; at the n-2 edge threshold, the only q=3 case is a double-star plus an isolated vertex.","lead":"A graph's q-value is the fewest distinct eigenvalues a symmetric matrix with that graph's zero pattern can have. This paper proves graphs whose complement is sparse and bipartite always reach q-value 2, and identifies the single near-bound exception.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.7 depends entirely on the cited SSP realization of K_s □ K_2 (Theorem 20 of [10]); no internal proof or construction is given, so the bipartite-complement conjecture rests on that external result.","rationale":"The reader's weakest_assumption identifies precisely the reliance on Theorem 20 of [10] for the SSP realization of K_s □ K_2. This is indeed the single most load-bearing assumption in the paper: without it, Theorem 3.7 cannot conclude q(G) = 2 for the constructed supergraphs, and the bipartite-complement conjecture would remain unproved. The rest of the proof is structurally sound assuming this theorem holds: the even and odd cases correctly reduce to supergraphs of K_s □ K_2, and the SSP extension theorem then yields q = 2. The reader's verdict of CONDITIONAL is appropriate because this external dependency, while likely correct, is not demonstrated in the paper. I propose a concrete verification that would settle the concern: either checking the cited proof or constructing explicit SSP matrices for small s. No other part of the central argument appears to be at comparable risk; the minor issues noted by the reader (the k=2 verification and Theorem 5.1 notation) are local and do not affect Theorem 3.7. Therefore I do not change the verdict, but I underline the same load-bearing concern.","tokens_in":17150,"tokens_out":20820,"duration_ms":189861,"concrete_test":"Inspect the proof of Theorem 20 in Fallat and Mojallal (2023) and independently construct explicit symmetric matrices in S(K_3 □ K_2) and S(K_4 □ K_2) with exactly two distinct eigenvalues, then verify the SSP certificate condition: A∘X = 0, I∘X = 0, and AX = XA imply X = 0. If such matrices exist (or the cited proof checks out), the dependency is sound; if not, the argument for Theorem 3.7 loses its pivotal step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3.7 uses the external result that K_s □ K_2 has an SSP matrix realization with two distinct eigenvalues. This is applied in the even-n case with s = n/2, and in the odd-n reduction after removing an isolated vertex, with s = (n-1)/2 (and with s = 2 handled by [4]). The step 'Therefore, any supergraph of this graph will have q-value 2' requires both the two-eigenvalue realization and the Strong Spectral Property, because Theorem 10 of [7] extends the realization to supergraphs only for SSP matrices. If Theorem 20 of [10] were false or lacked the SSP, the proof would not establish q(G) = 2 for the supergraphs G or G' constructed in Section 3. The paper gives no proof, construction, or verification of this pivotal fact, and it is not derived internally; the authors only cite [10]. Thus the central claim for bipartite complements is contingent on an unverified external theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameter q(G), the minimum number of distinct eigenvalues over all real symmetric matrices whose off-diagonal zero pattern is described by the graph G. Its main results are: (1) Theorem 2.3, giving the general bound e(\\overline G) ≤ floor(n/2) − 1 ⇒ q(G) = 2; (2) Theorem 3.7, proving Conjecture 1.1 for all graphs whose complement is bipartite and has at most n − 3 edges; (3) Theorem 4.1, characterizing the bipartite-complement case with e(\\overline G) = n − 2, where q(G) = 3 exactly when the complement is S_{a,b} ∪ K_1; and (4) several supporting results and further evidence toward Conjecture 1.1. The proofs use a mix of combinatorial structure (Hall's theorem, induction on component sizes) and the Strong Spectral Property to extend two-eigenvalue realizations to supergraphs.","tokens_in":17375,"tokens_out":15315,"duration_ms":151498,"significance":"If the main results are correct, the paper makes substantial progress on a well-known open problem in the inverse eigenvalue problem for graphs: it confirms the q = 2 'requires' conjecture for the large natural class of bipartite complements and gives the first general edge bound of the form e(\\overline G) ≤ n/2 − 1 without extra hypotheses. The SSP machinery is used in a principled way, and the paper contains explicit matrix constructions (Corollary 4.5, Lemma 5.2) that are reproducible and do not fit constants or define quantities circularly. The combinatorial lemmas (Lemma 2.2 and the Hall argument in Lemma 3.5) are readable and appear sound. The main caveat is that the pivotal SSP realization of K_s □ K_2 is imported from an external reference without statement or proof, and one later theorem (Theorem 5.1) has a proof that is currently incorrect as written.","major_comments":[{"comment":"The proof of Theorem 3.7 rests entirely on the cited result ‘Theorem 20 of [10]’ (with the s = 2 case from [4]) that K_s □ K_2 has an SSP matrix realization with two distinct eigenvalues for every s ≥ 3. This fact is used in the even-n case with s = n/2 and in the odd-n reduction after removing an isolated vertex with s = (n−1)/2, and the SSP property is essential for the supergraph extension via Theorem 10 of [7]. The manuscript provides no statement, proof, or construction for this realization, so the central claim is contingent on an external theorem that the referee cannot verify from the manuscript. Please state the theorem exactly and either prove it or include an explicit matrix family with its two-eigenvalue and SSP verification (e.g., in an appendix).","section":"Section 3, proof of Theorem 3.7"},{"comment":"The proof of Theorem 5.1 contains a false inequality. For G′ = K_1 ∨ H on n−1 vertices, the number of edges in the complement is e(\\overline{G′}) = e(\\overline H) = binom(n−2,2) − e(H). With the stated hypothesis e(H) ≤ n−4, this quantity is generally much larger than n−4, so the induction hypothesis for graphs on at most n−1 vertices is not applicable. The displayed lower bound e(K_1 ∨ H) ≥ binom(n−1,2) − (n−4) does not follow; for example, with n = 6 and H two disjoint edges on four vertices, e(K_1 ∨ H) = 6 while the claimed bound is 8. The theorem may be salvageable with a different argument or a corrected hypothesis, but as written the proof does not establish the result.","section":"Section 5, Theorem 5.1"},{"comment":"Lemma 4.3 is the k = 2 case of the infinite family used in Theorem 4.1, and its proof relies on the sentence ‘It is easy to check that q(M_7) = 2 and that M_7 has the SSP.’ No computation is shown for either the spectrum or the SSP certificate. Since this verification is load-bearing for the characterization theorem and the 7 × 7 matrix is not part of the repeated family W_{2k+3}, please include the characteristic or minimal polynomial of M_7 and a brief argument that its only SSP certificate is the zero matrix, or provide a reproducible computation.","section":"Section 4, Lemma 4.3"}],"minor_comments":[{"comment":"The overline on \\overline G is frequently missing in the displayed text; for example, Theorem 2.3, Lemma 3.4, and Lemma 3.5 appear to state hypotheses about e(G) where the intended quantity is e(\\overline G). Please ensure that G and \\overline G are consistently distinguished, especially in Lemma 3.5 where both the dense graph and its sparse complement appear in the same proof.","section":"Throughout Sections 2–4"},{"comment":"The sentence ‘In the first four cases, G is not simplified while in the last two cases, G has no cycle’ refers to five listed configurations in Figure 2, so the counts do not match. This should be rephrased (for instance, ‘in the remaining cases’).","section":"Lemma 3.5, proof after Figure 2"},{"comment":"The assertion that if the 3 × 3 matrix C has zero, two, or three edges in its graph, then C has the SSP is stated without justification; only the one-edge case is shown. Please add a sentence explaining why the remaining three cases are immediate or provide a short verification.","section":"Theorem 5.3, proof"}],"recommendation":"major_revision","confidential_remarks":"The heavy reliance on Theorem 20 of [10] is a concern for the refereeing process: the result is imported from a paper co-authored by one of the present authors and is not stated or proved here. If the construction is correct, the main theorem is likely sound, but the manuscript should make the verification self-contained. The error in Theorem 5.1 suggests that the later sections need a careful re-reading before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does what it says: it proves Conjecture 1.1 for graphs whose complement is bipartite, improves the general edge-removal bound to floor(n/2)-1, and gives the first characterization at the n-2 threshold for bipartite complements. The proofs of Theorems 2.3, 3.7, and 4.1 are readable and, as far as I can see, sound. The combinatorial partition lemma (Lemma 2.2) is a neat piece of work, and the Hall argument in Lemma 3.5 goes through cleanly.\n\nThe main proof of Theorem 3.7 relies on Theorem 20 of [10] to assert that K_s □ K_2 has an SSP matrix realization with two distinct eigenvalues for every s, with the s=2 case from [4]. That is a cited result, not proved or constructed here. This is normal practice, but since it is the load-bearing step in both the even-n case and the odd-n reduction, a referee should verify that theorem's statement and proof. I have no reason to doubt it, but it would strengthen the paper to at least state the theorem explicitly.\n\nSoft spots are localized. Lemma 4.3 says it is easy to check that the displayed 7x7 matrix has q=2 and the SSP, without showing the computation. For a constructive proof, a referee may ask for the eigenvalues or an SSP certificate; this is minor. More significant is Theorem 5.1 in the 'Further Evidence' section, which appears to have a statement/notation problem. It defines H as a graph on n-2 vertices with e(H) <= n-4, then writes K_n - E(H) = K2 ∨ H. If H is the removed graph, the expression should be K2 ∨ \\overline{H}. The proof's inequalities suggest H is meant to be the complement of the removed graph. As stated, the theorem is garbled and should be fixed before publication. This does not affect the main theorems, which remain credible.\n\nWho gets value from this: anyone working on the inverse eigenvalue problem for graphs, particularly the q=2 question and the interplay with complements. The bipartite-complement theorem is a genuine advance, and the n-2 characterization is useful. The paper deserves a serious referee; I would send it out, with a request to fix Section 5 and add a short verification for Lemma 4.3.","headline":"Solid, well-written paper with a real proof of the bipartite-complement case of Conjecture 1.1; the main theorems are credible, but Section 5 has a statement/notation problem and the key SSP realization is only cited.","tokens_in":17947,"tokens_out":4030,"would_cite":true,"duration_ms":39164,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A29","15A18"],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph whose complement is bipartite and has at most $n-3$ edges always has a matrix with exactly two distinct eigenvalues.","keywords":["inverse eigenvalue problem for graphs","q-parameter","strong spectral property","bipartite complement","two distinct eigenvalues","joined duplication","Cartesian product"],"falsifier":"Compute $q(G)$ for every graph on nine vertices whose complement is bipartite with at most six edges; any graph for which an exhaustive search shows every admissible symmetric matrix has at least three distinct eigenvalues would disprove Theorem 3.7. A smaller-scale falsifier would be to find a supergraph of $K_s\\square K_2$ that admits no two-eigenvalue realization, contradicting the SSP extension principle used in the proof.","tokens_in":16969,"feed_emoji":"🔢","tokens_out":12800,"duration_ms":114820,"temperature":0.7,"pith_summary":"The paper studies $q(G)$, the minimum number of distinct eigenvalues over all real symmetric matrices whose off-diagonal zero pattern matches a graph $G$. Its central result is that Conjecture 1.1 — if the complement of an $n$-vertex graph has at most $n-3$ edges then $q(G)=2$ — is true whenever the complement is bipartite. The proof shows that every such graph contains a standard ladder graph $K_{n/2}\\square K_2$ after simplifications, and a known two-eigenvalue matrix on that ladder can be extended to the whole graph by the Strong Spectral Property. A second theorem characterizes the borderline case of $n-2$ missing edges: the only bipartite-complement graphs with $q(G)>2$ are those whose complement is a double-star together with an isolated vertex, and there $q(G)=3$.","feed_headline":"Two eigenvalues suffice for bipartite complements","feed_subtitle":"Missing at most n−3 edges and bipartite guarantee a matrix with exactly two distinct eigenvalues.","key_machinery":"The load-bearing object is the Cartesian product $K_s\\square K_2$: two copies of the complete graph $K_s$ joined by a perfect matching, a ladder-like graph whose complement is a complete bipartite graph minus a matching. The paper reduces the bipartite-complement problem to finding this graph inside $G$: for even $n$, Hall's theorem produces the matching that completes the two cliques, and for odd $n$ an isolated vertex of the complement is removed to reduce to the even case. Once $K_{n/2}\\square K_2$ lies inside $G$, the Strong Spectral Property does the rest: a known matrix on $K_s\\square K_2$ with exactly two distinct eigenvalues and the SSP is extended to any supergraph with the same spectrum. Joined duplication transfers the result from the reduced graph back to the original graph.","core_discovery":"The paper establishes that, for every graph $G$ whose complement $\\overline G$ is bipartite and has $e(\\overline G)\\le n-3$, there is a real symmetric matrix with off-diagonal zero pattern exactly $G$ and exactly two distinct eigenvalues, i.e. $q(G)=2$. This resolves Conjecture 1.1 on the entire bipartite-complement class. At the next edge count, $e(\\overline G)=n-2$, the paper proves that $q(G)=2$ unless $\\overline G=S_{a,b}\\cup K_1$ for some $a,b\\ge0$, in which case $q(G)=3$; this is the only way a unique induced path of length two blocks the two-eigenvalue realization. The same strategy also yields the unconditional general bound $q(G)=2$ for all graphs with $e(\\overline G)\\le\\lfloor n/2\\rfloor-1$.","pith_inferences":["The ladder-embedding strategy suggests that the full Conjecture 1.1 will follow if every graph with $e(\\overline G)\\le n-3$ contains $K_s\\square K_2$ after deleting isolated vertices; the remaining difficulty looks purely combinatorial rather than spectral.","The $n-2$ characterization singles out a unique induced path of length two in the complement as the obstruction, matching the necessary condition of Lemma 1.2; if Conjecture 5.5 holds, the whole $q=2$ problem for dense graphs reduces to checking one forbidden configuration.","The explicit SSP matrices constructed for complements of $W(k,1,\\vec 1)\\cup K_1$ are parametric and could be reused in future inductive extensions of the theorem to non-bipartite complements."],"forward_implications":["Every graph with bipartite complement and $e(\\overline G)\\le n-3$ satisfies $q(G)=2$, settling Conjecture 1.1 for the entire bipartite-complement family.","For general graphs, $q(G)=2$ whenever $e(\\overline G)\\le\\lfloor n/2\\rfloor-1$, the strongest unconditional form of the requires problem obtained in the paper.","At $e(\\overline G)=n-2$ with bipartite complement, $q(G)=3$ exactly for $\\overline G=S_{a,b}\\cup K_1$; all other such graphs have $q(G)=2$.","The strengthened Conjecture 5.5 asserts that the same double-star-plus-isolated-vertex characterization holds without the bipartite assumption at $e(\\overline G)\\le n-2$.","Joined duplication preserves or lowers $q$, so odd-order cases reduce to even-order ladder cases and keep the $q=2$ conclusion."],"supporting_citations":[{"why":"Supplies the SSP two-eigenvalue realization of $K_s\\square K_2$ for all $s\\ge3$, the fact that carries Theorem 3.7.","marker":"[10]"},{"why":"Supplies the $s=2$ case of the same $K_s\\square K_2$ realization, needed when $n=4$ or in the odd reduction.","marker":"[4]"},{"why":"Theorem 2.7 handles bipartite graphs outside the spanning double-biclique obstruction; Lemma 2.9 gives the joined-duplication inequality used throughout.","marker":"[16]"},{"why":"Theorem 10 extends an SSP matrix to every supergraph, allowing $q=2$ to pass from the ladder to the dense graph $G$.","marker":"[7]"},{"why":"Proposition 5.2 gives $q=2$ for joins of connected equal-order graphs, used in proving the general $\\lfloor n/2\\rfloor-1$ bound.","marker":"[13]"},{"why":"Theorem 3.4 covers joins whose orders differ by at most two, used in the same bound and in parity reductions.","marker":"[17]"},{"why":"Lemma 5.1 is the criterion used to certify the Strong Spectral Property for the matrices built for $W(k,1,\\vec 1)\\cup K_1$.","marker":"[18]"}],"fun_headline_variants":["Bipartite complements ensure two distinct eigenvalues","Two eigenvalues for graphs with bipartite complements","Sparse bipartite complements lead to exactly two eigenvalues","Only one obstruction to two eigenvalues in bipartite complements","Two eigenvalues for all but one bipartite complement graph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the previously established fact that the ladder graph $K_s\\square K_2$, two equal cliques connected by a perfect matching, has a symmetric matrix with exactly two distinct eigenvalues and the Strong Spectral Property for every $s$; if that matrix did not exist, the extension argument behind Theorem 3.7 would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Bipartite complements ensure two distinct eigenvalues","Two eigenvalues for graphs with bipartite complements","Sparse bipartite complements lead to exactly two eigenvalues","Only one obstruction to two eigenvalues in bipartite complements","Two eigenvalues for all but one bipartite complement graph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000466,"raw_usage":{"total_tokens":2285,"prompt_tokens":864,"completion_tokens":1421,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":1349}},"tokens_in":480,"tokens_out":1421,"duration_ms":9808,"temperature":1.0,"reasoning_tokens":1349,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:06:10.134160+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $q(G)$ for every graph on nine vertices whose complement is bipartite with at most six edges; any graph for which an exhaustive search shows every admissible symmetric matrix has at least three distinct eigenvalues would disprove Theorem 3.7. A smaller-scale falsifier would be to find a supergraph of $K_s\\square K_2$ that admits no two-eigenvalue realization, contradicting the SSP extension principle used in the proof.","supporting_citations":[{"cited_title":"Spectral applications of v ertex-clique incidence matrices associated with a graph","cited_arxiv_id":null,"evidence_quote":"Supplies the SSP two-eigenvalue realization of $K_s\\square K_2$ for all $s\\ge3$, the fact that carries Theorem 3.7."},{"cited_title":"Fallat, H","cited_arxiv_id":null,"evidence_quote":"Supplies the $s=2$ case of the same $K_s\\square K_2$ realization, needed when $n=4$ or in the odd reduction."},{"cited_title":"Levene, Polona Oblak, and Helena ˇSmigoc","cited_arxiv_id":null,"evidence_quote":"Theorem 2.7 handles bipartite graphs outside the spanning double-biclique obstruction; Lemma 2.9 gives the joined-duplication inequality used throughout."},{"cited_title":"Tracy Hall, Leslie Hogben, Jephia n C.-H","cited_arxiv_id":null,"evidence_quote":"Theorem 10 extends an SSP matrix to every supergraph, allowing $q=2$ to pass from the ladder to the dense graph $G$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proposition 5.2 gives $q=2$ for joins of connected equal-order graphs, used in proving the general $\\lfloor n/2\\rfloor-1$ bound."},{"cited_title":"Levene, Polona Oblak, and Helena ˇSmigoc","cited_arxiv_id":null,"evidence_quote":"Theorem 3.4 covers joins whose orders differ by at most two, used in the same bound and in parity reductions."},{"cited_title":"The strong spectral property for graphs","cited_arxiv_id":null,"evidence_quote":"Lemma 5.1 is the criterion used to certify the Strong Spectral Property for the matrices built for $W(k,1,\\vec 1)\\cup K_1$."}],"review_version":1}