A graph energy conjecture through the lenses of semidefinite programming

Aida Abiad; Emanuel Juliano; Gabriel Coutinho; Luuk Reijnders

REVIEW 3 major objections 3 minor 1 cited by

A graph energy conjecture through the lenses of semidefinite programming

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

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

Pith's one-line read Half graph energy equals a semidefinite program optimum, and the paper uses feasible solutions to prove new lower bounds supporting Fajtlowicz's n − α conjecture.

desk verdict Solid SDP-based bounds in Sections 2–4, but Section 5 is broken as printed; Theorem 1.6 is not proven. read the letter →

arxiv 2509.05814 v1 pith:X6SA3TDO submitted 2025-09-06 math.CO

Aida Abiad , Gabriel Coutinho , Emanuel Juliano , Luuk Reijnders This is my paper · ORCID

classification math.CO MSC 05C5090C2205C1505C69

keywords graphenergysemidefiniteprogrammingFajtlowiczconjectureindependencenumberfractionalchromaticHoffmanratioboundSchrijverthetahighlyregulargraphs

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 derives a semidefinite program whose optimal value is exactly half the graph energy—the sum of the positive adjacency eigenvalues. It then uses feasible solutions of that program to prove new lower bounds on this quantity: at least n minus the fractional chromatic number of the complement, at least n minus Hoffman's ratio number for regular graphs, and, for highly regular graphs, at least n minus Schrijver's theta number. These inequalities strengthen earlier bounds by Hoffman and Nikiforov and bring partial, not conclusive, support to Fajtlowicz's conjecture that half the energy is at least n minus the independence number. The proofs also yield an energy-decomposition lemma of independent interest.

What carries the argument

The engine is the semidefinite characterization of half-energy together with its dual: maximize <A,X> subject to 0 ≼ X ≼ I, whose dual minimizes <I,Y> with Y ≽ A and Y ≽ 0; weak duality gives <A,X> ≤ 1/2E(G) for every feasible X. The positive part of the adjacency spectrum realizes the optimum. For the highly regular case, the extra tool is the coherent algebra of the graph—a matrix algebra containing A, I, J that is spanned by a 0/1 basis—because projection onto this algebra preserves positive semidefiniteness and lets the authors move optimal Szegedy-theta solutions into the algebra.

What would settle it

Look at the complete graph K_n: the lemma behind Theorem 1.6 asserts ϑ^-(K_n)ϑ^+(K_n)=n, but both theta numbers equal 1, so the identity is false and the proof of the highly regular bound is not valid as written for that case. The final inequality itself still holds for K_n (both sides equal n−1), so this observation targets the proof's lemma, not the theorem's truth.

Watch

Extended reading notes

Core claim

The central claim is that half the graph energy, defined as the sum of the positive adjacency eigenvalues, is exactly the optimum of the semidefinite program max{<A,X> : I ≽ X ≽ 0}. From this exact reformulation, the paper constructs feasible matrices X and obtains new lower bounds: (1/2)E(G) ≥ n − χ_f(bar G); for regular non-complete G, (1/2)E(G) ≥ n − H(G); a refined regular-graph bound (1/2)E(G) ≥ [2m − λ1(λ1−λ2)]/(λ2−λ_n), which implies the conjecture for Johnson graphs; and, for highly regular graphs, (1/2)E(G) ≥ n − ϑ^-(G). Each feasible X yields a certificate, so the SDP formulation turns the search for energy bounds into a search for matrices with spectra inside [0,1].

Load-bearing premise

The highly regular graph bound relies on an imported product identity relating two theta numbers of the graph's coherent algebra; as printed that identity fails for complete graphs, so the proof needs a missing complement bar or an added hypothesis.

Editorial extensions

If this is right

Any feasible matrix X with 0 ≼ X ≼ I produces a computable lower bound on half the energy, turning future constructions of such matrices into direct evidence for the conjecture.
Theorem 1.3 upgrades Hoffman's clique-cover bound to the fractional chromatic number of the complement, settling the conjecture for graphs with α(G)=χ_f(bar G).
Theorem 1.4 proves the conjecture for every regular graph that meets Hoffman's ratio bound with equality.
Theorem 1.5 gives a lower bound depending only on the degree and the top three adjacency eigenvalues, and implies the conjecture for all Johnson graphs J(r,k).
Theorem 1.6 gives the strongest bound in the paper: for highly regular graphs, (1/2)E(G) ≥ n − ϑ^-(G), which is tighter than the other new bounds because ϑ^- sits closer to α.

Reading between the lines

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

The decomposition lemma (Lemma 3.2) holds for arbitrary symmetric matrices, not only adjacency matrices; applying it to weighted graphs or other matrix frames satisfying the same weighted square decomposition would yield energy bounds for those objects as well.
The SDP viewpoint suggests a route to the full conjecture: find, for every graph, a matrix in some algebra attached to the graph that closes the gap to n − α(G); Theorem 1.6 shows this works for coherent algebras, and a generic projection that preserves positive semidefiniteness would extend it.
If the product-identity gap in Theorem 1.6 is repaired by excluding or complementing complete graphs, one could test whether the highly regular bound remains tight for distance-regular graphs and how it degrades for small perturbations of regular graphs.

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

Quick take: the SDP reformulation of graph energy is real, and the weighted decomposition lemma gives clean refinements of Hoffman and Nikiforov. But the final section, on highly regular graphs, is not valid as written. The paper needs revision, not rejection of the underlying idea.

What's genuinely good: Lemma 3.2 is a flexible tool—it generalizes Andrade–Robbiano–San Martin and Day–So, and it yields a simple proof of (1/2)E ≥ n − χ_f(\bar G), which is a nice strengthening of Hoffman's clique-cover bound. Theorems 1.4 and 1.5 for regular graphs are proven carefully; the LP duality check in Lemma 4.2 is sound, and the Johnson graph application is a pleasant concrete win. The computational tables in the appendix are useful.

The problems: Theorem 1.3 as stated in the full text says χ_f(G), which is false for K_{1,3}. The proof actually establishes χ_f(\bar G), and the abstract has the complement bar. This looks like a transcription slip in the provided text, but a false theorem in the body is still a false theorem.

More serious: Section 5. Lemma 5.3, taken from [8], claims θ^−(G)θ^+(G)=n for every highly regular G. For G=K_n (n≥2), both θ^− and θ^+ equal 1, so the product is 1, not n. That's not a minor typo; it's a counterexample to the stated identity. Since the proof of Theorem 1.6 uses exactly this product to conclude θ^−(G)θ^+(G)=n, the claimed bound (1/2)E ≥ n−θ^−(G) is unsupported for the class of highly regular graphs. The stress-test note is correct: tracing the proof with K_n gives objective value 0, not n−1.

The fix may well be to state the identity for the complement (θ^+(K_n)=n), but that needs to be proved or properly imported from [8], and Section 5 re-checked. My sense is the authors know these details—the abstract is right about Theorem 1.3—so this is a bug in the writing, not a failure of the method.

Bottom line: send it to referees. The core SDP approach is worth attention, and the errors look correctable. But as it stands, only Sections 2–4 can be trusted; the highly-regular result should not be cited until it's fixed.

Referee Report

3 major / 3 minor

Summary. The manuscript gives an SDP formulation of graph energy (Theorem 1.2) and uses feasible solutions of that SDP to derive lower bounds on half the energy: n − χ_f(G) (Theorem 1.3), n − H(G) for regular graphs (Theorem 1.4), a refinement of Nikiforov's bound (Theorem 1.5), and n − ϑ^−(G) for highly regular graphs (Theorem 1.6). These are presented as partial evidence for Fajtlowicz's conjecture (1/2)E(G) ≥ n − α(G). Sections 2–4 contain proofs that are mostly verifiable and appear sound, including the SDP duality argument, the matrix decomposition lemma, the LP duality for the restricted SDP, and the Johnson graph application. Section 5, however, contains a false imported lemma and an algebraically invalid proof of Theorem 1.6, which is one of the paper's headline results.

Significance. If the results were correct, Theorems 1.3–1.6 would be new spectral lower bounds on graph energy, refining classical results of Hoffman and Nikiforov, and the SDP perspective would be a valuable tool for Fajtlowicz's conjecture. The verified parts—Theorem 1.2, Lemma 3.2, Lemma 4.2, and Corollary 4.3—are elegant and of independent interest. However, the paper's strongest advertised contribution, Theorem 1.6 for highly regular graphs, is not established: Lemma 5.3 is false as stated, and the displayed computation in the proof of Theorem 1.6 is not a valid consequence of the construction. These are load-bearing errors, not presentation issues.

major comments (3)

[Section 5, Lemma 5.3] Lemma 5.3 claims ϑ^−(G)ϑ^+(G)=n for every n-vertex highly regular graph. This is false. For G=K_n (n≥2), which is highly regular, ϑ^−(K_n)=1 because X∘A=0 forces X diagonal, tr X=1 and X≥0 force ⟨J,X⟩=1. Likewise, in SDP (10), Y∘A=0 forces off-diagonal entries of Y to be ≤0; since tr Y=1 and Y≽0, the maximum of ⟨J,Y⟩ is achieved at diagonal Y, giving ϑ^+(K_n)=1. Thus the product is 1, not n. The intended identity may involve the complement, but the manuscript neither states nor proves a correct version. Consequently, the line '= n−ϑ^−(G)' in the proof of Theorem 1.6 has no valid basis.
[Section 5, proof of Theorem 1.6] The proof defines X=ϑ^−(G)Y with Y optimal for SDP (10). Then ⟨A,X⟩=ϑ^−(G)⟨A,Y⟩. The proof instead asserts ⟨A,X⟩=ϑ^−(G)(⟨J,Y⟩−⟨A,Y⟩−1). No justification is given, and the identity is generally false. For K_n, take Y=I/n; the right-hand side is 0, whereas the claimed bound n−ϑ^−(K_n)=n−1 is positive. Since every feasible Y for SDP (10) satisfies Y∘A≤0, we have ⟨A,Y⟩≤0, so a matrix of the form ϑ^−(G)Y cannot have the required objective. This is not a minor typo; the construction and the computation are incompatible.
[Section 3, Theorem 1.3 and Eq. (6)] The theorem states (1/2)E(G) ≥ n−χ_f(G), with χ_f called the fractional chromatic number. However, Eq. (6) defines χ_f via a fractional clique cover of G, not a fractional independent-set coloring. Under the standard meaning of fractional chromatic number, the theorem is false: for K_{1,3}, (1/2)E(K_{1,3})=√3≈1.732, but n−χ_f(K_{1,3})=4−2=2. Under the clique-cover definition used in the proof, the bound is correct but is not a statement about χ_f(G); it is a bound on the fractional clique cover number, equivalently on χ_f(\bar G). The abstract writes χ_f(\bar G), while the full text writes χ_f(G). The statement, the definition, and the abstract need to be reconciled.

minor comments (3)

[Section 4, SDP (7)] The notation 'X=aA+b A+cI' is confusing because the displayed list of variables is 'a,b∈R' and c is not mentioned; the text later says c can be ignored, but the constraint set should state c∈R explicitly.
[Section 5, Definition 5.1] Property 3, '∃I:A=∑_{i∈I} B_i', uses I both as an index set and (elsewhere) as the identity matrix. Please rename the index set, e.g., S, to avoid ambiguity.
[Appendix, Tables 1 and 2] The table captions describe ratios 'n−α(G) divided by the bound', but the columns are not fully defined; in particular, the difference between 'SDP (7) (b=0)' and 'SDP (7)' should be clarified.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; self-cited [8] results are load-bearing but independent, and the printed Lemma 5.3 is a correctness defect rather than a circular step.

full rationale

The central derivation chain is self-contained: Theorem 1.2 is an exact SDP formulation proven by exhibiting primal and dual feasible solutions with equal objective value; Theorems 1.3, 1.4, and 1.5 follow from explicit feasible solutions (Lemmas 3.3 and 4.1, and the optimized a,b in Theorem 1.5) whose optimality within the restricted family is proven in Lemma 4.2. None of these steps uses the Fajtlowicz inequality as an input, and no parameter is fitted to the target energy. The only self-citation of concern is Section 5, where Lemmas 5.2 and 5.3 are imported from [8], a paper sharing an author (Coutinho). These results are load-bearing for Theorem 1.6, but they are external mathematical statements about coherent algebras and theta numbers, not consequences of the energy conjecture; they are not fitted or defined in terms of the target bound. In fact, Lemma 5.3 is false as printed for G=K_n, since both Schrijver's and Szegedy's theta equal 1, so the displayed identity ϑ^-(G)ϑ^+(G)=n fails; this invalidates the proof of Theorem 1.6 as written and is a serious correctness gap, but it is not a circularity. Additionally, the abstract's χ_f(\bar G) version of Theorem 1.3 is not the same as the full-text χ_f(G) claim, which is false for K_{1,3}; again a correctness issue, not circularity. Accordingly, the circularity burden is low.

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

No numerical constants are fitted to data; the a, b, c in Section 4 are chosen for feasibility and proven optimal within the restricted family (Lemma 4.2), and ϑ^- is a standard graph parameter. The most consequential assumptions are the imported theta-body facts from [8] behind Theorem 1.6, which as printed fail for complete graphs and were not re-derived here.

assumptions (7)

standard math SDP weak duality for the primal/dual pair (2)/(3)
Used in the proof of Theorem 1.2 to show ⟨A,X⟩ ≤ ⟨I,Y⟩ for feasible X, Y, and in Lemma 4.2 for LP duality.
standard math Variational form of the positive spectral part: max{⟨M,X⟩ : 0 ≼ X ≼ I} = Σ_{λ>0} λ
Content of Theorem 1.2; standard matrix duality, proven by the authors with explicit primal and dual optimal solutions.
domain assumption The clique LP (6) with equality constraints computes the fractional chromatic number
Invoked in the proof of Theorem 1.3. Under definition (6) the quantity is θ_f(G) = χ_f(\bar G), so this assumption encodes the complement-bar discrepancy between the abstract and the full-text theorem.
domain assumption Projection onto the coherent algebra of a highly regular graph preserves positive semidefiniteness
Lemma 5.2, cited from [8, Cor. 2.2] and not re-proved; load-bearing for Lemma 5.4, Lemma 5.5, and Theorem 1.6. The reference shares an author (Coutinho) with this paper.
domain assumption ϑ^-(G)ϑ^+(G) = n for highly regular graphs
Lemma 5.3, cited from [8, Cor. 10]; as printed it fails for complete graphs (both thetas equal 1), so the true hypothesis must involve the complement or exclude such graphs.
domain assumption α(G) ≤ ϑ^-(G) ≤ χ_f(\bar G) ≤ χ(\bar G) and ϑ^-(G) ≤ H(G) for regular G
Used in the introduction to position Theorem 1.6 relative to the conjecture; cited to Lovász [16].
standard math Spread bound n ≥ λ_1 + |λ_n| for k-regular graphs
Used in Lemma 4.5; cited to Gregory, Hershkowitz, and Kirkland [11].

how reviews work

0 comments

Cite this review

Pith. "Pith review of A graph energy conjecture through the lenses of semidefinite programming." pith.science (2026). https://pith.science/paper/X6SA3TDO

@misc{pith2026250905814,
  author       = {Pith},
  title        = {Pith review of: A graph energy conjecture through the lenses of semidefinite programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X6SA3TDO}},
  note         = {Machine review of arXiv:2509.05814}
}

abstract

Let $G$ be a graph on $n$ vertices with independence number $\alpha(G)$. Let $\mathcal{E}(G)$ be the energy of a graph, defined as the sum of the absolute values of the adjacency eigenvalues of $G$. Using Graffiti, Fajtlowicz conjectured in the 1980s that $$\frac{1}{2}\mathcal{E}(G) \geq n - \alpha(G).$$ In this paper we derive a semidefinite program formulation of the graph energy, and we use it to obtain several results that constitute a first step towards proving this conjecture. In particular, we show that $$\frac{1}{2}\mathcal{E}(G) \geq n - \chi_f(\overline{G}) \quad \text{ and } \quad \frac{1}{2}\mathcal{E}(G) \geq n - H(G),$$ where $\chi_f(G)$ is the fractional chromatic number and $H(G)$ is Hoffman's ratio number. As a byproduct of the SDP formulation we obtain several lower bounds for the graph energy that improve and refine previous results by Hoffman (1970) and Nikiforov (2007). The later author showed that the conjecture holds for almost all graphs. However, the graph families known to attain the conjecture with equality are highly structured and do not represent typical graphs. Motivated by this, we prove the following bound in support of the conjecture for the class of highly regular graphs $$\frac{1}{2}\mathcal{E}(G) \geq n - \vartheta^-(G),$$ where $\vartheta^-$ is Schrijver's theta number.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Energy and independence number
math.CO 2026-07 accept novelty 8.0 of 10

Every graph's energy is at least 2(n−α(G)), so Fajtlowicz's energy–independence conjecture is true.

Reference graph

Works this paper leans on

21 extracted references · 18 canonical work pages · cited by 1 Pith paper

[8]

M. K. de Carli Silva, G. Coutinho, C. Godsil, and D. E. Roberson. Algebras, graphs and thetas.Electronic Notes in Theoretical Computer Science, 346:275–283, 2019

work page 2019
[1]

Abiad, W

A. Abiad, W. Bosma, and T. van Veluw. Hoffman colorings of graphs.Linear Algebra and its Applications, 710:129–150, 2025

work page 2025
[2]

Hoffman colorability of (strongly) regular graphs

A. Abiad, B. De Bruyn, and T. van Veluw. Hoffman colorability of (strongly) regular graphs. arXiv:2508.18793

work page Pith review arXiv
[3]

Akbari, M

S. Akbari, M. Einollahzadeh, M. M. Karkhaneei, and M. A. Nematollahi. Proof of a conjecture on the Seidel energy of graphs.Linear Algebra and its Applications, 574:1–9, 2019

work page 2019
[4]

Andrade, M

E. Andrade, M. Robbiano, and B. San Martin. A lower bound for the energy of symmetric matrices and graphs.Linear Algebra and its Applications, 513:264–275, 2017

work page 2017
[5]

Aouchiche and P

M. Aouchiche and P. Hansen. A survey of automated conjectures in spectral graph theory.Linear Algebra and its Applications, 432:2293–2322, 2010

work page 2010
[6]

Coutinho, T

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

arXiv
[7]

Day and W

J. Day and W. So. Graph energy change due to edge deletion.Linear Algebra and its Applications, 428(8-9):2070–2078, 2008

work page

Show all 21 references

[9]

Elphick, Q

C. Elphick, Q. Tang, and S. Zhang. A spectral lower bound on chromatic numbers usingp-energy. arXiv:2504.01295

arXiv
[10]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi. Asymmetric graphs.Acta Mathematica Academiae Scien- tiarum Hungaricae, 14(1-2):295–315, 1963. 15

1963
[11]

D. A. Gregory, D. Hershkowitz, and S. J. Kirkland. The spread of the spectrum of a graph.Linear Algebra and its Applications, 332:23–35, 2001

2001
[12]

I. Gutman. The energy of a graph: Old and new results. In A. Betten, A. Kohnert, R. Laue, and A. Wassermann, editors,Algebraic Combinatorics and Applications, pages 196–211. Springer, Berlin, Heidelberg, 2001

2001
[13]

A. J. Hoffman. On eigenvalues and colorings of graphs.Selected Papers of Alan J. Hoffman: With Commentary, pages 407–419, 2003

2003
[14]

Laurent, S

M. Laurent, S. C. Polak, and L. F. Vargas. Semidefinite approximations for bicliques and bi-independent pairs.Mathematics of Operations Research, 50(1):537–572, 2024

2024
[15]

Liu and B

L. Liu and B. Ning. Unsolved problems in spectral graph theory.Operations Research Transactions, 27(4):33–60, 2023

2023
[16]

Lov´ asz

L. Lov´ asz. On the Shannon capacity of a graph.IEEE Transactions on Information Theory, 25(1):1–7, 1979

1979
[17]

Nikiforov

V. Nikiforov. The energy of graphs and matrices.Journal of Mathematical Analysis and Applications, 326(2):1472–1475, 2007

2007
[18]

R. Sotirov. An efficient semidefinite programming relaxation for the graph partition problem.INFORMS Journal on Computing, 26(1):16–30, 2014

2014
[19]

R. C. Thompson. Singular value inequalities for matrix sums and minors.Linear Algebra and its Applications, 11(3):251–269, 1975

1975
[20]

E. R. van Dam, W. H. Haemers, and J. H. Koolen. Regular graphs with maximal energy per vertex.Journal of Combinatorial Theory, Series B, 107:123–131, 2014

2014
[21]

S. Zhang. Extremal values for the square energies of graphs. arXiv:2409.15504. 16 Appendix: computational experiments Graph SDP (7) (b= 0) Theorem 1.3 SDP (7) SDP (2) Balaban 10-cage 1.0 1.0 0.91544 0.64477 Balaban 11-cage 1.04568 1.07143 0.96127 0.71395 Bidiakis cube 1.08142 ...

arXiv

Pith tools

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

[1] [8]

M. K. de Carli Silva, G. Coutinho, C. Godsil, and D. E. Roberson. Algebras, graphs and thetas.Electronic Notes in Theoretical Computer Science, 346:275–283, 2019

work page 2019

[2] [1]

Abiad, W

A. Abiad, W. Bosma, and T. van Veluw. Hoffman colorings of graphs.Linear Algebra and its Applications, 710:129–150, 2025

work page 2025

[3] [2]

Hoffman colorability of (strongly) regular graphs

A. Abiad, B. De Bruyn, and T. van Veluw. Hoffman colorability of (strongly) regular graphs. arXiv:2508.18793

work page Pith review arXiv

[4] [3]

Akbari, M

S. Akbari, M. Einollahzadeh, M. M. Karkhaneei, and M. A. Nematollahi. Proof of a conjecture on the Seidel energy of graphs.Linear Algebra and its Applications, 574:1–9, 2019

work page 2019

[5] [4]

Andrade, M

E. Andrade, M. Robbiano, and B. San Martin. A lower bound for the energy of symmetric matrices and graphs.Linear Algebra and its Applications, 513:264–275, 2017

work page 2017

[6] [5]

Aouchiche and P

M. Aouchiche and P. Hansen. A survey of automated conjectures in spectral graph theory.Linear Algebra and its Applications, 432:2293–2322, 2010

work page 2010

[7] [6]

Coutinho, T

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

arXiv

[8] [7]

Day and W

J. Day and W. So. Graph energy change due to edge deletion.Linear Algebra and its Applications, 428(8-9):2070–2078, 2008

work page