Pith. sign in

REVIEW 4 cited by

Conic programming to understand sums of squares of eigenvalues of graphs

T0 review · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read For every graph, min{s+, s-} is at least 2m/chi_vec(G), resolving a conjecture of Wocjan, Elphick and Anekstein.

arxiv 2411.08184 v1 pith:KBX5HBT3 submitted 2024-11-12 math.CO math.OCmath.SP

Gabriel Coutinho , Thomás Jung Spier , Shengtong Zhang This is my paper · ORCID
classification math.COmath.OCmath.SP
keywords numberchromaticconjectureeigenvaluesvectorversioncliquematrices
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

Graphs can be summarized by the eigenvalues of their adjacency matrix. The paper studies the sum of squares of the positive eigenvalues, and similarly the negative ones. Wocjan, Elphick and Anekstein conjectured in 2018 that this quantity is at least 2m divided by the vector chromatic number, where m is the number of edges and chi_vec is a semidefinite programming relaxation of the chromatic number. The authors prove this conjecture by reformulating chi_vec as a conic program and deriving a strengthened Cauchy-Schwarz inequality for Hermitian matrices. The proof is short and the new inequality is likely useful on its own.

For the related Bollobas and Nikiforov conjecture, which replaces the vector chromatic number by the clique number and bounds only the top two eigenvalues, the paper proves a weaker constant, about 1.4231, instead of the conjectured 1. It also proves an asymptotic version with clique number plus 50 omega^{5/6}. The NP-hardness result for rank-r vector chromatic number SDPs follows from a rank-based bound.

The asymptotic version, however, appears to contain a mistake. In Lemma 20, the Motzkin-Straus inequality is applied to a completely positive Gram matrix and is claimed to give a lower bound on the nonedge sum alone. The correct inequality includes the diagonal terms as well. Omitting the diagonal makes the asserted bound false, so the proof of Theorem 4 does not go through.

Extended reading notes

Core claim

Theorem 1: For every graph G with m edges, min{s+, s-} >= 2m/chi_vec(G). This resolves the Wocjan-Elphick-Anekstein conjecture.

Load-bearing premise

The proof of Theorem 4 relies on Lemma 20, which states that for vectors in a cone of length pi/2 + 2 epsilon, the sum over nonedges of squared inner products is at least (1/((1+10 sqrt epsilon) omega)) times the total sum. In the proof, the Motzkin-Straus inequality (4) is applied to the completely positive Gram matrix W and is claimed to yield sum over nonedges of W_ij^2 >= (1/omega) times the total sum. The correct consequence of equation (5) is sum_i W_ii^2 plus sum over nonedges of W_ij^2 >= (1/omega) times the total sum. The diagonal terms sum_i r_i^4 are generally nonzero, so the claimed inequality is false, and this breaks the derivation of Lemma 12, Theorem 24 and Theorem 4.

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.

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

The central claims rest on standard matrix inequalities, the completely positive formulation of the clique number, and the equivalence of two SDPs for the vector chromatic number. The Motzkin-Straus application in the proof of the asymptotic Bollobas-Nikiforov bound is where the main error occurs.

assumptions (5)
  • standard math Schur product theorem: the Hadamard product of two PSD matrices is PSD
    Used in Lemma 2 to assert X composed with X is PSD when X is PSD.
  • standard math De Klerk-Pasechnik completely positive formulation of the clique number, equation (4)
    Used in Corollary 8, Lemma 15, and the vertex-weighted results.
  • standard math Motzkin-Straus inequality
    Used in Lemma 20; the paper's application drops the diagonal term and is flawed.
  • domain assumption The SDP in (3) exactly computes chi_vec(G), including the perturbation argument in Lemma 5
    Load-bearing for Theorem 1; the construction should zero out nonedge entries, which is obscured by the OCR and notation.
  • domain assumption Lemma 19 holds for all Borel measures by a standard limit argument from continuous densities
    Used in Lemma 18 and Lemma 11; the finite atomic case needed for the graph application follows by approximation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Conic programming to understand sums of squares of eigenvalues of graphs." pith.science (2026). https://pith.science/paper/KBX5HBT3

@misc{pith2026241108184,
  author       = {Pith},
  title        = {Pith review of: Conic programming to understand sums of squares of eigenvalues of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KBX5HBT3}},
  note         = {Machine review of arXiv:2411.08184}
}
abstract

In this paper we prove a conjecture by Wocjan, Elphick and Anekstein (2018) which upper bounds the sum of the squares of the positive (or negative) eigenvalues of the adjacency matrix of a graph by an expression that behaves monotonically in terms of the vector chromatic number. One of our lemmas is a strengthening of the Cauchy-Schwarz inequality for Hermitian matrices when one of the matrices is positive semidefinite. A related conjecture due to Bollob\'as and Nikiforov (2007) replaces the vector chromatic number by the clique number and sums over the first two eigenvalues only. We prove a version of this conjecture with weaker constants. An important consequence of our work is a proof that for any fixed $r$, computing a rank $r$ optimum solution to the vector chromatic number semidefinite programming is NP-hard. We also present a vertex weighted version of some of our results, and we show how it leads quite naturally to the known vertex-weighted version of the Motzkin-Straus quadratic optimization formulation for the clique number.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

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

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

    math.CO 2026-07 conditional novelty 8.0 of 10

    Every n-vertex graph with clique number ω has √s⁺(G) ≤ (1−1/ω)n, where s⁺(G) is the sum of squared positive adjacency eigenvalues.

  2. The positive and negative square-energy conjecture

    math.CO 2026-07 accept novelty 8.0 of 10

    Every connected graph G on n vertices satisfies min{s+(G), s−(G)} ≥ n−1, confirming the Elphick–Farber–Goldberg–Wocjan conjecture.

  3. Refinement of a conjecture on positive square energy of graphs

    math.CO 2025-06 conditional novelty 8.0 of 10

    For connected claw-free graphs with maximum degree at least 3 and for diameter-2 graphs other than stars and C5, the positive square energy is at least the number of vertices.

  4. A graph energy conjecture through the lenses of semidefinite programming

    math.CO 2025-09 reject novelty 6.0 of 10

    New SDP-based bounds relate graph energy to the fractional clique cover number, Hoffman's ratio number, and Schrijver's theta number, supporting a 40-year-old conjecture without proving it.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · cited by 4 Pith papers

  1. [1]

    Positive and negative square energies of graphs

    Aida Abiad, Leonardo De Lima, Dheer Noal Desai, Krystal Guo, Le slie Hogben, and Jos´ e Madrid. Positive and negative square energies of graphs. arXiv preprint arXiv:2303.11930 , 2023

    work page arXiv 2023

  2. [2]

    Proof of a conjectured lower bo und on the chromatic number of a graph

    Tsuyoshi Ando and Minghua Lin. Proof of a conjectured lower bo und on the chromatic number of a graph. Linear Algebra and its Applications , 485:480–484, 2015

    work page 2015

  3. [3]

    Orthonormal representations, vector chromatic n umber, and extension complexity

    Igor Balla. Orthonormal representations, vector chromatic n umber, and extension complexity. Bulletin of the London Mathematical Society , 56(9):2911–2921, 2024

    work page 2024

  4. [4]

    Matrix Analysis, volume 169

    Rajendra Bhatia. Matrix Analysis, volume 169. Springer, New York, NY, 1997. 30

    work page 1997

  5. [5]

    Academic Press, New York, 1978

    B´ ela Bollob´ as.Extremal graph theory . Academic Press, New York, 1978

    work page 1978

  6. [6]

    Cliques and the spectral rad ius

    B´ ela Bollob´ as and Vladimir Nikiforov. Cliques and the spectral rad ius. Journal of Combinatorial Theory, Series B , 97(5):859–865, 2007

    work page 2007

  7. [7]

    de Carli Silva and Levent Tun¸ cel

    Marcel K. de Carli Silva and Levent Tun¸ cel. An axiomatic duality fr ame- work for the theta body and related convex corners. Mathematical Pro- gramming, 162:283–323, 3 2017

    work page 2017

  8. [8]

    Approximation of the sta - bility number of a graph via copositive programming

    Etienne De Klerk and Dmitrii V Pasechnik. Approximation of the sta - bility number of a graph via copositive programming. SIAM Journal on Optimization, 12(4):875–892, 2002

    work page 2002

Show all 29 references
  1. [9]

    Symmetry and asymmetry be- tween positive and negative square energies of graphs

    Clive Elphick and William Linz. Symmetry and asymmetry be- tween positive and negative square energies of graphs. arXiv preprint arXiv:2311.11530, 2023

    2023 arXiv

  2. [10]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, Vera T. S´ os, and E. Szemer´ edi. More r esults on Ramsey-Tur´ an type problems.Combinatorica, 3(1):69–81, 1983

    1983

  3. [11]

    Continuous characterizations of the maximum clique proble m

    Luana E Gibbons, Donald W Hearn, Panos M Pardalos, and Motaku ri V Ramana. Continuous characterizations of the maximum clique proble m. Mathematics of Operations Research , 22(3):754–768, 1997

    1997

  4. [12]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Relaxations of vertex packing. Journal of Combinatorial Theory, Series B , 40:330–343, 6 1986

    1986

  5. [13]

    New eigenvalue bound for the fract ional chromatic number

    Krystal Guo and Sam Spiro. New eigenvalue bound for the fract ional chromatic number. J. Graph Theory , 106(1):167–181, 2024

    2024

  6. [14]

    Clique is hard to approximate within n 1- ε

    Johan H ˚ astad. Clique is hard to approximate within n 1- ε. Acta Math , 182(1):105–142, 1999

    1999

  7. [15]

    Signed spect ral Tur´ an type theorems

    M Rajesh Kannan and Shivaramakrishna Pragada. Signed spect ral Tur´ an type theorems. Linear Algebra and its Applications , 663:62–79, 2023

    2023

  8. [16]

    Approximate graph coloring by semidefinite programming

    David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM , 45(2):246– 265, 1998

    1998

  9. [17]

    The sandwich theorem

    Donald E Knuth. The sandwich theorem. arXiv preprint math/9312214 , 1993. 31

    1993 arXiv

  10. [18]

    Bollob´ as-Nikifor ov Conjecture for graphs with not so many triangles

    Hitesh Kumar and Shivaramakrishna Pragada. Bollob´ as-Nikifor ov Conjecture for graphs with not so many triangles. arXiv preprint arXiv:2407.19341, 2024

    2024 arXiv

  11. [19]

    Eigenvalues and triangle s in graphs

    Huiqiu Lin, Bo Ning, and Baoyindureng Wu. Eigenvalues and triangle s in graphs. Combinatorics, Probability and Computing , 30(2):258–270, 2021

    2021

  12. [20]

    Unsolved problems in spectral graph theory

    Lele Liu and Bo Ning. Unsolved problems in spectral graph theory . Oper. Res. Trans., 27(4):33–60, 2023

    2023

  13. [21]

    New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities

    Robert McEliece, Eugene Rodemich, Howard Rumsey, and Lloyd W elch. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities. IEEE transactions on Information Theory , 23(2):157–166, 1977

    1977

  14. [22]

    T. S. Motzkin and E. G. Straus. Maxima for graphs and a new pro of of a theorem of tur´ an.Canadian Journal of Mathematics , 17:533–540, 1965

    1965

  15. [23]

    Some inequalities for the largest eigenvalue of a graph

    Vladimir Nikiforov. Some inequalities for the largest eigenvalue of a graph. Combinatorics, Probability and Computing , 11(2):179–189, 2002

    2002

  16. [24]

    Eigenvalues of graphs

    Eva Nosal. Eigenvalues of graphs. Master’s thesis, University of Calgary , 1970

    1970

  17. [25]

    A comparison of the Delsarte and Lov´ as z bounds

    Alexander Schrijver. A comparison of the Delsarte and Lov´ as z bounds. IEEE Transactions on Information Theory , 25(4):425–429, 1979

    1979

  18. [26]

    Copositive and com- pletely positive matrices

    Naomi Shaked-Monderer and Abraham Berman. Copositive and com- pletely positive matrices . World Scientific, 2021

    2021

  19. [27]

    More tales of H off- man: bounds for the vector chromatic number of a graph

    Pawel Wocjan, Clive Elphick, and David Anekstein. More tales of H off- man: bounds for the vector chromatic number of a graph. arXiv preprint arXiv:1812.02613, 2018

    2018 arXiv

  20. [28]

    On the first two eigenvalues of regular grap hs

    Shengtong Zhang. On the first two eigenvalues of regular grap hs. Linear Algebra and its Applications , 686:102–110, 2024

    2024

  21. [29]

    Graph theory and additive combinatorics—exploring struct ure and randomness

    Yufei Zhao. Graph theory and additive combinatorics—exploring struct ure and randomness . Cambridge University Press, Cambridge, 2023. 32 Gabriel Coutinho Dept. of Computer Science Universidade Federal de Minas Gerais, Brazil E-mail address : gabriel@dcc.ufmg.br Thom´as Jung S...

    2023

Pith tools

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