The Exact Maximum of the Spectral Sum of Graphs

Jing Huang; Wei Wei

The Exact Maximum of the Spectral Sum of Graphs

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

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

Pith's one-line read For every graph with n≥5 vertices, the sum of its two largest adjacency eigenvalues is maximized by a single explicit graph, K_n^*, and the paper pinpoints that graph exactly.

desk verdict Solid, self-contained proof of the exact spectral-sum maximum and uniqueness; resolves the conjectures and deserves a serious referee. read the letter →

arxiv 2607.23081 v1 pith:OAANTVUH submitted 2026-07-25 math.CO

Jing Huang , Wei Wei This is my paper · ORCID

classification math.CO MSC 05C5005C3515A18

keywords spectralsumadjacencyeigenvaluesextremalgraphchainFerrersmatrixKyFanvariationalprincipleincidencerankenergy

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 determines, for every order n≥5, the exact largest possible value of the sum of the two largest adjacency eigenvalues of a graph, and it identifies the unique graph attaining that value. The extremal graph K_n^* is the complement of a disjoint union of a balanced complete bipartite graph and isolated vertices, with the three part sizes determined by n modulo 7. The paper further proves that this maximum never exceeds 8n/7 − 2, with equality exactly when 7 divides n. This settles a conjecture that strengthened a 2010 conjecture and also subsumes a 2008 conjecture, completing the search for the exact finite-order maximum.

What carries the argument

The central object is the weighted Ferrers quotient M_c (and its limit M_0), a (2k+1)×(2k+1) matrix built from block weights √p_i and √q_j and a lower-triangular chain support matrix; it captures the spectrum of the complement J−A(H) of a chain graph H up to additional zeros. The load-bearing identity is Lemma 3.5: for incidence rank k≥2, the sum of pairwise products of the tail eigenvalues λ_3,…,λ_{2k+1} is ≤0. The proof shows that the off-diagonal support graph of M_c^{-1} is a cycle, then uses a sign-variation stability argument on polynomial coefficients to force the second coefficient of the tail polynomial to be nonpositive. This inequality drives a uniform defect that excludes all cha

What would settle it

Compute the eigenvalues of the weighted Ferrers quotient M_c for a concrete incidence-rank-2 chain graph, for example k=2 with p_1=1, p_2=2, q_1=1, q_2=1, c=1, and check whether ∑_{3≤i<j≤5} λ_i λ_j > 0. A single example with positive tail pairwise-product sum would disprove Lemma 3.5. Alternatively, an exhaustive search over all graphs of order 6, 7, or 8 comparing S_2(G) with S_2(K_n^*) would settle the theorem for those orders directly.

Watch

Extended reading notes

Core claim

Theorem 1.1 states that for every graph G of order n≥5, S_2(G) ≤ S_2(K_n^*), with equality if and only if G is isomorphic to K_n^*. The proof begins by choosing a maximizer with as many edges as possible and using Ky Fan's variational principle to convert edge-maximality into a threshold rule that forces the complement to be a chain graph. A new spectral-tail inequality for weighted Ferrers quotients then gives a uniform numerical defect whenever the complement has incidence rank at least two, ruling out all such cases. The complement therefore has incidence rank one, meaning the graph belongs to the family K(n,p,q); exact integer optimization over this family selects K_n^*. A separate equal

Load-bearing premise

The whole reduction to incidence rank one rests on Lemma 3.5, which asserts that for a weighted Ferrers quotient with k≥2 the tail pairwise-product sum ∑_{3≤i<j≤2k+1} λ_i λ_j is ≤0; if that lemma failed, the uniform numerical defect would not follow and the extremal graph could have a complement of higher incidence rank.

Editorial extensions

If this is right

The universal linear bound S_2(G) ≤ 8n/7 − 2 is now known to be sharp exactly when 7 divides n, and the precise finite-order maximum is known for every n≥5.
The unique extremal graph at each order belongs to the three-part family whose complement is a balanced complete bipartite graph plus isolated vertices; no other graph can tie it.
The result extends the earlier connected-graph conjecture to all graphs, adding a uniqueness clause that was previously missing.
A monotonicity lemma shows S_2(K_n^*) strictly increases with n, so the extremal value is a strictly increasing function of the order.
The equality analysis in the threshold rule rules out disconnected maximizers and any maximizer not isomorphic to K_n^*, giving a complete classification.

Reading between the lines

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

The compression of a chain graph to a weighted Ferrers quotient, combined with sign-variation control of the tail, may generalize to partial spectral sums S_k for fixed k>2; the same 7-periodic arithmetic could reappear for S_3.
A direct computational search over all graphs of small orders (e.g., n=6,7,8) comparing S_2 with S_2(K_n^*) would provide an independent, low-cost check of the theorem's core claim before relying on the full proof.
The 4/7 balance between the two nonadjacent parts emerges from a discrete optimization; one might test whether finite-order maxima for other fixed k produce similar rational proportions with periodic residues.
The proof's connectedness step is essential: the equality analysis uses the positivity of the Perron eigenvector of B(G), which fails for disconnected graphs; the paper's separate argument ruling out disconnected maximizers is what makes uniqueness possible.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The paper closes a 15-year-old open problem: it gives the exact maximum of S2 over all graphs of each order n≥5 and proves uniqueness of the extremal graph K_n^*. That is a real result, not just a bound improvement. Prior work had the linear coefficient 8/7 and the connected-graph candidate, but the exact residue-dependent maximum and the equality classification were open. The proof lands cleanly: Ky Fan reduces edge-maximality to a threshold rule, the complement becomes a chain graph, and a new sign-variation argument on weighted Ferrers quotients produces the spectral-tail inequality that kills incidence rank ≥2. The integer optimization in Proposition 2.3 and the analytic bound in Lemma 2.4 are explicit and check out. The equality analysis is also carefully done, with the small connected-graph table handled directly. The authors are honest about what is new: they cite the 2008 and 2010 conjectures and the recent Kumar–Liu–Monterde–Pragada–Tait bound, and do not use any of those as input. There is no circularity and no parameter fitting. The soft spots are minor. Lemma 3.5 is the technical heart, and it is also the densest part of the paper. The displayed formula for C^{-1} has a typographical inconsistency (the entries look off by a scaling), but the zero pattern—which is all the support-graph argument needs—is correct. The perturbation argument that removes zero coefficients is legitimate: it treats the λ_i as independent variables, uses that coefficient signs persist in an open neighborhood, and Lemma 3.4 correctly identifies sign changes with positive roots. I also checked the rank-one interlacing in Lemma 3.7 and the defect inequality; they hold. The only place I would want a bit more exposition is the continuity argument in Theorem 3.6 for c=0, but the eigenvalues do depend continuously and the claim follows. Overall, the paper is coherent on its own terms. The central argument holds up. It deserves a serious referee, and I would expect it to be accepted after a light round of revisions that fix the display typo and perhaps expand the perturbation step in Lemma 3.5 for readability. I would cite this if I worked in extremal spectral graph theory.

Referee Report

0 major / 3 minor

Summary. The paper determines the exact maximum of the spectral sum S_2(G)=λ_1+λ_2 over all simple graphs of order n≥5 and identifies the unique extremal graph K_n^*, defined as the complement of a suitably balanced complete bipartite graph plus isolated vertices. It further proves the sharp bound S_2(K_n^*)≤8n/7−2, with equality exactly when 7 divides n. The authors state that this resolves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, strengthens the Aouchiche–Hansen conjecture, and subsumes the Ebrahimi–Mohar–Nikiforov–Ahmady conjecture. The proof combines Ky Fan's variational principle, a chain-graph reduction, a spectral-tail inequality for weighted Ferrers quotients, exact integer optimization of a three-parameter family, and a separate equality analysis.

Significance. If the proof is correct, the result is a clean finite-order extremal theorem with uniqueness, going beyond the asymptotic coefficient 8/7 and beyond the connected-graph setting. The argument is self-contained and parameter-free: no prior conjectures are used as input, and the extremal candidate is identified by optimizing an explicit family. The technical heart is Lemma 3.5, whose sign-variation and principal-minor machinery I checked with care; the integer optimization table, the τ_n bounds, the support-graph argument, and the uniform defect estimate are internally consistent. The paper does not provide machine-checked code, but the analytic proof is detailed enough for independent verification.

minor comments (3)

[Lemma 3.5] The displayed formula for (C^{-1})_{ij} has the wrong scaling. For C_{ij}=√(p_i q_j) for j≤i, the inverse has reciprocal square roots, e.g. the diagonal entry is 1/√(p_i q_i) and the subdiagonal entry is −1/√(p_{i-1} q_i), not the printed expression. This does not affect the proof, because the subsequent inverse of M_c is justified via W y=x and only the zero pattern of C^{-1} is used for the support graph; nonetheless the displayed formula should be corrected.
[Proposition 2.3] The table of R_{s_n−1} and R_{s_n} is correct but very hard to read in the manuscript because many entries are run together (for example, “2k+ 2k+ 1” and “−5k−2−13k−7”). It should be typeset as a proper table with clear column separators.
[Theorem 3.6] The c=0 limiting argument is compressed: the ordered eigenvalues of M_ε depend continuously on ε, so the tail pair sum passes to the limit. Adding one sentence explaining this continuity would improve readability, especially because the tail sum involves only the eigenvalues after the two largest.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is self-contained and does not use the conjectures it proves as input.

full rationale

I walked the derivation chain from the variational setup through the structural reduction to the final equality analysis. The candidate family K(n,p,q) is optimized in Proposition 2.3 from an explicit polynomial equation, not from the conjectured extremal value; the parameter s_n is derived rather than assumed. The chain-graph reduction (Proposition 2.7) follows from Ky Fan's principle and an edge-maximality tie-break, with no hidden appeal to the conclusion. The technical heart, Lemma 3.5, is proved from the matrix C, its inverse support graph, and an externally cited variation-diminishing theorem of Pinkus; it does not cite the Aouchiche–Hansen or Kumar–Liu–Monterde–Pragada–Tait conjectures. Lemma 3.7 and the uniform defect are consequences of Lemma 3.5, interlacing, and singular-value arguments. The upper bound S2(K_n^*) ≤ 8n/7 - 2 is obtained by direct polynomial evaluation in Lemma 2.4, and the uniqueness argument analyzes equality in the variational threshold without using the claimed uniqueness as an assumption. The cited prior conjectures and the universal bound of [9] appear only as context or as the statement being resolved, not as load-bearing inputs. There are no fitted parameters, no self-citations by the present authors, and no step in which the theorem's conclusion is renamed as a hypothesis. Accordingly, no circularity is present.

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

The proof relies only on standard linear algebra and spectral graph theory. No free parameters are fitted and no ad hoc entities are introduced.

assumptions (5)

standard math Ky Fan's variational principle
Used in Lemma 2.1 to express S_2 as a maximum Rayleigh trace over orthonormal pairs.
standard math Perron–Frobenius theorem and Cauchy interlacing
Used in Lemma 2.5 and in the equality analysis to justify strict spectral radius increase and a positive Perron vector.
standard math Variation-diminishing theorem for totally nonnegative matrices
Used in Lemma 3.1 (from Pinkus [14]) to control sign-change positions in Lemma 3.2.
standard math Descartes' rule of signs
Used in Lemma 3.4 to identify coefficient variation with the number of positive roots.
standard math Schur complement and inertia preservation
Used in Lemma 3.5 to compute the inertia of M_0 and M_c and the signs of principal minors.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Exact Maximum of the Spectral Sum of Graphs." pith.science (2026). https://pith.science/paper/OAANTVUH

@misc{pith2026260723081,
  author       = {Pith},
  title        = {Pith review of: The Exact Maximum of the Spectral Sum of Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OAANTVUH}},
  note         = {Machine review of arXiv:2607.23081}
}

abstract

For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph and isolated vertices, with the sizes of its three parts determined by $n$ modulo $7$. Denoting this graph by $K_n^\star$, we further show that $ S_2(K_n^\star)\leq\frac{8n}{7}-2,$ with equality exactly when $7\mid n$. This proves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, which strengthens the Aouchiche--Hansen 2010 conjecture by extending it from connected graphs to all graphs and by asserting uniqueness of the extremal graph. The result also subsumes the 2008 conjecture of Ebrahimi B., Mohar, Nikiforov, and Ahmady. The proof combines Ky Fan's variational principle with a spectral inequality for weighted Ferrers quotients to reduce the problem to an explicit family whose complements have incidence rank one. Exact integer optimization and a separate equality analysis then yield the maximum and uniqueness.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 2 linked inside Pith

[1]

Aouchiche and P

M. Aouchiche and P. Hansen,A survey of automated conjectures in spectral graph theory, Linear Algebra Appl.432(2010) 2293–2322. 16

2010
[2]

Cvetković and P

D. Cvetković and P. Rowlinson,The largest eigenvalue of a graph: A survey, Linear Multilinear Algebra28(1990) 3–33

1990
[3]

Cvetković and S

D. Cvetković and S. Simić,The second largest eigenvalue of a graph (a survey), Filomat9 (1995) 449–472

1995
[4]

K. C. Das, S. A. Mojallal and S. Sun,On the sum of theklargest eigenvalues of graphs and maximal energy of bipartite graphs, Linear Algebra Appl.569(2019) 175–194

2019
[5]

Ebrahimi B., B

J. Ebrahimi B., B. Mohar, V. Nikiforov and A. S. Ahmady,On the sum of two largest eigen- values of a symmetric matrix, Linear Algebra Appl.429(2008) 2781–2787

2008
[6]

Fan,On a theorem of Weyl concerning eigenvalues of linear transformations I, Proc

K. Fan,On a theorem of Weyl concerning eigenvalues of linear transformations I, Proc. Natl. Acad. Sci. USA35(1949) 652–655

1949
[7]

Gutman,The energy of a graph, Ber

I. Gutman,The energy of a graph, Ber. Math. Stat. Sekt. Forschungsz. Graz103(1978) 1–22

1978
[8]

L. Y. Kolotilina,Upper bounds for the second largest eigenvalue of symmetric nonnegative matrices, J. Math. Sci.191(2013) 75–88

2013

Show all 19 references

[9]

Kumar, L

H. Kumar, L. Liu, H. Monterde, S. Pragada and M. Tait,Maximum spectral sum of graphs, (2026), arXiv:2604.00512

2026 arXiv
[10]

Kumar, B

H. Kumar, B. Mohar, S. Pragada and H. Zhan,Convex combination of first and second eigen- values of trees, (2026), arXiv:2601.10036

2026
[11]

Mohar,On the sum ofklargest eigenvalues of graphs and symmetric matrices, J

B. Mohar,On the sum ofklargest eigenvalues of graphs and symmetric matrices, J. Combin. Theory Ser. B99(2009) 306–313

2009
[12]

Nikiforov,Linear combinations of graph eigenvalues, Electron

V. Nikiforov,Linear combinations of graph eigenvalues, Electron. J. Linear Algebra15(2006) 329–336

2006
[13]

Nikiforov,Beyond graph energy: Norms of graphs and matrices, Linear Algebra Appl.506 (2016) 82–138

V. Nikiforov,Beyond graph energy: Norms of graphs and matrices, Linear Algebra Appl.506 (2016) 82–138

2016
[14]

Pinkus,Totally Positive Matrices, Cambridge Tracts in Mathematics 181, Cambridge Uni- versity Press, Cambridge, 2010

A. Pinkus,Totally Positive Matrices, Cambridge Tracts in Mathematics 181, Cambridge Uni- versity Press, Cambridge, 2010

2010
[15]

Rocha,Partial sum of eigenvalues of random graphs, Appl

I. Rocha,Partial sum of eigenvalues of random graphs, Appl. Math.65(2020) 609–618

2020
[16]

Stanić,Inequalities for Graph Eigenvalues, London Mathematical Society Lecture Note Series 423, Cambridge University Press, Cambridge, 2015

Z. Stanić,Inequalities for Graph Eigenvalues, London Mathematical Society Lecture Note Series 423, Cambridge University Press, Cambridge, 2015

2015
[17]

S. Sun, Y. Min and K. C. Das,Extremal graphs for the sum of two largest eigenvalues, AIMS Math.11(2026) 15028–15036

2026
[18]

S. Sun, Y. Min and K. C. Das,Sum of theklargest eigenvalues of symmetric matrices: Theory and applications, (2026) arXiv:2605.26707

2026 arXiv
[19]

Wang,A simple proof of Descartes’s rule of signs, Amer

X. Wang,A simple proof of Descartes’s rule of signs, Amer. Math. Monthly111(2004) 525– 526. 17

2004

Pith tools

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

[1] [1]

Aouchiche and P

M. Aouchiche and P. Hansen,A survey of automated conjectures in spectral graph theory, Linear Algebra Appl.432(2010) 2293–2322. 16

2010

[2] [2]

Cvetković and P

D. Cvetković and P. Rowlinson,The largest eigenvalue of a graph: A survey, Linear Multilinear Algebra28(1990) 3–33

1990

[3] [3]

Cvetković and S

D. Cvetković and S. Simić,The second largest eigenvalue of a graph (a survey), Filomat9 (1995) 449–472

1995

[4] [4]

K. C. Das, S. A. Mojallal and S. Sun,On the sum of theklargest eigenvalues of graphs and maximal energy of bipartite graphs, Linear Algebra Appl.569(2019) 175–194

2019

[5] [5]

Ebrahimi B., B

J. Ebrahimi B., B. Mohar, V. Nikiforov and A. S. Ahmady,On the sum of two largest eigen- values of a symmetric matrix, Linear Algebra Appl.429(2008) 2781–2787

2008

[6] [6]

Fan,On a theorem of Weyl concerning eigenvalues of linear transformations I, Proc

K. Fan,On a theorem of Weyl concerning eigenvalues of linear transformations I, Proc. Natl. Acad. Sci. USA35(1949) 652–655

1949

[7] [7]

Gutman,The energy of a graph, Ber

I. Gutman,The energy of a graph, Ber. Math. Stat. Sekt. Forschungsz. Graz103(1978) 1–22

1978

[8] [8]

L. Y. Kolotilina,Upper bounds for the second largest eigenvalue of symmetric nonnegative matrices, J. Math. Sci.191(2013) 75–88

2013