{"id":"4f3a5799-a70d-4900-8111-2e79f4061785","arxiv_id":"2509.05814","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This paper derives new lower bounds on graph energy, a spectral measure of a graph, using semidefinite programming, as partial progress on a 40-year-old conjecture. It advances the field's tools and verifies the conjecture for new graph families, but leaves the conjecture open.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5 invalid: Lemma 5.3 (ϑ^-ϑ^+=n) is false for K_n; Theorem 1.6's proof therefore fails for a highly regular graph.","rationale":"The SDP identity in Theorem 1.2 and the decomposition machinery in Sections 2–4 appear sound; the Johnson graph application is a nice consequence. However, Theorem 1.6 is the paper's most novel and strongest statement, and its proof rests on Lemma 5.3. The complete graph K_n is an explicit member of every 'highly regular' class mentioned (vertex-transitive, distance-regular), and the two theta values are easy to compute; the product is 1, not n. This is not a subtle gap: the equality step in the proof of Theorem 1.6 evaluates to 0 for K_n instead of n−1. The abstract's version of Theorem 1.3 indicates a parallel transcription issue (χ_f(\\bar G) vs χ_f(G)), but that bound is independently recoverable and less central. The Section 5 flaw cannot be repaired by swapping G for \\bar G without a new argument, because the proof requires ⟨J,Y⟩ for the Szegedy theta of G itself. The reader's assessment is therefore correct: the central claims as printed are unsupported, and REJECT is warranted. The concrete computation of K_n is a decisive check; if instead [8]'s Cor 10 is verified to say ϑ^-(G)ϑ^+(G)=n, then the definitions in this paper or in [8] must mismatch, and the paper should state and prove the correct identity.","tokens_in":13295,"tokens_out":10544,"duration_ms":101971,"concrete_test":"Evaluate SDP (5.3) and SDP (10) directly for G=K_n (n≥3). For ϑ^-(K_n), X must be diagonal with X≥0, trace 1, so ϑ^-=1. For ϑ^+(K_n), feasibility gives Y_{ij}≤0 for i≠j; the maximum of ⟨J,Y⟩ is attained at Y_{ij}=0 off-diagonal, so ϑ^+=1. If the product is 1≠n, Lemma 5.3 is falsified. Then insert Y=I/n into the proof of Theorem 1.6: ⟨A,K_n,I/n⟩=0, while n−ϑ^-(K_n)=n−1, demonstrating the failure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central new bound, Theorem 1.6, depends on Lemma 5.3, imported from [8, Cor 10], that for every highly regular G, ϑ^-(G)ϑ^+(G)=n. This identity is false as stated. For G=K_n, which is highly regular (vertex-transitive and distance-regular), Schrijver's ϑ^- equals 1: the constraint X∘A=0 forces X diagonal, trace 1 and X≥0 give maximum ⟨J,X⟩=1. The Szegedy theta SDP (10) also equals 1: off-diagonal entries must be ≤0, so to maximize ⟨J,Y⟩ with trace 1 one sets off-diagonal entries to 0, again giving 1. Thus ϑ^-ϑ^+=1≠n for n≥2. Consequently the proof of Theorem 1.6 is invalid: tracing it with G=K_n and Y=I/n (an optimal solution of SDP (10)), the constructed X=I/n gives ⟨A,X⟩=0, whereas the theorem would require n−1. The line '= n − ϑ^-(G)' in the proof is precisely where the false product is used. The likely intended identity involves the complement (ϑ^+(ar K_n)=n), but the paper neither states nor proves a correct identity for ϑ^+(G), so the gap is not a simple typo. This leaves Theorem 1.6, the paper's strongest support for Fajtlowicz's conjecture, unproven as printed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13499,"tokens_out":9800,"duration_ms":108270,"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":[{"comment":"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":"Section 5, Lemma 5.3"},{"comment":"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":"Section 5, proof of Theorem 1.6"},{"comment":"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.","section":"Section 3, Theorem 1.3 and Eq. (6)"}],"minor_comments":[{"comment":"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":"Section 4, SDP (7)"},{"comment":"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.","section":"Section 5, Definition 5.1"},{"comment":"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.","section":"Appendix, Tables 1 and 2"}],"recommendation":"reject","confidential_remarks":"Sections 2–4 contain solid, publishable material. The main obstacle is Section 5, where Lemma 5.3 is false and the proof of Theorem 1.6 is algebraically invalid; repairing this will require a new argument, not a local correction. In addition, Theorem 1.3 currently states a false result under standard terminology. The authors may wish to split the paper into a Sections 2–4 contribution and a separate, fully corrected treatment of theta-based bounds. The misquotation of Corollary 10 from [8] (which shares an author) should be checked carefully in any revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nMore 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.\n\nThe 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.\n\nBottom 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.","headline":"Solid SDP-based bounds in Sections 2–4, but Section 5 is broken as printed; Theorem 1.6 is not proven.","tokens_in":14161,"tokens_out":4264,"would_cite":false,"duration_ms":43362,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","90C22","05C15","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"Half graph energy equals a semidefinite program optimum, and the paper uses feasible solutions to prove new lower bounds supporting Fajtlowicz's n − α conjecture.","keywords":["graph energy","semidefinite programming","Fajtlowicz conjecture","independence number","fractional chromatic number","Hoffman ratio bound","Schrijver theta number","highly regular graphs"],"falsifier":"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.","tokens_in":13043,"feed_emoji":"⚡","tokens_out":13918,"duration_ms":134010,"temperature":0.7,"pith_summary":"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.","feed_headline":"Half graph energy equals one SDP optimum; new bounds support conjecture","feed_subtitle":"New lower bounds using fractional chromatic, Hoffman, and theta numbers edge closer to Fajtlowicz's n − α conjecture.","key_machinery":"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.","core_discovery":"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].","pith_inferences":["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."],"forward_implications":["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 α."],"supporting_citations":[{"why":"Records Fajtlowicz's Graffiti conjecture that the paper aims to support.","marker":"[5]"},{"why":"States the conjecture as Conjecture 20 and documents its verification for all graphs up to 10 vertices.","marker":"[15]"},{"why":"Supplies the clique-cover energy bound and the additivity lemma that Theorem 1.3 and Lemma 3.2 generalize.","marker":"[13]"},{"why":"Gives the energy lower bound that Theorem 1.5 refines for regular graphs and the almost-all-graphs support for the conjecture.","marker":"[17]"},{"why":"Provides the coherent-algebra facts—PSD projection preservation and the theta product identity—on which Theorem 1.6's proof relies.","marker":"[8]"},{"why":"The earlier energy decomposition bound that Lemma 3.2 extends.","marker":"[4]"},{"why":"The earlier edge-deletion energy bound that Lemma 3.2 extends.","marker":"[7]"}],"fun_headline_variants":["Graph energy as SDP optimum yields new lower bounds","SDP unlocks graph energy bounds, closing in on conjecture","New SDP proof edges toward Fajtlowicz's energy conjecture","Graph energy reformulated as SDP, boosting conjecture support","Semidefinite lens sharpens graph energy bounds"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Graph energy as SDP optimum yields new lower bounds","SDP unlocks graph energy bounds, closing in on conjecture","New SDP proof edges toward Fajtlowicz's energy conjecture","Graph energy reformulated as SDP, boosting conjecture support","Semidefinite lens sharpens graph energy bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000168,"raw_usage":{"total_tokens":1175,"prompt_tokens":896,"completion_tokens":279,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":640,"completion_tokens_details":{"reasoning_tokens":198}},"tokens_in":640,"tokens_out":279,"duration_ms":3467,"temperature":1.0,"reasoning_tokens":198,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T05:05:58.697391+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Aouchiche and P","cited_arxiv_id":null,"evidence_quote":"Records Fajtlowicz's Graffiti conjecture that the paper aims to support."},{"cited_title":"Liu and B","cited_arxiv_id":null,"evidence_quote":"States the conjecture as Conjecture 20 and documents its verification for all graphs up to 10 vertices."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the clique-cover energy bound and the additivity lemma that Theorem 1.3 and Lemma 3.2 generalize."},{"cited_title":"Nikiforov","cited_arxiv_id":null,"evidence_quote":"Gives the energy lower bound that Theorem 1.5 refines for regular graphs and the almost-all-graphs support for the conjecture."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the coherent-algebra facts—PSD projection preservation and the theta product identity—on which Theorem 1.6's proof relies."},{"cited_title":"Andrade, M","cited_arxiv_id":null,"evidence_quote":"The earlier energy decomposition bound that Lemma 3.2 extends."},{"cited_title":"Day and W","cited_arxiv_id":null,"evidence_quote":"The earlier edge-deletion energy bound that Lemma 3.2 extends."}],"review_version":1}