pith. sign in

arxiv: 2604.00512 · v2 · submitted 2026-04-01 · 🧮 math.CO

Maximum spectral sum of graphs

Hitesh Kumar , Lele Liu , Hermie Monterde , Shivaramakrishna Pragada , Michael Tait This is my paper

Pith reviewed 2026-05-13 22:42 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C35
keywords spectral graph theoryadjacency eigenvaluesgraph limitsextremal problemsconvex optimizationgraphons
0
0 comments X

The pith

Any graph on n vertices has its two largest adjacency eigenvalues summing to at most 8n/7.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

Load-bearing premise

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

What would settle it

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

Figures

Figures reproduced from arXiv: 2604.00512 by Hermie Monterde, Hitesh Kumar, Lele Liu, Michael Tait, Shivaramakrishna Pragada.

Figure 1
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) f… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

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

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

pith-pipeline@v0.9.0 · 5431 in / 1022 out tokens · 42972 ms · 2026-05-13T22:42:00.067981+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  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

  9. [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

    work page 1990

  10. [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

    work page 1995

  11. [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,

    work page

  12. [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,

    work page

  13. [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

    work page 1974

  14. [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

    work page 2026

  15. [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

    work page 2024

  16. [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

    work page 2012

  17. [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

    work page 2006

  18. [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

    work page 2007

  19. [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

    work page 1988

  20. [20]

    Springer, 2002

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

    work page 2002

  21. [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

    work page 2009

  22. [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

    work page 2006

  23. [23]

    Linear combinations of graph eigenvalues.Electron

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

    work page 2006

  24. [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

    work page 2007

  25. [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

    work page 1962

  26. [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

    work page 2020

  27. [27]

    Graphs with small spectral gap.Electron

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

    work page 2013

  28. [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

    work page 2015

  29. [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 School of Mathematical Sciences, Anhui University, Hefei 230601, P.R. China Hermie M...

    work page 2011

  30. [30]

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

    work page

  31. [31]

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

    work page

  32. [32]

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

    work page

  33. [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

    work page

  34. [34]

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

    work page

  35. [35]

    Verify the coefficient identity exactly usingSymPywith rational arithmetic

    work page

  36. [36]

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

    work page