Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

Graphs with Bipartite Complement that Admit Two Distinct Eigenvalues

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A graph whose complement is bipartite and has at most $n-3$ edges always has a matrix with exactly two distinct eigenvalues.

desk verdict 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. read the letter →

arxiv 2411.12917 v1 pith:WTSJUZ4T submitted 2024-11-19 math.CO

Wayne Barrett , Shaun Fallat , Veronika Furst , Shahla Nasserasr , Brendan Rooney , Michael Tait This is my paper · ORCID
classification math.CO MSC 05C5015A2915A18
keywords inverseeigenvalueproblemforgraphsq-parameterstrongspectralpropertybipartitecomplementtwodistincteigenvaluesjoinedduplicationCartesianproduct
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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.

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 (3)
  1. [Section 3, proof of Theorem 3.7] 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).
  2. [Section 5, Theorem 5.1] 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.
  3. [Section 4, Lemma 4.3] 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.
minor comments (3)
  1. [Throughout Sections 2–4] 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.
  2. [Lemma 3.5, proof after Figure 2] 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’).
  3. [Theorem 5.3, proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central theorem reduces bipartite-complement graphs to independently proven spectral facts about Cartesian-product graphs, not to its own inputs.

full rationale

Theorem 3.7 is not circular. The paper's new content is a structural reduction: Lemmas 3.4, 3.6, and 3.5 show, by elementary counting and Hall's theorem, that every simplified graph whose complement is bipartite and has at most n-3 edges contains K_{n/2} □ K_2 as a subgraph (with an isolated-vertex reduction in the odd order case). This part of the proof never uses the target conclusion q(G)=2. The final spectral step invokes Theorem 20 of [10] and the s=2 case from [4] for the existence of SSP matrices with two distinct eigenvalues on K_s □ K_2, together with Theorem 10 of [7] to extend such realizations to supergraphs. These are parameter-free published theorems whose hypotheses concern a specific Cartesian-product graph and do not include Conjecture 1.1 or the arbitrary supergraphs in Theorem 3.7, so they are independent support rather than self-citation load-bearing. No parameters are fitted, no quantity is defined in terms of the result, and no uniqueness theorem is imported to forbid alternatives. The joined-duplication and same-neighborhood reductions are explicit graph transformations with independent proofs, and Theorem 5.1 is transparently conditional on the conjecture for smaller orders. Thus no step of the derivation reduces to its own input.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters or invented entities. The paper's contributions are theorems and explicit matrices; the only inputs are prior published results (SSP framework, [16]'s bipartite theorem, [10]'s lattice-graph realization) and standard mathematics. None of these are fitted to produce the target result.

assumptions (7)
  • domain assumption Theorem 3.1 of [16]: a bipartite graph not containing K_{m1,n1} union K_{m2,n2} as a spanning subgraph has q=2
    Primary external tool for the generic bipartite case in Theorem 3.7; stated in Section 3 and used without proof.
  • domain assumption Theorem 20 of [10]: K_s box K_2 has an SSP realization with two distinct eigenvalues for s at least 3, and [4] for s=2
    Used to conclude q=2 for supergraphs in Theorem 3.7 and Theorem 4.1.
  • domain assumption SSP extension theorem (Theorem 10 of [7]): a matrix with SSP in S(G) extends to any supergraph with the same spectrum
    Basis for Lemma 1.7, Theorem 5.3, and Porism 5.4.
  • domain assumption Lemma 1.4 from [16]: q(jdup(G,v)) is at most q(G)
    Used in Observation 3.3 and the odd-n reductions to remove or duplicate vertices.
  • domain assumption Lemma 1.2 from [2]: a length-2 path in a q=2 graph must have its endpoints adjacent or have a second common neighbor
    Used in Observation 1.3 and to prove q=3 for the exceptional S_{a,b} union K1 graphs in Theorem 4.1.
  • standard math Hall's Theorem
    Used in Lemma 3.5 to build a perfect matching in the bipartite complement.
  • standard math Weyl's eigenvalue perturbation theorem
    Used in Lemma 5.2 to control the spectrum of M^T M.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graphs with Bipartite Complement that Admit Two Distinct Eigenvalues." pith.science (2026). https://pith.science/paper/WTSJUZ4T

@misc{pith2026241112917,
  author       = {Pith},
  title        = {Pith review of: Graphs with Bipartite Complement that Admit Two Distinct Eigenvalues},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WTSJUZ4T}},
  note         = {Machine review of arXiv:2411.12917}
}
abstract

The parameter $q(G)$ of an $n$-vertex graph $G$ is the minimum number of distinct eigenvalues over the family of symmetric matrices described by $G$. We show that all $G$ with $e(\overline{G}) = |E(\overline{G})| \leq \lfloor n/2 \rfloor -1$ have $q(G)=2$. We conjecture that any $G$ with $e(\overline{G}) \leq n-3$ satisfies $q(G) = 2$. We show that this conjecture is true if $\overline{G}$ is bipartite and in other sporadic cases. Furthermore, we characterize $G$ with $\overline{G}$ bipartite and $e(\overline{G}) = n-2$ for which $q(G) > 2$.

Figures

Figures reproduced from arXiv: 2411.12917 by the authors.

Figure 1
Figure 1. The graphs W(5, 0,~1) and W(4, 1,~1). This paper is organized as follows. In Section 2 we present some results towards the full generality of Conjecture 1.1 but with fewer removed edges. In Section 3 we establish our principal result (Theorem 3.7) that the conjecture holds under the additional assumption that G is bipartite. Moreover, for G bipartite and e(G) = n−2, we establish in Section 4 (Theorem 4.1) that q(G) … view at source ↗
Figure 2
Figure 2. are candidates for e(G) ∈ {3, 4, 5}. e(G) = 3 e(G) = 4 e(G) = 5 e(G) = 5 e(G) = 5 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. The graph H7. Lemma 4.4. For any k ≥ 3, there is a matrix B and vector ~v that satisfy the following: 1. B ∈ S(Kk+1), 2. the spectral radius of B is strictly less than 1, 3. there is a totally nonzero unit vector ~v in the null space of B, 4. B2 is entrywise positive. Proof. Let Tk+1 be the (k + 1)× (k + 1) matrix with [Tk+1]i,j = (i − j) 2 for all 1 ≤ i, j ≤ k + 1. It follows easily that Tk+1 ∈ S(Kk+1) and Tk+1 has… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Two Distinct Eigenvalues from a New Graph Product

    math.CO 2025-01 conditional novelty 6.0 of 10

    A new graph product and a tensor-based matrix construction yield new infinite families of graphs whose minimum number of distinct eigenvalues equals two.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages · cited by 1 Pith paper

  1. [10]

    Spectral applications of v ertex-clique incidence matrices associated with a graph

    Shaun Fallat and Seyed Ahmad Mojallal. Spectral applications of v ertex-clique incidence matrices associated with a graph. Mathematics, 11(16), 2023

    work page 2023

  2. [4]

    Fallat, H

    Wayne Barrett, Steve Butler, Shaun M. Fallat, H. Tracy Hall, Les lie Hogben, Jephian C.-H. Lin, Bryan L. Shader, and Michael Young. The inverse eigenvalue proble m of a graph: multiplicities and minors. J. Combin. Theory Ser. B , 142:276–306, 2020

    work page 2020

  3. [7]

    Tracy Hall, Leslie Hogben, Jephia n C.-H

    Wayne Barrett, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephia n C.-H. Lin, and Bryan L. Shader. Generalizations of the strong Arnold property and the minimum numb er of distinct eigenvalues of a graph. Electron. J. Combin. , 24(2):Paper No. 2.40, 28, 2017

    work page 2017

  4. [1]

    Achievable multiplicity partitions in the inverse eigenvalue problem of a g raph

    Mohammad Adm, Shaun Fallat, Karen Meagher, Shahla Nasserasr , Sarah Plosker, and Boting Yang. Achievable multiplicity partitions in the inverse eigenvalue problem of a g raph. Spec. Matrices, 7:276– 290, 2019

    work page 2019

  5. [2]

    Cavers, Shaun Fallat, Karen Meagher, and Shahla Nasserasr

    Bahman Ahmadi, Fatemeh Alinaghipour, Michael S. Cavers, Shaun Fallat, Karen Meagher, and Shahla Nasserasr. Minimum number of distinct eigenva lues of graphs. Electron. J. Linear Algebra , 26:673–691, 2013. Erratum available at: https://journals.uwyo.edu/index.php/ela/article/view/1293/5765

    work page 2013

  6. [3]

    John Ahn, Christine Alar, Beth Bjorkman, Steve Butler, Joshua Carlson, Audrey Goodnight, Haley Knox, Casandra Monroe, and Michael C. Wigal. Ordered multiplicity inv erse eigenvalue problem for graphs on six vertices. Electron. J. Linear Algebra , 37:316–358, 2021

    work page 2021

  7. [5]

    Sparsity of graphs that allow tw o distinct eigenvalues

    Wayne Barrett, Shaun Fallat, Veronika Furst, Franklin Kenter, Shahla Nasserasr, Brendan Rooney, Michael Tait, and Hein van der Holst. Sparsity of graphs that allow tw o distinct eigenvalues. Linear Algebra Appl., 674:377–395, 2023

    work page 2023

  8. [6]

    Regular graphs of degree at most four that allow two distinct eigenv alues

    Wayne Barrett, Shaun Fallat, Veronika Furst, Shahla Nasseras r, Brendan Rooney, and Michael Tait. Regular graphs of degree at most four that allow two distinct eigenv alues. Linear Algebra Appl. , 679:127–164, 2023

    work page 2023

Show all 18 references
  1. [8]

    Applica- tions of analysis to the determination of the minimum number of distinc t eigenvalues of a graph

    Beth Bjorkman, Leslie Hogben, Scarlitte Ponce, Carolyn Reinhar t, and Theodore Tranel. Applica- tions of analysis to the determination of the minimum number of distinc t eigenvalues of a graph. Pure Appl. Funct. Anal. , 3(4):537–563, 2018

    2018

  2. [9]

    John son, Margaret Lay, Terry D

    Matthew Booth, Philip Hackney, Benjamin Harris, Charles R. John son, Margaret Lay, Terry D. Lenker, Lon H. Mitchell, Sivaram K. Narayan, Amanda Pascoe, and B rian D. Sutton. On the minimum semidefinite rank of a simple graph. Linear Multilinear Algebra , 59(5):483–506, 2011

    2011

  3. [11]

    Hu nter, Bonnie Jacob, Andrew Klimas, and Sharon McCathern

    Cheryl Grood, Johannes Harmse, Leslie Hogben, Thomas J. Hu nter, Bonnie Jacob, Andrew Klimas, and Sharon McCathern. Minimum rank with zero diagonal. Electron. J. Linear Algebra, 27:458–477, 2014

    2014

  4. [12]

    Zero forcing sets and the minimum rank of graphs

    AIM Minimum Rank-Special Graphs Work Group et al. Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl. , 428(7):1628–1648, 2008

    2008

  5. [13]

    Keivan Hassani Monfared and Bryan L. Shader. The nowhere- zero eigenbasis problem for a graph. Linear Algebra Appl. , 505:296–312, 2016. 15

    2016

  6. [14]

    Lin, and Bryan L

    Leslie Hogben, Jephian C.-H. Lin, and Bryan L. Shader. Inverse problems and zero forcing for graphs , volume 270 of Mathematical Surveys and Monographs . American Mathematical Society, Providence, RI, 2022

    2022

  7. [15]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson. Matrix analysis . Cambridge University Press, Cambridge, second edition, 2013

    2013

  8. [16]

    Levene, Polona Oblak, and Helena ˇSmigoc

    Rupert H. Levene, Polona Oblak, and Helena ˇSmigoc. A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph. Linear Algebra Appl. , 564:236–263, 2019

    2019

  9. [17]

    Levene, Polona Oblak, and Helena ˇSmigoc

    Rupert H. Levene, Polona Oblak, and Helena ˇSmigoc. Distinct eigenvalues are realizable with generic eigenvectors. Linear Multilinear Algebra , 72(12):2054–2068, 2024

    2024

  10. [18]

    The strong spectral property for graphs

    Jephian C.-H Lin, Polona Oblak, and Helena ˇSmigoc. The strong spectral property for graphs. arXiv preprint, 2019. 16

    2019

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.