Pith. sign in

REVIEW 4 cited by

Conic programming to understand sums of squares of eigenvalues of graphs

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

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
0 comments
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.

Pith tools