Pith. sign in

REVIEW 1 major objections 2 minor 3 cited by

Maximum spectral sum of graphs

T0 review · 1 major / 2 minor · reviewed 2026-05-13 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Any graph on n vertices has its two largest adjacency eigenvalues summing to at most 8n/7.

desk verdict They prove the 2008 spectral sum conjecture with a graphon-plus-convex-geometry argument that looks clean on the surface. read the letter →

arxiv 2604.00512 v2 submitted 2026-04-01 math.CO

Hitesh Kumar , Lele Liu , Hermie Monterde , Shivaramakrishna Pragada , Michael Tait This is my paper · ORCID
classification math.CO MSC 05C5005C35
keywords spectralgraphtheoryadjacencyeigenvalueslimitsextremalproblemsconvexoptimizationgraphons
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 establishes that for any graph G with n vertices the spectral sum λ1(G) + λ2(G) is bounded above by 8n/7. This settles a conjecture posed in 2008. The proof proceeds by lifting the finite-graph problem into the space of graphons, then applying convex-geometry and exterior-algebra arguments to obtain an exact upper bound that is attained by certain explicit constructions. A reader cares because the leading eigenvalues control expansion, connectivity, and mixing rates, so a uniform cap on their sum constrains the global structure of all graphs.

What carries the argument

Graphon formulation of the spectral sum together with convex optimization over the space of symmetric measurable functions that represent the limiting adjacency operators.

What would settle it

A single explicit graph on n vertices whose adjacency matrix has λ1 + λ2 strictly larger than (8/7)n.

Watch

Extended reading notes

Core claim

The spectral sum λ1(G) + λ2(G) satisfies λ1(G) + λ2(G) ≤ (8/7)n for every graph G of order n. The inequality is proved by embedding G into the space of graphons, formulating the sum as a continuous functional, and showing via convex optimization and exterior-algebra identities that the functional never exceeds 8/7 times the measure of the vertex set.

Load-bearing premise

The continuous relaxation via graph limits recovers the exact maximum value attained by finite graphs.

Editorial extensions

If this is right

  • The bound is tight and is achieved by a family of blow-up graphs whose limiting graphon is the optimizer.
  • Any graph whose spectral sum meets or exceeds (8/7)n must be close in cut distance to one of the extremal graphons.
  • The same analytic setup yields upper bounds on other linear combinations of the largest k eigenvalues for fixed k.
  • The methods extend verbatim to weighted graphs and to the normalized Laplacian.

Reading between the lines

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

  • The same graphon-plus-convex-geometry pipeline is likely to resolve analogous conjectures for the sum of the three largest eigenvalues.
  • Because the bound is asymptotic-sharp, it gives precise control on the eigenvalue gap for dense graphs whose second eigenvalue is close to the first.
  • The exterior-algebra step suggests that similar identities may bound higher-order spectral invariants such as the trace of powers of the adjacency matrix.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 2 minor

Summary. The manuscript proves the Ebrahimi-Mohar-Nikiforov-Ahmady conjecture that λ₁(G) + λ₂(G) ≤ (8/7)n for every graph G on n vertices. The argument proceeds by passing to the graphon limit to identify the extremal value in the space of graphons, applies convex geometry and exterior algebra to characterize the optimizer, uses convex optimization to confirm the bound 8/7, and transfers the inequality back to finite graphs.

Significance. Resolution of the 2008 conjecture supplies a sharp linear upper bound on the sum of the two largest adjacency eigenvalues. The combination of graph-limit theory with convex-geometric and optimization tools is of independent methodological interest and may extend to other spectral extremal problems.

major comments (1)
  1. [§4–5] The passage from the graphon maximizer back to finite graphs (presumably §4 or §5) must include an explicit error bound showing that the spectral sum of any finite graph is at most the graphon value plus a term that vanishes relative to n; without this quantitative transfer the inequality for finite n is not yet established.
minor comments (2)
  1. [§2] Notation for the exterior-algebra inner product and the convex body K should be introduced once and used consistently; a short table of symbols would help.
  2. [Theorem 1.1] The statement of the main theorem should explicitly record that equality is attained (or approached) by the complete bipartite graph K_{3,4} or its blow-ups, as implied by the optimization step.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment of the work, and the recommendation for minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: [§4–5] The passage from the graphon maximizer back to finite graphs (presumably §4 or §5) must include an explicit error bound showing that the spectral sum of any finite graph is at most the graphon value plus a term that vanishes relative to n; without this quantitative transfer the inequality for finite n is not yet established.

    Authors: We agree that an explicit quantitative error bound strengthens the transfer argument. While the manuscript invokes standard continuity of the largest eigenvalues under cut-norm convergence of graphons (which already implies that the difference between the finite-graph spectral sum and the graphon value is o(n)), we will add a dedicated lemma in Section 5 that supplies an explicit bound of the form |λ₁(G) + λ₂(G) − (λ₁(W_G) + λ₂(W_G))| ≤ C·d_□(W_G, W)·n, where C is an absolute constant derived from the convex-optimization step and d_□ denotes the cut distance. This will make the passage from the graphon maximizer to finite graphs fully quantitative and self-contained. The revision will be incorporated in the next version. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper establishes the spectral sum bound λ1(G) + λ2(G) ≤ (8/7)n by applying external, independently developed tools from graphon theory, convex geometry, exterior algebra, and convex optimization to obtain the extremal value in the graphon space and transfer it to finite graphs. No load-bearing step reduces by construction to a self-definition, a fitted parameter renamed as a prediction, or a self-citation chain whose validity depends on the present work; the cited frameworks are standard and externally verifiable. The derivation is therefore self-contained against external benchmarks.

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

The proof draws on standard background mathematics without introducing free parameters, ad-hoc axioms, or new postulated entities.

assumptions (1)
  • standard math Standard axioms and theorems of real analysis, linear algebra, and convex geometry
    Invoked throughout the graph-limit and optimization arguments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Maximum spectral sum of graphs." pith.science (2026). https://pith.science/paper/2604.00512

@misc{pith2026260400512,
  author       = {Pith},
  title        = {Pith review of: Maximum spectral sum of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.00512}},
  note         = {Machine review of arXiv:2604.00512}
}
abstract

For a graph $G$ of order $n$, the spectral sum of $G$ is defined to be the sum $\lambda_1(G) + \lambda_2(G)$, where $\lambda_1(G)$ (resp. $\lambda_2(G)$) is the largest (resp. second largest) adjacency eigenvalue of $G$. Ebrahimi, Mohar, Nikiforov and Ahmady (2008) conjectured that the spectral sum \[ \lambda_1(G) + \lambda_2(G)\le \frac{8}{7}n \] for any graph $G$. We prove this conjecture by combining tools from the theory of graph limits, convex geometry, exterior algebra and convex optimization. The techniques developed are of independent interest.

Figures

Figures reproduced from arXiv: 2604.00512 by the authors.

Figure 1
Figure 1. Possibilities for G∗ . The vertex labeled by i in the figure corresponds to Ui . We will prove Lemma 4.9 in a series of claims. We say that two distinct vertices in a graph are true twins if they have the same closed neighbourhoods. We observe that G∗ cannot have true twins. Lemma 4.10. The graph G∗ is true-twin-free. Proof. Suppose Ui , Uj ∈ V (G∗ ) are true twins. Then, by the eigenvalue-equation (4.1) for µ1, we … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

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

  1. The Exact Maximum of the Spectral Sum of Graphs

    math.CO 2026-07 accept novelty 8.0 of 10

    For every n≥5, S_2(G)=λ1+λ2 over n-vertex graphs is maximized uniquely by K_n^⋆, with S_2(K_n^⋆)=n−2+τ_n and S_2(K_n^⋆)≤8n/7−2, equality iff 7|n.

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

  3. Generalized Nordhaus--Gaddum Inequalities for Eigenvalues

    math.CO 2026-07 conditional novelty 7.0 of 10

    The asymptotic maximum of λ₁(G)+λ₂(complement of G) is exactly 8/7 per vertex, with new general bounds for all pairs and a short proof of Terpai's spectral-radius bound.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 3 Pith papers

  1. [1]

    A survey of automated conjectures in spectral graph theory.Linear Algebra Appl., 432(9):2293–2322, 2010

    Mustapha Aouchiche and Pierre Hansen. A survey of automated conjectures in spectral graph theory.Linear Algebra Appl., 432(9):2293–2322, 2010. 21

    work page 2010

  2. [2]

    A survey of Nordhaus-Gaddum type relations.Discrete Appl

    Mustapha Aouchiche and Pierre Hansen. A survey of Nordhaus-Gaddum type relations.Discrete Appl. Math., 161(4-5):466–546, 2013. 1

    work page 2013

  3. [3]

    Pure and Applied Mathematics (New York)

    Jean-Pierre Aubin.Applied Functional Analysis. Pure and Applied Mathematics (New York). Wiley-Interscience, New York, second edition, 2000. With exercises by Bernard Cornet and Jean-Michel Lasry, Translated from the French by Carole Labrousse. 5

    work page 2000

  4. [4]

    Borgs, J

    C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics.Ann. of Math. (2), 176(1):151–219,

    work page

  5. [5]

    Cambridge University Press, Cambridge, 2004

    Stephen Boyd and Lieven Vandenberghe.Convex Optimization. Cambridge University Press, Cambridge, 2004. 13

    work page 2004

  6. [6]

    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. 1, 2

    work page 2022

  7. [7]

    On a conjecture of V

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

    work page 2009

  8. [8]

    Note on the sum of the smallest and largest eigenvalues of a triangle-free graph

    P´ eter Csikv´ ari. Note on the sum of the smallest and largest eigenvalues of a triangle-free graph. Linear Algebra Appl., 650:92–97, 2022. 1 22

    work page 2022

Show all 36 references
  1. [9]

    Cvetkovi´ c and P

    D. Cvetkovi´ c and P. Rowlinson. The largest eigenvalue of a graph: a survey.Linear and Multilinear Algebra, 28(1-2):3–33, 1990. 1

    1990

  2. [10]

    The second largest eigenvalue of a graph (a survey)

    Dragoˇ s Cvetkovi´ c and Slobodan Simi´ c. The second largest eigenvalue of a graph (a survey). Number 9, pages 449–472. 1995. Algebra, logic & discrete mathematics (Niˇ s, 1995). 1

    1995

  3. [11]

    On the sum of the k largest eigenvalues of graphs and maximal energy of bipartite graphs.Linear Algebra Appl., 569:175–194,

    Kinkar Chandra Das, Seyed Ahmad Mojallal, and Shaowei Sun. On the sum of the k largest eigenvalues of graphs and maximal energy of bipartite graphs.Linear Algebra Appl., 569:175–194,

  4. [12]

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

    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,

  5. [13]

    Additive compound matrices and an inequality for eigenvalues of symmetric- stochastic matrices.Czechoslovak Math

    Miroslav Fiedler. Additive compound matrices and an inequality for eigenvalues of symmetric- stochastic matrices.Czechoslovak Math. J., 24(3):392–402, 1974. 20

    1974

  6. [14]

    Convex combi- nation of first and second eigenvalues of trees, 2026

    Hitesh Kumar, Bojan Mohar, Shivaramakrishna Pragada, and Hanmeng Zhan. Convex combi- nation of first and second eigenvalues of trees, 2026. 21

    2026

  7. [15]

    Graph limits and spectral extremal problems for graphs.SIAM J

    Lele Liu. Graph limits and spectral extremal problems for graphs.SIAM J. Discrete Math., 38(1):590–608, 2024. 2, 6

    2024

  8. [16]

    American Mathematical Society, Providence, RI, 2012

    L´ aszl´ o Lov´ asz.Large networks and graph limits, volume 60 ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012. 4

    2012

  9. [17]

    Limits of dense graph sequences.J

    L´ aszl´ o Lov´ asz and Bal´ azs Szegedy. Limits of dense graph sequences.J. Combin. Theory Ser. B, 96(6):933–957, 2006. 4

    2006

  10. [18]

    Szemer´ edi’s lemma for the analyst.Geom

    L´ aszl´ o Lov´ asz and Bal´ azs Szegedy. Szemer´ edi’s lemma for the analyst.Geom. Funct. Anal., 17(1):252–270, 2007. 4

    2007

  11. [19]

    Chelsea Publishing Co., New York, third edition, 1988

    Saunders Mac Lane and Garrett Birkhoff.Algebra. Chelsea Publishing Co., New York, third edition, 1988. 19

    1988

  12. [20]

    Springer, 2002

    Jiˇ r´ ı Matouˇ sek.Lectures on Discrete Geometry, volume 212 ofGraduate Texts in Mathematics. Springer, 2002. 13

    2002

  13. [21]

    On the sum of k largest eigenvalues of graphs and symmetric matrices.J

    Bojan Mohar. On the sum of k largest eigenvalues of graphs and symmetric matrices.J. Combin. Theory Ser. B, 99:306–313, 2009. 1

    2009

  14. [22]

    Eigenvalues and degree deviation in graphs.Linear Algebra Appl., 414:347– 360, 2006

    Vladimir Nikiforov. Eigenvalues and degree deviation in graphs.Linear Algebra Appl., 414:347– 360, 2006. 3

    2006

  15. [23]

    Linear combinations of graph eigenvalues.Electron

    Vladimir Nikiforov. Linear combinations of graph eigenvalues.Electron. J. Linear Algebra, 15:329–336, 2006. 2 23

    2006

  16. [24]

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

    2007

  17. [25]

    XXXVIII ofAmerican Mathematical Society Colloquium Publications

    Oystein Ore.Theory of Graphs, volume Vol. XXXVIII ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 1962. 5

    1962

  18. [26]

    Parrilo and R.R

    P.A. Parrilo and R.R. Thomas.Sum of Squares: Theory and Applications. Proceedings of Symposia in Applied Mathematics. American Mathematical Society, 2020. 20

    2020

  19. [27]

    Graphs with small spectral gap.Electron

    Zoran Stani´ c. Graphs with small spectral gap.Electron. J. Linear Algebra, 26:417–432, 2013. 1

    2013

  20. [28]

    Cambridge University Press, Cambridge, 2015

    Zoran Stani´ c.Inequalities for Graph Eigenvalues, volume 423 ofLondon Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2015. 1

    2015

  21. [29]

    Proof of a conjecture of V

    Tam´ as Terpai. Proof of a conjecture of V. Nikiforov.Combinatorica, 31(6):739–754, 2011. 1, 2, 6 Hitesh Kumar, Email:hitesh.kumar.math@gmail.com, hitesh kumar@sfu.ca Dept. of Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada Lele Liu, Email:liu@ahu.edu.cn Scho...

    2011

  22. [30]

    Set up the coefficient equations (5.5) as a semidefinite feasibility problem in the unknown blocksQ ab andT, together with the constraintQ⪰0

  23. [31]

    Solve this feasibility problem numerically in CVXPY using the solver SCS, to a prescribed error tolerance, obtaining numerical matricesQ num andT num

  24. [32]

    Symmetrize the numerical solution by replacing Qnum ← 1 2 Qnum + (Qnum)T , T num ← 1 2 T num + (T num)T . 25

  25. [33]

    More precisely, selected entries of Qnum and T num are replaced by nearby rational numbers of bounded denominator, and then assembled into candidate exact matricesQ rat andT rat

    Convert the numerical matrices into exact rational matrices using SymPy. More precisely, selected entries of Qnum and T num are replaced by nearby rational numbers of bounded denominator, and then assembled into candidate exact matricesQ rat andT rat

  26. [34]

    Reconstruct the remaining entries of Qrat exactly from the linear coefficient equations, so that the polynomial identity holds exactly overQ

  27. [35]

    Verify the coefficient identity exactly usingSymPywith rational arithmetic

  28. [36]

    Verify Qrat ⪰ 0 exactly by checking a rank one decomposition of Qrat over Q, again using SymPy. 26

Pith tools

Reviewed May 13, 2026 · model on record in the stance chip above.