Pith. sign in

REVIEW 1 major objections 3 minor 38 references

A positive square-energy strengthening of Tur\'an's theorem

T0 review · 1 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 on n vertices with clique number ω, the square root of the sum of squared positive adjacency eigenvalues is at most (1 − 1/ω)n, settling a conjecture stated in 2018.

desk verdict The paper resolves Elphick–Wocjan with a genuinely new Caro–Wei/Motzkin–Straus argument, but Theorem 1.3 as printed contains a reciprocal-constant typo that blocks the chain until fixed. read the letter →

arxiv 2607.18044 v1 pith:VMSEIFY3 submitted 2026-07-20 math.CO

Yinchen Liu , Quanyu Tang , Shengtong Zhang This is my paper · ORCID
classification math.CO MSC 05C5005C3515A42
keywords positivesquareenergycliquenumberspectralTurántheoremdoublynonnegativematricesMotzkin–StrausinequalityCaro–Weigreedyprocessrandompartitionmachine-verifiedproof
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 a sharp spectral analogue of Turán's theorem: for every n-vertex graph with clique number ω, the sum s⁺ of squares of the positive adjacency eigenvalues satisfies √s⁺ ≤ (1 − 1/ω)n. This confirms a conjecture that had been open since 2018 and strengthens Wilf's classical bound on the largest eigenvalue. The proof reduces the spectral statement through a chain of increasingly combinatorial inequalities, ending at a local probabilistic estimate for the random greedy Caro–Wei partition. Along the way it yields a weighted Turán stability theorem with an explicit random partition, and the full proof has been machine-checked.

What carries the argument

The proof is carried by the Caro–Wei random greedy process on the complement graph, which yields a random partition of the vertex set into at most ω parts because the chosen pivots form a clique. The load-bearing estimate is the local inverse-probability inequality (Lemma 1.6 / Theorem 2.3): for every vertex v, 1/p_G(v) + Σ_{u∈N_G(v)} 1/q_G(vu) ≤ n, where p_G(v) is the probability that v is chosen as a pivot and q_G(vu) is the probability that the edge uv lies between two different parts. The lemma is proved by induction via first-pivot recurrences together with an AM–GM inequality on reciprocal row sums. Summing this local estimate yields a harmonic bound on the edges, which implies a weigh

What would settle it

Search, for all graphs on at most nine vertices, for a vertex v with 1/p(v) + Σ_{u∈N(v)} 1/q(vu) > n; finding one would falsify the key lemma and thus the theorem as proved.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 1.2: for every graph on n≥1 vertices with clique number ω, the quantity √s⁺(G) is bounded by (1−1/ω)n, where s⁺(G) is the sum of the squares of the positive eigenvalues of the adjacency matrix. This is equivalent to the ratio n/(n−√s⁺(G)) being at most ω, the form originally conjectured. The bound is tight: when ω divides n, the complete ω-partite Turán graph has exactly one positive eigenvalue equal to (1−1/ω)n, so equality holds.

Load-bearing premise

The whole proof rests on the local inverse-probability estimate (Lemma 1.6) that for every vertex 1/p(v) + Σ_{u∈N(v)} 1/q(vu) ≤ n, so if any graph violates this inequality the weighted Turán bound, the doubly nonnegative Motzkin–Straus lemma, and the spectral theorem all collapse; separately, as printed, Theorem 1.3 and (3.3) need the constant corrected from 2(1−1/ω)/n² to 2ω/((ω−1)n²) for Lemma 1.4's proof to work as written.

Editorial extensions

If this is right

  • Resolves the square-energy conjecture posed in 2018: n/(n−√s⁺(G)) ≤ ω(G) for every graph.
  • Strengthens Wilf's spectral Turán theorem, since √s⁺(G) ≥ λ₁(G).
  • Gives a weighted Turán stability statement (Theorem 1.3): an explicit random ω-partition with a guaranteed lower bound on separated mass for arbitrary nonnegative edge weights, valid for all graphs and computable in polynomial time.
  • Provides a constructive, probability-based path from spectral data to clique number, potentially useful for algorithms that estimate clique number from eigenvalues.
  • The entire theorem is formally machine-verified, so the combinatorial and spectral reasoning is checkable step by step.

Reading between the lines

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

  • Because the local harmonic inequality holds with equality for all complete multipartite graphs, a natural next step is a stability version: are complete multipartite graphs the only extremal cases, and if so, how much can a graph deviate before the bound becomes strict?
  • The Caro–Wei partition is exactly the clustering produced by the random-pivot correlation-clustering algorithm, so the harmonic estimate could translate into approximation guarantees for correlation clustering on dense graphs.
  • The doubly-nonnegative relaxation is flexible: replacing the entrywise square by entrywise p-th powers (for suitable p) might yield analogous spectral bounds for p-energies, provided the resulting matrix remains doubly nonnegative.
  • One could test computationally, on all graphs up to a modest size, whether equality in the local estimate forces complete multipartiteness; a counterexample would refine the extremal analysis of the theorem.
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.

Referee Report

1 major / 3 minor

Summary. The paper proves that for every graph G on n vertices with clique number ω, √s⁺(G) ≤ (1−1/ω)n, where s⁺(G) is the sum of squared positive adjacency eigenvalues. This resolves Conjecture 1.1 of Elphick and Wocjan and strengthens Wilf's spectral Turán theorem. The proof proceeds by a chain of reductions: from a local inverse-probability estimate for the Caro–Wei random greedy partition (Lemma 1.6 / Theorem 2.3), to a weighted Turán-type lower bound on expected separated mass (Theorem 1.3), to a doubly nonnegative Motzkin–Straus inequality (Lemma 1.4), and finally to the spectral square-energy bound via the Schur product theorem applied to the positive part A₊ of the adjacency matrix. The paper also states that the proof of Theorem 1.2 has been formally verified in Lean 4. The central issue is that the displayed constant in Theorem 1.3 and Eq. (3.3) is weaker than the constant actually proved, and as printed it is insufficient for the proof of Lemma 1.4. The proof itself supplies the stronger constant needed; this is a correctable but load-bearing transcription error.

Significance. If the constant issue is corrected, this is a substantial result: it settles a named conjecture in spectral graph theory, strengthens Wilf's theorem, and introduces a remarkably clean local estimate for the Caro–Wei process. The doubly nonnegative relaxation and the use of the Schur product theorem provide a coherent and largely self-contained proof strategy. The claimed Lean formalization is an important reproducibility asset, although it needs to be matched to the corrected statements. The local harmonic inequality (1.5), with equality for complete multipartite graphs, is a striking contribution in its own right and is likely to find further applications.

major comments (1)
  1. [Theorem 1.3 and Eq. (3.3)] The displayed lower bound is too weak by a factor ω²/(ω−1)². The proof of Theorem 1.3 actually derives (Σ√a_e)² ≤ (1/2)(1−1/ω)n² · E W_P(a), which rearranges to E W_P(a) ≥ 2ω/((ω−1)n²)·(Σ√a_e)². The printed statement has 2(1−1/ω)/n² instead. This is load-bearing: in the proof of Lemma 1.4, combining (3.2) with the printed (3.3) gives only (Σ√M_uv)² ≤ n² 1ᵀM1/4, missing the factor (1−1/ω)², so the proof of Lemma 1.4 fails as written. The subsequent remark that a_e≡1 yields an ω-partite subgraph with at least 2m²/((1−1/ω)n²) edges already uses the corrected constant. Please update the statement of Theorem 1.3, Eq. (3.3), and the overview to the stronger constant proved in the argument.
minor comments (3)
  1. [Section 2, proof of Theorem 2.3] The notation q_{x,u} is currently ambiguous: it should be defined explicitly as q_{G_x}(vu), while q_{u,x} is q_{G_u}(vx), so that the direction of the edge pair is unambiguous in the row-sum matrix R.
  2. [Section 1.2, Formal verification] The statement that the proof has been formally verified in Lean 4 needs to be reconciled with the corrected constant in Theorem 1.3. Please state explicitly which displayed statements are certified and update the repository documentation to match the corrected bound; otherwise the formal-verification claim cannot be independently audited.
  3. [Section 3, proof of Lemma 1.4] After the constant is corrected, the sentence 'Combining (3.2) and (3.3) and rearranging' is valid, but it may be worth displaying the intermediate line (Σ√M_uv)² ≤ (1−1/ω)² n² 1ᵀM1/4 to make the role of the corrected constant transparent.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the DNN relaxation is restated and proved, the target inequality is never assumed, and the companion-paper self-citation is not load-bearing.

full rationale

The derivation chain is self-contained and non-circular. Theorem 1.2 is reduced to Lemma 1.4 by substituting M = A_+ ∘ A_+: the only facts used are 1^T M1 = s^+(G) and 2∑_{uv∈E} sqrt(M_uv) ≥ tr(AA_+) = s^+(G), both computed directly from the spectral decomposition; the desired inequality is not assumed. Lemma 1.4 is then proved from Theorem 1.3 via the pointwise bound W_P(M) ≤ (1/2)(1 − 1/ω)1^T M1, and Theorem 1.3 is proved from the weight-free harmonic bound (1.4). In turn, (1.4) follows from Lemma 1.6 by summing over vertices and applying Cauchy–Schwarz, while Lemma 1.6 is proved by induction from the first-pivot recurrences (Lemma 2.1) and the elementary reciprocal-row-sum inequality (Lemma 2.2). None of these implications invokes Conjecture 1.1 or Theorem 1.2. The citation to the authors' companion paper [28] ('Adopting the relaxation of our companion paper') is not load-bearing: the DNN Motzkin–Straus lemma is restated as Lemma 1.4 and fully proved here, and the square-energy result of [28] is not used in the proof. The statement of Lean 4 formal verification further supports self-containedness, assuming the formalization covers the corrected constant. Non-circularity caveat: Theorem 1.3 and Eq (3.3) print the constant 2(1 − 1/ω)/n², whereas the proof's own rearrangement yields 2ω/((ω − 1)n²); with the printed constant, the combination with (3.2) does not imply Lemma 1.4. This is a localized transcription/correctness error, not a circularity, because the derivation itself proves the corrected version.

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

No free parameters or invented entities. The proof is an exact parameter-free derivation using standard spectral, linear-algebraic, and probabilistic facts.

assumptions (4)
  • standard math Schur product theorem: the entrywise product of positive semidefinite matrices is positive semidefinite.
    Used in §3 to conclude M = A⁺∘A⁺ is PSD and hence doubly nonnegative.
  • standard math Spectral decomposition of a real symmetric adjacency matrix into positive and negative parts with A⁺A⁻ = 0.
    Used throughout §3 and in the proof of Theorem 1.2.
  • standard math Cauchy-Schwarz inequality.
    Used in §3 for the weighted Turán bound and in the sum over vertices.
  • standard math AM-GM inequality for two positive numbers.
    Used in Lemma 2.2 to prove the reciprocal row-sum bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A positive square-energy strengthening of Tur\'an's theorem." pith.science (2026). https://pith.science/paper/VMSEIFY3

@misc{pith2026260718044,
  author       = {Pith},
  title        = {Pith review of: A positive square-energy strengthening of Tur\'an's theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VMSEIFY3}},
  note         = {Machine review of arXiv:2607.18044}
}
abstract

Let $G$ be an $n$-vertex graph with clique number $\omega(G)$, and let $s^+(G)$ denote the sum of the squared positive adjacency eigenvalues. We prove that $$ \sqrt{s^+(G)}\le\left(1-\frac{1}{\omega(G)}\right)n. $$ This strengthens Wilf's classical spectral Tur\'{a}n theorem and resolves a conjecture of Elphick and Wocjan. Adopting the relaxation of our companion paper on the square-energy conjecture, we reduce the theorem to a Motzkin--Straus inequality for doubly nonnegative matrices, which we prove via a local inverse-probability estimate for the Caro--Wei greedy algorithm on the complement.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 6 linked inside Pith

  1. [1]

    Abiad, L

    A. Abiad, L. de Lima, D. N. Desai, K. Guo, L. Hogben, and J. Madrid, Positive and negative square energies of graphs,Electron. J. Linear Algebra39(2023), 307–326

    2023

  2. [2]

    Ailon, M

    N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: ranking and clustering,J. ACM55(2008), no. 5, Article 23

    2008

  3. [3]

    Akbari, H

    S. Akbari, H. Kumar, B. Mohar, and S. Pragada, A linear lower bound for the square energy of graphs, Electron. J. Combin.32(2025), no. 3, Paper P3.53

    2025

  4. [4]

    Akbari, H

    S. Akbari, H. Kumar, B. Mohar, and S. Pragada, Vertex partitioning andp-energy of graphs,Linear Algebra Appl.724(2025), 96–107

    2025

  5. [5]

    Akbari, H

    S. Akbari, H. Kumar, B. Mohar, S. Pragada, and S. Zhang, Refinement of a conjecture on positive square energy of graphs, arXiv:2506.07264, 2025

    arXiv 2025

  6. [6]

    Alon and J

    N. Alon and J. H. Spencer,The Probabilistic Method, fourth ed., John Wiley & Sons, Hoboken, NJ, 2016

    2016

  7. [7]

    Ando and M

    T. Ando and M. Lin, Proof of a conjectured lower bound on the chromatic number of a graph,Linear Algebra Appl.485(2015), 480–484

    2015

  8. [8]

    Balogh, F

    J. Balogh, F. C. Clemen, M. Lavrov, B. Lidický, and F. Pfender, MakingKr+1-free graphs r-partite, Combin. Probab. Comput.30(2021), 609–618. 10 Y. LIU, Q. TANG, AND S. ZHANG

    2021

Show all 38 references
  1. [9]

    G. E. Blelloch, J. T. Fineman, and J. Shun, Greedy sequential maximal independent set and matching are parallel on average, inProceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012, pp. 308–317; arXiv:1202.3205

    2012 arXiv

  2. [10]

    Bollobás and V

    B. Bollobás and V. Nikiforov, Cliques and the spectral radius,J. Combin. Theory Ser. B97(2007), no. 5, 859–865

    2007

  3. [11]

    Caro, New results on the independence number, Technical Report, Tel-Aviv University, 1979

    Y. Caro, New results on the independence number, Technical Report, Tel-Aviv University, 1979

    1979

  4. [12]

    Coutinho, T

    G. Coutinho, T. Jung Spier, and S. Zhang, Conic programming to understand sums of squares of eigenvalues of graphs, arXiv:2411.08184, 2024

    2024 arXiv

  5. [13]

    C. S. Edwards and C. H. Elphick, Lower bounds for the clique and the chromatic numbers of a graph, Discrete Appl. Math.5(1983), no. 1, 51–64

    1983

  6. [14]

    Elphick, M

    C. Elphick, M. Farber, F. Goldberg, and P. Wocjan, Conjectured bounds for the sum of squares of positive eigenvalues of a graph,Discrete Math.339(2016), no. 9, 2215–2223

    2016

  7. [15]

    Elphick and W

    C. Elphick and W. Linz, Symmetry and asymmetry between positive and negative square energies of graphs, Electron. J. Linear Algebra40(2024), 418–432

    2024

  8. [16]

    Elphick, W

    C. Elphick, W. Linz, and P. Wocjan, Two conjectured strengthenings of Turán’s theorem,Linear Algebra Appl.684(2024), 23–36

    2024

  9. [17]

    Elphick, Q

    C. Elphick, Q. Tang, and S. Zhang, A spectral lower bound on chromatic numbers usingp-energy,European J. Combin.132(2026), Part B, Article 104252

    2026

  10. [18]

    Elphick and P

    C. Elphick and P. Wocjan, Conjectured lower bound for the clique number of a graph, arXiv:1804.03752, 2018

    2018 arXiv

  11. [19]

    Fischer and A

    M. Fischer and A. Noever, Tight analysis of parallel randomized greedy MIS,ACM Trans. Algorithms16 (2019), no. 1, Article 6

    2019

  12. [20]

    Füredi, A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity,J

    Z. Füredi, A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity,J. Combin. Theory Ser. B115(2015), 66–71

    2015

  13. [21]

    A. J. Hoffman, On eigenvalues and colorings of graphs, inGraph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. Wisconsin, Madison, Wis., 1969), Academic Press, New York, 1970, pp. 79–91

    1969

  14. [22]

    R. A. Horn and C. R. Johnson,Matrix Analysis, second ed., Cambridge University Press, 2013

    2013

  15. [23]

    P. Hu, B. Lidický, T. Martins, S. Norin, and J. Volec, Large multipartite subgraphs inH-free graphs, in Extended Abstracts EuroComb 2021, Trends in Mathematics, Springer, Cham, 2021, pp. 707–713

    2021

  16. [24]

    Jadav, S

    H. Jadav, S. Madyastha, R. Raut, and R. Singh, Strengthening Wilf’s lower bound on clique number, arXiv:2504.04836, 2025

    2025 arXiv

  17. [25]

    Kelly and L

    T. Kelly and L. Postle, Improving the Caro–Wei bound and applications to Turán stability,Discrete Appl. Math.358(2024), 33–43

    2024

  18. [26]

    Krivelevich, T

    M. Krivelevich, T. Mészáros, P. Michaeli, and C. Shikhelman, Greedy maximal independent sets via local limits,Random Structures Algorithms64(2024), 986–1015

    2024

  19. [27]

    Liu and B

    L. Liu and B. Ning, Unsolved problems in spectral graph theory,Oper. Res. Trans.27(2023), no. 4, 33–60

    2023

  20. [28]

    Y. Liu, Q. Tang, and S. Zhang, The positive and negative square-energy conjecture, preprint, 2026

    2026

  21. [29]

    Mantel, Vraagstuk XXVIII,Wiskundige Opgaven met de Oplossingen10(1907), 60–61

    W. Mantel, Vraagstuk XXVIII,Wiskundige Opgaven met de Oplossingen10(1907), 60–61

    1907

  22. [30]

    T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán,Canad. J. Math.17(1965), 533–540

    1965

  23. [31]

    Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin

    V. Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin. Probab. Comput.11(2002), no. 2, 179–189

    2002

  24. [32]

    Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc

    M. Simonovits, A method for solving extremal problems in graph theory, stability problems, inTheory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319

    1966

  25. [33]

    Q. Tang, Y. Liu, and W. Wang, On the positive and negativep-energies of graphs under edge addition, Discrete Appl. Math.388(2026), 25–33

    2026

  26. [34]

    Turán, On an extremal problem in graph theory,Mat

    P. Turán, On an extremal problem in graph theory,Mat. Fiz. Lapok48(1941), 436–452

    1941

  27. [35]

    V. K. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum No. 81-11217-9, 1981

    1981

  28. [36]

    H. S. Wilf, Spectral bounds for the clique and independence numbers of graphs,J. Combin. Theory Ser. B 40(1986), 113–117

    1986

  29. [37]

    Wocjan and C

    P. Wocjan and C. Elphick, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix,Electron. J. Combin.20(2013), no. 3, Paper P39

    2013

  30. [38]

    Zhang, Extremal values for the square energies of graphs, arXiv:2409.15504, 2024

    S. Zhang, Extremal values for the square energies of graphs, arXiv:2409.15504, 2024. A POSITIVE SQUARE-ENERGY STRENGTHENING OF TURÁN’S THEOREM 11 Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, P. R. China Email address:liuyinch23@mai...

    2024 arXiv

Pith tools

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