Pith. sign in

REVIEW 4 major objections 5 minor 2 cited by

Strengthened upper bound on the third eigenvalue of graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · 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 the supremum of the third eigenvalue ratio λ3/n over all n-vertex graphs is strictly smaller than the classical threshold 1/(2√2).

desk verdict A serious proof of a Nikiforov claim, with one load-bearing numerical gap that a referee can ask to be fixed. read the letter →

arxiv 2501.07494 v1 pith:EN2B5TSZ submitted 2025-01-13 math.CO

Sida Li This is my paper · ORCID
classification math.CO MSC 05C5005C35
keywords thirdeigenvalueextremalgrapheigenvaluesadjacencyspectrumoperationeigenvectortypescliqueandchromaticnumberspectralgap
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 proves a long-claimed strengthening of the extremal bound for the k-th largest adjacency eigenvalue of a graph, in the first open case k=3. It shows there is a fixed gap ε3>0 such that λ3(G)/n < 1/(2√2) − ε3 for every graph G on n vertices, where 1/(2√2) is the bound obtained from arithmetic-mean/quadratic-mean comparison. The proof works indirectly: it studies the sum of the two smallest eigenvalues λ_{n−1}+λ_n, whose infimum is shown to lie strictly above −√2/2, and then converts this into the bound on λ3 via Weyl's inequality. Along the way the paper introduces a new graph operation, the ∗ operation, that restructures any minimising graph into one with clique number at most 3 and chromatic number at most 4, and reduces the hypothetical worst case to a family of n/2-regular invariant graphs whose spectral analysis can be carried out by explicit eigenvector inequalities.

What carries the argument

The central object is Operation ∗: given a graph G and an orthonormal pair of eigenvectors x,y for λ_{n−1}(G), λ_n(G), define G* by i∼j iff x_i x_j + y_i y_j < 0. The spectral minimisation principle in Theorem 2.2 shows λ_{n−1}(G*)+λ_n(G*) ≤ λ_{n−1}(G)+λ_n(G), so a minimal graph can be assumed invariant, G=G*. Invariance gives a circular-arc structure (Theorem 2.4), clique number ≤3 and chromatic number ≤4. For the critical n/2-regular invariant case the adjacency matrix splits as [[Q, J−Q],[J−Q, Q]], and the spectrum of G reduces to the spectra of J and 2Q−J; the eigenvectors of 2Q−J are shown to come in two monotone Types (front-increasing-then-decreasing nonnegative, and always-decreasing), from which a series of boundary inequalities defines a feasible region in (a,c,ν)-space. The proof of Theorem 3.7 traces the minimum of ν1+ν2 across phases of these inequalities and rules out ν1+ν2=−√2.

What would settle it

Evaluate the polynomial P(ν1)=$ν1^{3}$+$ν1^{2}$+4(T−S)ν1+4(√T(T+S)−S) from Intersection IIa with interval arithmetic over the stated ranges T∈[1/9,1/8], S∈[T+7/400,1/4] and check that P(−0.7)>0; likewise verify P(−√2+2√T)>0.001 for the second polynomial at the prescribed S-endpoints over T∈[0.055,1/8]. A single counterexample to either inequality, or an explicit sequence of n/2-regular invariant graphs with (λ_{n−1}+λ_n)/n approaching −√2/2, would settle the claim either way.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: there exists ε>0 such that inf{ (λ_{n−1}(G)+λ_n(G))/n : |V(G)|=n≥3 } > −√2/2 + ε. Consequently, via the inequality λ3+λ_{n−1} ≤ λ2(K_n) = −1, the third eigenvalue ratio is bounded away from 1/(2√2). The proof eliminates the equality case of the elementary AM-QM bound λ_{n−1}^2 + $λ_n^{2}$ ≤ $n^{2}$/4: a sequence of graphs with the sum converging to −√2/2 would force a specific limit state — parameters X=Z=1/2, T=1/8 and eigenvector components a=c=√2/2 — and the paper shows that this state cannot be approached simultaneously by the two structural types of eigenvectors that the invariant graphs admit. The near-equality graphs are then shown to be close, up to o($n^{2}$) edge changes, to n/2-regular graphs invariant under the new operation, so the contradiction transfers to the general problem.

Load-bearing premise

The proof that the infimum is strictly above −√2/2 depends on two numerical inequalities in Stage 4 of Theorem 3.7 — that the cubic P is positive at −0.7 and that at −√2+2√T it is bounded below by 0.001 — which are asserted from direct computation rather than proved or machine-verified; if either sign were wrong, the contradiction forcing strict inequality would fail.

Editorial extensions

If this is right

  • There is a constant ε3>0 such that every n-vertex graph satisfies λ3(G)/n < 1/(2√2) − ε3, settling the long-claimed strengthening for k=3.
  • The infimum of (λ_{n−1}+λ_n)/n over all graphs of order n is bounded below by −√2/2 + ε, so the trivial AM-QM bound is not tight.
  • The same argument gives c_{−2} < 1/(2√2) − ε3, a strengthened upper bound on the second smallest eigenvalue in absolute value.
  • Conjecture 5.1, that λ_{n−1}+λ_n ≥ −2n/3, is verified for all graphs on at most 9 vertices and is compatible with the new bound; if true it would imply c3 = 1/3.

Reading between the lines

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

  • The direct numerical checks in Stage 4 (positivity of P(−0.7) and the 0.001 lower bound for P(−√2+2√T)) could be replaced by rigorous interval arithmetic or a computer-certified proof, so those two evaluations are the first place to audit the argument.
  • The same ∗_k generalisation in Subsection 2.2 may give analogous strengthened bounds for higher k, although the paper notes that for k≥3 there is no canonical ordering of the vectors, which currently blocks that route.
  • The equality-state analysis suggests that any minimising sequence, if it existed, would concentrate on block-type constructions; one testable extension is to check whether explicit pivalous or circulant blow-up families achieve the −2/3 infimum in the limit rather than −√2/2.
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

4 major / 5 minor

Summary. The paper proves a strengthened upper bound for the third eigenvalue of a graph, namely that c3 is strictly below the classical bound 1/(2√2). The strategy is to study the closely related quantity λ_{n-1}+λ_n and to show a uniform spectral gap: inf(λ_{n-1}+λ_n)/n > −√2/2 + ε. The proof introduces a new graph operation G*, shows that minimising graphs can be assumed invariant under it, derives structural restrictions (ω ≤ 3, χ ≤ 4), then reduces a hypothetical worst-case sequence to n/2-regular invariant graphs. For those graphs the paper develops a lengthy finite-parameter extremal argument with two eigenvector types and rules out the limiting equality case, completing the proof of Theorems 3.1, 1.2, and 1.1.

Significance. If the argument is correct, this is a significant result: it resolves Nikiforov's omitted case k = 3 and gives the first rigorous proof of a uniform gap below 1/(2√2) for c3. The new operation G* is natural and the structural theorems (clique number ≤ 3, chromatic number ≤ 4, and the canonical front/middle/back decomposition) are elegant and appear to be correct. The proof is self-contained in the sense that no numerical constants are fitted and no external computational evidence is needed at the level of the main theorem. However, the paper is not yet a complete proof: several load-bearing inequalities, especially in Stage 4 of Theorem 3.7, are asserted on the basis of ad hoc Desmos computations rather than proved or certified, and the phase analysis in Stage 5 is similarly visual and informal. These gaps are local in the sense that they can likely be repaired with written-out polynomial bounds or interval arithmetic, but as submitted they prevent the central claim from being fully verified.

major comments (4)
  1. [§3.1, Stage 4 (Intersections IIa and IIb)] The exclusion of the equality state ν1+ν2 = −√2 depends on numerical assertions that are never proved or certified. In Intersection IIa the proof states 'Directly computing with Desmos, we get that as functions of T, P(−0.7) is always positive, contradiction', and in Intersection IIb it states that P(−√2+2√T) 'is bounded below by a positive number (0.001 suffices)' while the upper endpoint has 'the only root at T=1/8'. These are claims about cubic polynomials in parameters T and S, but the polynomials are not written out, no analytic proof is given, and no code or interval-arithmetic certificate is supplied. These checks are load-bearing: they are exactly what forces ν1 > −0.7 in IIa and what leaves only X=Z=1/2, T=1/8 in IIb. If either check is false or too coarse, the contradiction in Stage 4 fails and Theorems 3.7, 3.1, and 1.2 are unsupported. This is the central gap and must be closed by a rigorous proof or a machine-checkable certificate.
  2. [§3.1, Stage 2 (Smoothing inequalities)] The displayed smoothing inequalities are obtained by an unproved extremal heuristic. The text says that the minimum of Σ d_a x_a under fixed t and A occurs when d_a = n−k−l for the first t/(n−k−l) indices and x_a = x_b for the remaining indices, 'by considering the continuous generalisation'. This is not a proof, and the resulting inequalities are used in Intersections I, II, IIa and IIb to restrict the feasible region. Since the smoothing inequalities are load-bearing for the strict-gap argument, a rigorous derivation of these bounds must be supplied.
  3. [§3.1, Stage 5 and the final casework of Theorem 3.7] The phase analysis is presented largely through visual Desmos plots and informal assertions about hyperbola branches. For example, the proof says 'we claim that smoothing(c) eliminates anything below the lower intersection' and 'the feasible region lies inside the region bounded by the two intersection points of the branches', but no analytic verification of the relevant convexity, monotonicity, and branch-selection facts is provided. These phase claims determine which of Intersections Ia, Ib, IIa, IIb is active, so they are not merely illustrative. The forward reference 'For reasons justified in Stage 5, we require the second root of this cubic' only compounds the problem, since Stage 5 itself is not formal. A complete proof needs explicit inequalities proving the claimed shape of the feasible regions in each phase.
  4. [§3.1, final paragraph before Claims 3.8 and 3.9] The transition from the equality-state analysis to the asymptotic contradiction relies on the statement that, by continuity, the matrices get arbitrarily close to the equality state. This presupposes a compactness or subsequence argument for the normalized parameters X, Y, Z, T, a, c, and ν as n grows. The later claims do use averages, but they do not directly prove the needed parameter convergence. This is a more localized gap than the numerical checks, but it is still part of the strict-gap argument and should be made precise.
minor comments (5)
  1. [Corollary 2.9] The proof of Corollary 2.9 cites Leonida and Li [7], which is an unpublished preprint. If this result is used only as motivation and for examples, this should be stated explicitly; if it is needed in the proof, the argument should be made self-contained or the citation should be to a published source.
  2. [Theorem 2.4] The statement that the neighbours of vertex i are {a_i, a_i+1, ..., b_i} mod n is ambiguous; please specify the circular-interval convention and the intended ranges of a_i and b_i.
  3. [§3.1, Stage 4] In the sentence 'mean(c) and smoothing(c) intersect until T = 1/8, similarly with mean(c) and smoothing(c)', the second clause should presumably refer to mean(a) and smoothing(a); please correct this typo.
  4. [Throughout §3.1] The proof of Theorem 3.7 is very long but has almost no equation numbering; references such as 'smoothing(c)' and 'Extrema' would be much easier to check if the key displayed formulas and inequalities were numbered.
  5. [Theorem 3.2] The phrase 'the complement of Q is in a perfect elimination ordering' is used before its connection to Theorem 2.4 is explained; a short definition or reference would improve readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the central derivation is self-contained and does not reduce to its inputs.

full rationale

The central claim, Theorem 1.2, is proved by a self-contained extremal argument. The operation G* is introduced via the variational characterization of the two smallest eigenvalues and is used only to impose structural restrictions, not to encode the target bound. The reduction to n/2-regular invariant graphs proceeds through explicit matrix block structure and eigenvector component inequalities, with no fitted parameter renamed as a prediction. The exclusion of the limiting value -sqrt(2)/2 in Theorem 3.7 is obtained by analyzing intersections of inequalities and ruling out the equality state X = Z = 1/2, T = 1/8 through a further contradiction between Type 1 and Type 2 eigenvectors. Section 4 reduces a hypothetical worst-case sequence to this constrained family using o(n^2) edge modifications, which preserves the spectrum up to o(n); this is a structural reduction, not a circular redefinition. The self-citation to Leonida and Li [7] appears in Corollary 2.9 and as motivation, but it is not load-bearing for Theorem 3.1 or Theorem 1.2: those proofs do not rely on the pivalous-graph eigenvalue results. Nikiforov's prior bounds are used as baselines and as external facts, not as the strengthened conclusion being derived. The Desmos-based numerical checks in Stage 4 are a verification gap and a correctness risk, not a circularity: they assert inequalities for explicit cubic polynomials rather than importing the target result. Overall, the derivation chain is independent of its conclusions, so the circularity score is minimal.

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

The proof introduces no fitted constants. It relies on standard tools (Weyl, Chebyshev, spectral theorem) and on several results from prior work, notably Nikiforov's extremal bounds and Leonida-Li's unpublished analysis of large-λ3 graphs. The self-cited Leonida-Li material is used for structural corollaries (2.9) and motivation, not for the main contradiction. The central derivation is not circular, but the numerical checks in Stage 4 are unproved.

assumptions (7)
  • standard math Weyl's inequalities for Hermitian matrices
    Used to derive Theorem 1.1 from Theorem 1.2 and to bound eigenvalue changes under o(n^2) edge perturbations in Section 4 (Claims 4.2, 4.4).
  • domain assumption Nikiforov's bound λ_{n-1}^2 + λ_n^2 ≤ n^2/4, equivalently λ_{n-1}+λ_n ≥ -√2 n/2
    Baseline inequality in the introduction; the equality cases motivate the n/2-regular reduction in Claim 4.2.
  • domain assumption Nikiforov's degree-regularity bound s(G)=Σ|d(i)-2e(G)/n|=o(n^2) when λ_1 is close to n/2
    Used in Claim 4.2 to show the minimizer is close to n/2-regular; this is an external theorem from Nikiforov [10].
  • standard math Chebyshev sum inequality for monotone sequences
    Used in Stage 2 of Theorem 3.7 to derive mean inequalities for Type 1 and Type 2 eigenvectors.
  • standard math Strong perfect graph theorem (Chudnovsky et al., 2006)
    Invoked only as an alternative route in Theorem 2.7, not for the main theorem.
  • standard math Rankin's packing lemma (Lemma 8 of Rankin, 1947)
    Used in Theorem 2.15, a non-central generalization of the operation.
  • domain assumption Results from Leonida-Li [7] on abelian Cayley graphs and pivalous graphs
    Used in Corollary 2.9 and for motivation; the cited manuscript is unpublished and the results are not reused in the proof of Theorem 1.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strengthened upper bound on the third eigenvalue of graphs." pith.science (2026). https://pith.science/paper/EN2B5TSZ

@misc{pith2026250107494,
  author       = {Pith},
  title        = {Pith review of: Strengthened upper bound on the third eigenvalue of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EN2B5TSZ}},
  note         = {Machine review of arXiv:2501.07494}
}
abstract

Let $G$ be a graph on $n \ge 3$ vertices, whose adjacency matrix has eigenvalues $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$. The problem of bounding $\lambda_k$ in terms of $n$ was first proposed by Hong and was studied by Nikiforov, who demonstrated strong upper and lower bounds for arbitrary $k$. Nikiforov also claimed a strengthened upper bound for $k \ge 3$, namely that $\frac{\lambda_k}{n} < \frac{1}{2\sqrt{k-1}} - \varepsilon_k$ for some positive $\varepsilon_k$, but omitted the proof due to its length. In this paper, we give a proof of this bound for $k = 3$. We achieve this by instead looking at $\lambda_{n-1} + \lambda_n$ and introducing a new graph operation which provides structure to minimising graphs, including $\omega \le 3$ and $\chi \le 4$. Then we reduce the hypothetical worst case to a graph that is $n/2$-regular and invariant under said operation. By considering a series of inequalities on the restricted eigenvector components, we prove that a sequence of graphs with $\frac{\lambda_{n-1} + \lambda_n}{n}$ converging to $-\frac{\sqrt{2}}{2}$ cannot exist.

Figures

Figures reproduced from arXiv: 2501.07494 by the authors.

Figure 1
Figure 1. Invariant families. H5,2 on the left, P i21 on the right. Theorem 2.10. Ha,b is invariant under G → G → G ∗ → G ∗ . Proof. We claim that for ω = exp(πi/3), z = s 2 3(a + b) (1, . . . , 1 | {z } a , ω, . . . , ω | {z } b , ω2 , . . . , ω2 | {z } a , ω3 , . . . , ω3 | {z } b , ω4 , . . . , ω4 | {z } a , ω5 , . . . , ω5 | {z } b ) is an eigenvector of Ha,b of eigenvalue −(a + b). Indeed, note that ω k is adjacent to a·… view at source ↗
Figure 2
Figure 2. From left to right: G4, A(G4), the resultant R 2 vectors, Q. In anti-clockwise order, the vectors we obtain are approximately: v1 = (0.43, 0), v2 = (0.43, 0), v3 = (0.26, 0.5), v4 = (−0.26, 0.5), v5 = (−0.43, 0), v6 = (−0.43, 0), v7 = (−0.26, −0.5), v8 = (0.26, −0.5), hence the last two eigenvectors of 2Q−J are x = (0.43, 0.43, 0.26, −0.26) of Type 2 and y = (0, 0, 0.5, 0.5) of Type 1. These correspond to eigenvalue… view at source ↗
Figure 3
Figure 3. From left to right: G6, A(G6), the resultant R 2 vectors, Q. Here, the last two eigenvectors of 2Q − J are x = (0.37, 0.37, 0.30, 0.16, −0.16, −0.30) and y = (0, 0, 0.26, 0.43, 0.43, 0.26), with front {v1, v2, v3}, middle {v4}, back {v5, v6}. The eigenvalues are ≈ −4.4940 and ≈ −3.2361 respectively, giving λn−1+λn n ≈ −0.6442. 3.1 Proof of Theorem 3.1 The spectrum of J is n/2, 0, . . . , 0, all non-negative eigenval… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Visually demonstrating the inequalities for [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Phase 1 visualised, with T = 0.05. Overall and close-up view. We have that smoothing(c) and mean(c) are increasing hyperbolas in c. Note that c + 1 > 0 hence the region 0 ≤ c ≤ 1 from border(c) doesn’t intersect with the upper branch of smoothing(c), and hence the feas…
Figure 6
Figure 6. Figure 6: Phase 2 visualised, with T = 0.10. Overall and close-up view. T ≥ Z(1−Z) 2 hence 2 T Z − X ≥ 1 − Z − X ≥ 0. Now only the upper branch of mean(a) intersects with a ≥ 0 since a ≥ 0 ≥ 1 − 2T XZ implies Za + 2T X − Z ≥ 0, and the feasible region must lie outside it. Simila…
Figure 7
Figure 7. Figure 7: Phase 3 visualised, with T = 0.12. Overall and close-up view. Since a + 1 > 0 and c + 1 > 0, we only have the upper branches of both hyperbolas intersecting with the border conditions a, c ≥ 0, and the feasible region lies above (or inside) both. Thus, it must lie insi…
Figure 8
Figure 8. Figure 8: Type 1 (left) and Type 2 (right) equality cases for [PITH_FULL_IMAGE:figures/full_fig_p024_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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.

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

13 extracted references · 11 canonical work pages · cited by 2 Pith papers

  1. [1]

    Efficient testing of large graphs

    Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs. Combinatorica, 20(4):451–476, 2000

    2000

  2. [2]

    Borgs, J.T

    C. Borgs, J.T. Chayes, L. Lov´ asz, V.T. S´ os, and K. Vesztergombi. Convergent se- quences of dense graphs I: Subgraph frequencies, metric properties and testing. Ad- vances in Mathematics , 219(6):1801–1851, 2008

    work page 2008

  3. [3]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of Mathematics , 164(1):51–229, 2006

    2006

  4. [4]

    On a conjecture of V

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

    work page 2009

  5. [5]

    On the sum of two largest eigenvalues of a symmetric matrix

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

    work page 2008

  6. [6]

    Bounds of eigenvalues of graphs

    Yuan Hong. Bounds of eigenvalues of graphs. Discrete Mathematics , 123(1):65–74, 1993

    work page 1993

  7. [7]

    On graphs with large third eigenvalue, 2025

    Giacomo Leonida and Sida Li. On graphs with large third eigenvalue, 2025

    work page 2025

  8. [8]

    Improved lower bounds on the extrema of eigenvalues of graphs

    William Linz. Improved lower bounds on the extrema of eigenvalues of graphs. Graphs and Combinatorics , 39, 07 2023

    work page 2023

Show all 13 references
  1. [9]

    Linear combinations of graph eigenvalues

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

    2006

  2. [10]

    Eigenvalue problems of Nordhaus–Gaddum type

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

    2007

  3. [11]

    Extrema of graph eigenvalues

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

    2015

  4. [12]

    R. A. Rankin. On the closest packing of spheres in n dimensions. Annals of Mathe- matics, 48(4):1062–1081, 1947

    1947

  5. [13]

    Proof of a conjecture of V

    Tam´ as Terpai. Proof of a conjecture of V. Nikiforov.Combinatorica, 31:739–754, 2011. Appendix We deal with the block construction mentioned in the proof of Theorem 3.7 and prove that C[t] 6 is optimal over all closed vertex multiplications of C6 by [a, b, c, a, b, c]. Theore...

    2011

Pith tools

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