Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Generalized Nordhaus--Gaddum Inequalities for Eigenvalues

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

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

Pith's one-line read This paper proves that for every looped graph on n vertices, the largest eigenvalue plus the second-largest eigenvalue of its complement never exceeds 8n/7, and that this constant is asymptotically exact.

desk verdict The upper-bound machinery is solid and worth reading, but the claimed exact value α_{1,2}=8/7 is not established because the lower-bound proposition is wrong. read the letter →

arxiv 2607.15941 v1 pith:N3HQWNEU submitted 2026-07-17 math.CO

Sahil Agarwal , Carter Antley , Joseph Aulenbacher , George Brooks , Ian Gonzalez , Luke Hawranick , William Linz , Linyuan Lu
show 1 more author
Aiden Williams
This is my paper · ORCID
classification math.CO MSC 05C50
keywords Nordhaus–GadduminequalitiesadjacencyeigenvaluesspectralradiuseigenvaluesumgraphcomplementPerronvectorgaploopedgraphs
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

Across all looped graphs on n vertices, the paper proves that λ1(G)+λ2(complement) is at most (8/7)n, and that this ratio is asymptotically sharp, so α_{1,2}=8/7 exactly. This is the first exact value in a natural family of Nordhaus–Gaddum problems for eigenvalues. The same proof technique gives a short, self-contained derivation of the known bound λ1(G)+λ1(complement) ≤ (4/3)n−1 for simple graphs. For every k≥2, the paper also derives general upper bounds on λ1(G)+λk(complement), reducing them to a quadratic inequality and a Lagrange-multiplier optimization. The results are obtained from Perron vectors, Weyl inequalities, and trace identities, with no heavy machinery.

What carries the argument

The main instrument is Lemma 16, which bounds λ1(G)+λk(complement) by 4kn/(4k−1) whenever the complement has k nonnegative vectors y_r with pairwise disjoint supports satisfying A(complement)y_r ≥ λk y_r. The proof introduces the deficit vector d=(c/λ1)1−x for the Perron eigenvector x of G, and shows that each y_r forces at least c μ^2/(λ(λ+μ)) total deficit on its support; disjointness then sums these lower bounds to produce the inequality. For k=2, the required vectors are constructed by examining the component structure of the complement. The general upper bounds of Section 3 instead combine the trace identities tr(A^2)+tr(B^2)=n^2 and tr(A)+tr(B)=n with Weyl's inequalities, yielding a qu

What would settle it

Compute the adjacency spectrum of G=J_{2k−1}∨kJ₂ for k=3 (or any k≥3) and check whether λ1(G)+λk(G) equals 4k; the proposed Perron vector fails Ax=(4k−2)x, so this is directly checkable. Also compute the spectrum of the 7-vertex graph J3∨C4 and verify whether its t-blowup has (λ1+λ2)/n tending to 8/7. If the first quantity is less than 4k, Conjecture 20 is false; if the second is not 8/7, the stated extremal graph is wrong.

Watch

Extended reading notes

Core claim

The central claim is the exact asymptotic constant α_{1,2}=8/7: the limit of max_G (λ1(G)+λ2(complement))/n over looped graphs G equals 8/7, and equality is attained by blowups of the looped graph J3∨C4 (a looped triangle joined to a 4-cycle). The proof of the upper bound models the complement's second eigenvalue by two nonnegative vectors with pairwise disjoint supports that act as approximate eigenvectors, then uses a 'deficit vector' derived from the Perron eigenvector of G to obtain λ1+λ2 ≤ 8n/7. The same lemma immediately yields λ1+λ1 ≤ 4n/3, reproducing the known spectral-radius Nordhaus–Gaddum bound with a short argument. For general k, a trace-plus-Weyl argument produces a quadratic

Load-bearing premise

The tightness results for the α_{1,k} bounds rely on a specific Perron-vector computation for the graph J_{2k−1}∨kJ₂ (Proposition 13); for k≥3 that vector does not satisfy the eigenvector equation, so the lower bounds and the exactness of α_{1,2}=8/7 as proven in the paper depend on this unsupported calculation, even though the separately stated extremal graph J3∨C4 may still be correct if its spectrum is checked directly.

Editorial extensions

If this is right

  • If α_{1,2}=8/7 is correct, extremal sequences must asymptotically look like blowups of J3∨C4, giving a concrete structural prediction for near-extremal graphs.
  • The deficit-vector lemma gives a one-page proof of the spectral-radius Nordhaus–Gaddum bound λ1+λ1 ≤ 4n/3, making the previously analytic proof elementary.
  • The quadratic-inequality method yields the general upper bound λ1+λk ≤ n(k+√(k(4k−1)))/(3k−1), which for k≥2 improves the bound obtained from spectral-gap estimates.
  • The analogous smallest-eigenvalue problem is settled up to a signed constant: |β_{i,j}| ≤ (1/2)√(1/i+1/j), with equality for i=j=k whenever a symmetric Hadamard matrix of order 2k exists.
  • The connection via Weyl's inequalities shows that α_{i,j} lies between the spread constants s_{i−1,j−1} and s_{i−1,j−2}, so progress on spectral gaps transfers directly to Nordhaus–Gaddum constants.

Reading between the lines

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

  • The deficit-vector construction might generalize to all k: if one can produce k disjoint approximate eigenvectors for the complement of a candidate extremal graph, the bound 4k/(4k−1) would be tight for every k, making the paper's Conjecture 20 plausible despite the apparent error in the stated lower-bound construction.
  • The lower-bound construction in Proposition 13 appears to contain an algebraic error for k≥3 (the claimed Perron vector is not actually an eigenvector); correcting it could change the conjectured values of α_{1,k}.
  • The method of bounding λ1+λk by a quadratic inequality in the two individual eigenvalues may extend to other pairs (i,j), potentially yielding exact constants for all (i,j) where the extremal graphs are regular.
  • Because the (1,2) extremal graph J3∨C4 is near-regular, a plausible pattern is that extremal sequences for all pairs are regular or nearly regular; if so, the gap between the two spread bounds in Lemma 9 closes and gives exact α_{i,j}.
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 / 4 minor

Summary. The paper studies Nordhaus–Gaddum type problems for adjacency eigenvalues of looped graphs, focusing on α_{i,j} = lim n^{-1} max_G (λ_i(G)+λ_j(\bar G)) and the analogous minimum quantity β_{i,j}. The authors prove general upper bounds on α_{i,j} using the Brooks–Linz–Lu spread bounds, give a new short proof of Terpai's theorem λ_1(G)+λ_1(\bar G) ≤ (4/3)n − 1, and prove the upper bound λ_1(G)+λ_2(\bar G) ≤ (8/7)n. They further claim the exact value α_{1,2} = 8/7, achieved by a blowup of J_3∨C_4, and conjecture α_{1,k} = 4k/(4k−1) for all k ≥ 3, supported by a construction in Proposition 13. The paper also proves an upper bound α_{1,k} ≤ (k+√(k(4k−1)))/(3k−1) and bounds on |β_{i,j}|.

Significance. The upper-bound machinery is attractive and, in particular, Lemma 16 gives a genuinely short and self-contained proof of Terpai's bound, which is a meaningful contribution. The claimed upper bound λ_1(G)+λ_2(\bar G) ≤ 8n/7, if correct, is also a strong result, and the connection to spectral spreads is well motivated. However, the paper's claimed exact value α_{1,2}=8/7 is not established as written: the lower-bound argument in Proposition 13 is false, and the spectrum of the separately stated extremal graph J_3∨C_4 is never computed. Because the exactness claim and the conjecture for k ≥ 3 rest on that invalid proposition, the central contribution of the paper is currently unsupported. The upper bounds and the Terpai proof are sound and salvageable, so the manuscript has clear potential after a substantial revision.

major comments (3)
  1. [Section 3, Proposition 13] Proposition 13 is false. For G = J_{2k−1}∨kJ_2, the vector x with x_i=2k on the J_{2k−1} part and x_i=2k−1 on the kJ_2 part is not an eigenvector for k ≥ 2. For a vertex in kJ_2, (Ax)_i = (2k−1)(2k+1), whereas (4k−2)x_i = (2k−1)(4k−2); these agree only when k=3/2. Thus the asserted λ_1(G)=4k−2 is incorrect. Moreover, the proof applies λ_k(G) rather than λ_k(\bar G). For k=2, G=J_3∨2J_2 has complement consisting of three isolated vertices plus a simple C_4, so λ_2(\bar G)=0, and λ_1(G)+λ_2(\bar G)=2+√13≈5.61, not 8. This proposition cannot provide the claimed lower bound α_{1,k} ≥ 4k/(4k−1).
  2. [Theorem 18 and Theorem 3] The proof of Theorem 18 concludes 'Proposition 13 shows that this bound is tight', but Proposition 13 is not only false; its graph J_3∨2J_2 is not the extremal graph J_3∨C_4 named in Theorem 3. The spectrum of J_3∨C_4 is never computed in the paper, and no other lower-bound construction for α_{1,2}=8/7 is supplied. Since the equality claim requires both an upper bound and a matching lower bound, α_{1,2}=8/7 is unproven as written. A direct computation (λ_1(J_3∨C_4)=6 and λ_2 of its complement =2) would repair this, but the computation must actually appear.
  3. [Conjecture 20 and Appendix Table 2] The conjecture α_{1,k}=4k/(4k−1) for k ≥ 3 and the lower-bound entries in Table 2 for row i=1 rely entirely on Proposition 13. Since that proposition is false, these lower bounds are unsupported. In particular, Table 2 lists 'J_3∨2J_2' as the extremal graph for α_{1,2}, contradicting Theorem 3's claim that the extremal graph is J_3∨C_4. The tables and conjecture should be revised to reflect only constructions whose spectra are actually verified.
minor comments (4)
  1. [Theorem 14 statement] Theorem 14 states an upper bound on λ_1(G)+λ_k(G), but the proof and the definition of α_{1,k} show the intended quantity is λ_1(G)+λ_k(\bar G). The notation should be corrected consistently.
  2. [Proof of Theorem 14] In the sentence 'we denote the eigenvalues of G by μ_1 ≥ ... ≥ μ_n', the graph should be \bar G, as is clear from the trace identity that follows.
  3. [Proposition 13, notation] The expression 'G = kJ_2 ∪ (2k−1)K_1 = J_{2k−1} ∨ kJ_2' is confusing: a disjoint union is not a join. The graph should be defined unambiguously, preferably with an explicit adjacency-matrix description.
  4. [Appendix Table 2] The extremal graph listed for α_{1,2} is inconsistent with the statement of Theorem 3. If J_3∨C_4 is the intended graph, the table should say so and give its spectrum.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main upper bounds are derived from Perron-Frobenius, Weyl, and trace identities. The disclosed Brooks–Linz–Lu self-citation is not load-bearing for the central new claims. Proposition 13 contains a serious mathematical gap, but it is a correctness issue, not a circular reduction.

full rationale

The central derivation chain is not circular. Theorem 4 derives its upper bound from trace identities, Weyl inequalities, and a Lagrange-multiplier optimization; Theorem 5 does the same; Lemma 16 and Theorems 17–18 are proven from Perron eigenvectors and elementary inequalities. None of these steps fits a parameter to the target value or assumes the conclusion. The reuse of the Brooks–Linz–Lu spread bounds in Theorem 2 is a disclosed self-citation, but it is not load-bearing for the paper's main new results (Theorems 3–5), and the spread bounds are parameter-free stated results from the authors' prior work. The notable flaw is Proposition 13: its proof computes λ1(G)+λ_k(G) and asserts this gives a lower bound on α_{1,k}, which by definition involves λ_k(\bar G); the Perron-vector claim is also not generally valid. This is a mathematical gap/incorrect computation, not a circular reduction, because the claimed inequality does not hold by construction or by a fitted parameter. The same applies to the unshown spectrum of the stated extremal graph J3∨C4: the omission affects validity of the tightness proof, not the circularity status. Score 1 reflects the minor disclosed self-citation; it does not indicate a circular derivation.

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

The central proofs use standard spectral graph theory tools; no numbers are fitted to data. The main nonstandard assumption is the erroneous Proposition 13, which is ad hoc to this paper and unsupported.

assumptions (8)
  • standard math Perron-Frobenius theorem for nonnegative matrices
    Used in Lemma 16 and Theorem 17 to obtain a nonnegative Perron eigenvector x and to analyze connected components of the complement.
  • standard math Weyl's inequalities for eigenvalues of Hermitian matrices
    Used throughout for the relation A(G)+A(complement)=J, e.g., λ_i+μ_{n+1-i}≥λ_n(J)=0 and λ_i+μ_k≤0 for i≥n-k+2.
  • domain assumption Nikiforov's theorem on the existence of limits for linear combinations of graph eigenvalues
    Used to justify that α_{i,j} and β_{i,j} are well-defined limits; cited as [13].
  • domain assumption Brooks-Linz-Lu bounds on the (i,j)-spread (Theorems 10-12 of [3])
    Used to prove Theorem 2's general bounds on α_{i,j}; cited [3], a paper with overlapping authors.
  • standard math t-blowup eigenvalue scaling property
    Used to convert finite graph constructions into asymptotic lower bounds; stated in Section 2.
  • domain assumption Existence of symmetric Hadamard matrices of order 2k for sharpness of certain bounds
    Used to assert equality in Corollary 6 and Theorem 2(3) for infinitely many k; conditional on Hadamard existence.
  • domain assumption Nikiforov's result [15, Theorem 2.6] used to assume λ_{n-i+1}<0 and μ_{n-j+1}<0 in Theorem 5
    Cited prior result needed to set up the optimization in the β_{i,j} proof.
  • ad hoc to paper Proposition 13's Perron-vector claim (x_i=2k on J_{2k−1} and 2k−1 on kJ₂)
    Asserted without a correct proof and false for k≥3; the paper's lower bounds and Conjecture 20 depend on it. Flagged as a red flag.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generalized Nordhaus--Gaddum Inequalities for Eigenvalues." pith.science (2026). https://pith.science/paper/N3HQWNEU

@misc{pith2026260715941,
  author       = {Pith},
  title        = {Pith review of: Generalized Nordhaus--Gaddum Inequalities for Eigenvalues},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3HQWNEU}},
  note         = {Machine review of arXiv:2607.15941}
}
abstract

For a graph $G$, let $ \lambda_1(G)\ge \lambda_2(G)\ge \cdots \ge \lambda_n(G)$ denote the adjacency eigenvalues of $G$. We investigate the asymptotic maximum of \[ \lambda_i(G)+\lambda_j(\overline G) \] for fixed $i$ and $j$. We prove general bounds on $\lambda_i(G) + \lambda_{j}(\overline{G})$ for all pairs $(i, j)$ and also give general bounds on the related problem of minimizing $\lambda_{n-i+1}(G) + \lambda_{n-j+1}(\overline{G})$ for fixed $i$ and $j$. We prove that for all looped graphs $G$ on $n$ vertices, \[\lambda_1(G) + \lambda_2(\overline{G}) \le \frac87 n. \] Our method also gives a new short proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that $\lambda_1(G) + \lambda_1(\overline{G}) \le \frac43n - 1$. We also show the close relation of these Nordhaus-Gaddum type problems to recent work on the maximum spectral gaps of graphs by Brooks, Linz and Lu.

Figures

Figures reproduced from arXiv: 2607.15941 by the authors.

Figure 1
Figure 1. G1, where the vertices with self-loops are colored in black [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. G2, where the vertices with self-loops are colored in black. References [1] M. Aouchiche and P. Hansen. A survey of nordhaus-gaddum type relations. Discrete Applied Math￾ematics, 161(4–5):466–546, 2013. [2] Jane Breen, Alex W. N. Riasanovsky, Michael Tait, and John Urschel. Maximum spread of graphs and bipartite graphs. Commun. Am. Math. Soc., 2:417–480, 2022. [3] George Brooks, William Linz, and Linyuan Lu. Maximum… 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. Graph Eigenvalues and Projection Constants

    math.CO 2026-08 conditional novelty 7.0 of 10

    λ_k(G) ≤ ((k−2)√(k+1)+2)n/(2k(k−1)) − 1 for all graphs, tight for k ∈ {2,3,4,8,24}, resolving c₃ = 1/3 and Nikiforov's Conjecture 4.2.

Reference graph

Works this paper leans on

22 extracted references · 3 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Aouchiche and P

    M. Aouchiche and P. Hansen. A survey of nordhaus-gaddum type relations.Discrete Applied Math- ematics, 161(4–5):466–546, 2013

    2013

  2. [2]

    Jane Breen, Alex W. N. Riasanovsky, Michael Tait, and John Urschel. Maximum spread of graphs and bipartite graphs.Commun. Am. Math. Soc., 2:417–480, 2022

    2022

  3. [3]

    Maximum spectral gaps of graphs.Linear Algebra and its Applications, 730:297–312, 2026

    George Brooks, William Linz, and Linyuan Lu. Maximum spectral gaps of graphs.Linear Algebra and its Applications, 730:297–312, 2026

    2026

  4. [4]

    Cheng and C

    Y.J. Cheng and C. Weng. The maximum value ofλ 1(g) +λ 1(g), 2025. Preprint.arxiv.org/pdf/ 2506.11401

    arXiv 2025

  5. [5]

    On a conjecture of V

    P´ eter Csikv´ ari. On a conjecture of V. Nikiforov.Discrete Math., 309(13):4522–4526, 2009

    2009

  6. [6]

    On the sum of two largest eigenvalues of a symmetric matrix.Linear Algebra Appl., 429(11-12):2781–2787, 2008

    Javad Ebrahimi B, Bojan Mohar, Vladimir Nikiforov, and Azhvan Sheikh Ahmady. On the sum of two largest eigenvalues of a symmetric matrix.Linear Algebra Appl., 429(11-12):2781–2787, 2008. 14

    2008

  7. [7]

    Gregory, Daniel Hershkowitz, and Stephen J

    David A. Gregory, Daniel Hershkowitz, and Stephen J. Kirkland. The spread of the spectrum of a graph. InProceedings of the Eighth Conference of the International Linear Algebra Society (Barcelona, 1999), volume 332/334, pages 23–35, 2001

    1999

  8. [8]

    Maximum spectral sum of graphs

    Hitesh Kumar, Lele Liu, Hermie Monterde, Shivaramakrishna Pragada, and Michael Tait. Maximum spectral sum of graphs. Preprint, arXiv:2604.00512 [math.CO] (2026), 2026

    arXiv 2026

Show all 22 references
  1. [9]

    On graphs with large third eigenvalue.Linear Algebra Appl., 741:66– 96, 2026

    Giacomo Leonida and Sida Li. On graphs with large third eigenvalue.Linear Algebra Appl., 741:66– 96, 2026

    2026

  2. [10]

    Strengthened upper bound on the third eigenvalue of graphs

    Sida Li. Strengthened upper bound on the third eigenvalue of graphs. Preprint, arXiv:2501.07494 [math.CO] (2025), 2025

    2025 arXiv

  3. [11]

    Improved lower bounds on the extrema of eigenvalues of graphs.Graphs Comb., 39(4):4, 2023

    William Linz. Improved lower bounds on the extrema of eigenvalues of graphs.Graphs Comb., 39(4):4, 2023. Id/No 82

    2023

  4. [12]

    Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues.SIAM Journal on Discrete Mathematics, 37(3):1882–1895, 2023

    Lele Liu. Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues.SIAM Journal on Discrete Mathematics, 37(3):1882–1895, 2023

    2023

  5. [13]

    Linear combinations of graph eigenvalues.Electronic Journal of Linear Algebra, 15:329–336, 2006

    Vladimir Nikiforov. Linear combinations of graph eigenvalues.Electronic Journal of Linear Algebra, 15:329–336, 2006

    2006

  6. [14]

    Eigenvalue problems of Nordhaus-Gaddum type.Discrete Math., 307(6):774– 780, 2007

    Vladimir Nikiforov. Eigenvalue problems of Nordhaus-Gaddum type.Discrete Math., 307(6):774– 780, 2007

    2007

  7. [15]

    Extrema of graph eigenvalues.Linear Algebra and Its Applications, 482:158–190, 2015

    Vladimir Nikiforov. Extrema of graph eigenvalues.Linear Algebra and Its Applications, 482:158–190, 2015

    2015

  8. [16]

    More eigenvalue problems of nordhaus-gaddum type.Linear Algebra and its Applications, 451:231–245, 2014

    Vladimir Nikiforov and Xiying Yuan. More eigenvalue problems of nordhaus-gaddum type.Linear Algebra and its Applications, 451:231–245, 2014

    2014

  9. [17]

    E. A. Nordhaus and J. W. Gaddum. On complementary graphs.American Mathematical Monthly, 63(3):175–177, 1956

    1956

  10. [18]

    E. Nosal. Eigenvalues of graphs. Master’s thesis, University of Calgary, 1970

    1970

  11. [19]

    Upper bound on thek-th eigenvalue of a graph

    Varun Sivashankar. Upper bound on thek-th eigenvalue of a graph. Preprint, arXiv:2603.28738 [math.CO] (2026), 2026

    2026

  12. [20]

    A sharp upper bound on the third adjacency eigenvalue of a graph

    Quanyu Tang. A sharp upper bound on the third adjacency eigenvalue of a graph. Preprint, arXiv:2603.21181 [math.CO] (2026), 2026

    2026

  13. [21]

    Proof of a conjecture of V

    Tam´ as Terpai. Proof of a conjecture of V. Nikiforov.Combinatorica, 31(6):739–754, 2011

    2011

  14. [22]

    Graph Eigenvalues and Projection Constants

    Tanay Wakhare. Graph Eigenvalues and Projection Constants. Preprint, arXiv:2603.29280 [math.CO] (2026), 2026. 15 6 Appendix 6.1 Tables forα i,j Here are the best known bounds forα i,j. i j 1 2 3 4 5 1 4/3 8/7 1.0931 1.0909 1.0678 1.0667 1.0533 1.0526 2 8/7 1/ √ 2 0.6124 0.6000...

    2026

Pith tools

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