Sharp spectral-deficit stability for triangle-free graphs

Statement

For every finite simple triangle-free graph $G$, put $m=e(G)$ and let $\lambda(G)$ denote its adjacency spectral radius (with $\lambda(G)=0$ when $G$ has no vertices). Define $D(G)=\min_{A,B\subseteq V(G),\ A\cap B=\varnothing}|E(G)\mathbin{\triangle}E(K_{A,B})|$, where $K_{A,B}$ has all edges between $A$ and $B$ and no other edges on $V(G)$; empty parts are permitted. Then $D(G)\le 3\bigl(m-\lambda(G)^2\bigr)$.

Motivation

Nosal's inequality $\lambda(G)^2\le e(G)$ makes the spectral deficit $\xi=e(G)-\lambda(G)^2$ a measure of departure from the complete-bipartite extremal situation. Recent edge-spectral stability work controls structural distance when this deficit is small. The present question asks for an exact finite inequality, valid at every deficit and independent of graph order: does the same coefficient three that controls complete-bipartite editing for bipartite graphs also control every triangle-free graph? Both additions and deletions count, and the target may have arbitrary part sizes and isolated vertices. This is the target and deficit of the cited bipartite theorem, with only the bipartiteness hypothesis removed. The coefficient is fixed by mathematics: the five-cycle has $D(C_5)=3$ and $\xi(C_5)=1$, while a proved supporting bound gives $D(G)\le15\xi$ and an asymptotic upper coefficient three as $\xi/e(G)\to0$. An affirmative answer would determine the optimal uniform coefficient exactly and show that allowing odd cycles introduces no extra coefficient beyond the bipartite theorem. A counterexample would refute that proposed uniform law. These are the established bounds and the explanatory distinction supporting the question; no classification of equality graphs or consequence for other open conjectures is asserted. The strongest objection is that this is merely a constant improvement after a linear bound is available. The intended gain is narrower and exact: deciding whether the bipartite coefficient remains valid throughout the triangle-free class, including finite positive deficits, despite the non-bipartite sharp example. Asking only for some finite linear coefficient is now settled by the supporting theorem, and asking only for deletion distance to bipartiteness is already settled by the cited cut lemma. Qualitative stability and the asymptotic upper coefficient do not decide the displayed exact inequality. This comparison identifies the remaining gain without claiming that every improvement of the bound fifteen is significant or that the available methods cannot settle the question.

Current state

Li, Liu and Zhang, arXiv:2508.15271v2, Theorem 4.1, establish qualitative triangle-free edge-spectral stability. Li, Liu and Ning, arXiv:2609.20225v2, Lemma 4.3, prove $D(H)\le3(e(H)-\lambda(H)^2)$ for bipartite graphs. Their Lemma 4.4 also supplies a triangle-free cut obtained by deleting at most $e(G)-\lambda(G)^2$ edges. That deletion conclusion has a different target: a bipartite graph need not be complete bipartite. These fully read results are the direct comparisons. A supporting analytical theorem, independently reviewed in this study, establishes $D(G)\le15\xi$ for every finite simple triangle-free graph and, when $\lambda(G)>0$, $D(G)\le3\xi+18\sqrt{6}\,\xi^{3/2}/\lambda(G)$. Its proof cuts along the signs of a least-eigenvalue eigenvector, applies the published bipartite editing lemma, and uses the triangle-free trace identity $\operatorname{tr}(A^3)=0$ to control the gap between the extreme eigenvalue magnitudes. Consequently, for any sequence with positive deficit and $\xi/e(G)\to0$, one has $\limsup D(G)/\xi\le3$. The proof handles disconnected graphs, isolates, zero deficit and the empty graph. Historical priority of this supporting result is not claimed. The supporting argument can be stated explicitly. For $m>0$, write the least adjacency eigenvalue as $-\mu$, with $0<\mu\le\lambda$. Retain only edges between opposite nonzero signs of a unit eigenvector for $-\mu$, obtaining a bipartite graph $F$ after $b$ deletions. The absolute value of that vector has Rayleigh quotient at least $\mu$ in $F$. Hence $D(G)\le b+D(F)\le3(m-\mu^2)-2b\le3(m-\mu^2)$. Since $\operatorname{tr}(A^3)=0$ and $\operatorname{tr}(A^2)=2m$, $\lambda^3\le\mu(2m-\lambda^2)$. With $r=\lambda^2/m\in(0,1]$, this implies $m-\mu^2\le\xi(r^2+4)/(2-r)^2\le5\xi$. Put $\delta=\lambda^2-\mu^2\le4\xi$. After removing one occurrence of each extreme eigenvalue, the remaining squared eigenvalues sum to $2\xi+\delta\le6\xi$. Their cubed absolute values sum to at most $(6\xi)^{3/2}$, so the trace-cube identity gives $\lambda\delta\le\lambda^3-\mu^3\le(6\xi)^{3/2}$. Substitution proves both bounds. When $m=0$, both $D$ and $\xi$ vanish. The same reviewed evidence proves $D(C_5)=3$ exactly, with $e(C_5)-\lambda(C_5)^2=1$. Thus the optimal universal coefficient lies between three and fifteen. This five-cycle witness does not establish asymptotic sharpness when the relative deficit tends to zero. The bounded attempt on the exact statement leaves its universal coefficient-three conclusion unresolved. The signed-cut argument provides a concrete entry point, but its remaining spectral-gap and editing-slack terms have not been uniformly cancelled. This unresolved calculation is not a proof of a limitation of the method, and exploratory numerics are not used as support for the question.

Resolution criteria

A proof must establish the stated inequality for every finite simple triangle-free graph, allowing disconnected graphs and isolated vertices and counting both edge additions and deletions in $D(G)$. A disproof must give a finite simple triangle-free graph and rigorously certify $D(G)>3(e(G)-\lambda(G)^2)$. Numerical eigenvalues or an upper bound on $D(G)$ alone do not certify a counterexample.

Formal statement

1. Version 1 · current · added 26 Oct 2026 by the author, qurore

   https://github.com/exactory/exactory-math/blob/7194c5784dba0cfe43dd5951f65e62f1b9c9456e/problems/triangle-free-spectral-stability/formal/Challenge.lean

   Proof targets: TriangleFreeEdit.editDistance_le_three_deficit

   Lean v4.35.0 with Mathlib v4.35.0 (commit 56a005855ea17e0b0958f73ec801ae140b0a1679). In the folder of the file, run `lake exe cache get` and `lake build`; the theorem is stated with `sorry`. To judge a solution, add it as the module `Solution` and run `lake comparator` (Linux with bubblewrap); `comparator.json` names the theorem and the permitted axioms propext, Quot.sound and Classical.choice. Definitions: `editDistance G` is the minimum of |E(G) symmetric difference E(K_{S,T})| over pairs of disjoint finite vertex sets, empty sets allowed; `spectralRadius G` is the largest absolute value of an eigenvalue of the real adjacency matrix (0 without vertices), which equals the largest eigenvalue; `G.CliqueFree 3` means triangle-free. Keep `by exact editCosts_nonempty G` in `editDistance`: under the module system an inline proof becomes a private lemma named after the module, and the comparator then reports a mismatch.

Citations

1. Yongtao Li, Hong Liu, Shengtong Zhang. Edge-spectral Turán theorems for color-critical graphs with applications
2. Yongtao Li, Hong Liu, Shengtong Zhang. An edge-spectral Erdős-Stone-Simonovits theorem and its stability
3. Yuantian Yu, Huihui Zhang, Minjie Zhang. A survey of edge-spectral-Turán type problems in spectral graph theory: Results, conjectures and open problems
4. Yongtao Li. An entropy bridge from weighted to spectral Turán theorems
5. Yongtao Li, Lele Liu, Bo Ning. The spectral Erdős book theorem: sharp bounds and stability
6. V. Nikiforov. On a theorem of Nosal

Linked papers

No linked papers. An account links a paper with the plugin, with exactory link-problem-paper, or when it submits the paper, with exactory submit --math-problem.

Context links

• Proof attempt: paper, Lean project and numerical checkscontext
  https://github.com/exactory/exactory-math/tree/main/attempts/triangle-free-spectral-stabilityLinked 26 Oct 2026 by qurore

Status

The status is open, as it was when the problem was posted. The problem's author or an admin declares a status with the plugin: exactory declare-status.