Recognition: no theorem link
The Bollob\'{a}s--Nikiforov Conjecture for Complete Multipartite Graphs and Dense K₄-Free Graphs
Pith reviewed 2026-05-14 22:41 UTC · model grok-4.3
The pith
The Bollobás–Nikiforov conjecture on the sum of the two largest eigenvalue squares holds for complete multipartite graphs with more vertices than parts and for dense K4-free graphs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove the Bollobás–Nikiforov conjecture for all complete multipartite graphs K_{n1,…,nr} with n1 + ⋯ + nr > r. The proof computes the full spectrum via a secular equation, establishes that λ2 = 0 whenever the graph has more vertices than parts, and then applies Nikiforov's spectral Turán theorem; equality holds if and only if all parts have equal size. We also prove a stability result for K4-free graphs whose spectral radius is near the Turán maximum: such graphs are structurally close to the balanced complete tripartite graph, and as a consequence the conjecture holds for all K4-free graphs with m = Ω(n²) when n is sufficiently large. Finally, we identify the precise obstruction to a Hof
What carries the argument
The secular equation that determines the eigenvalues of the adjacency matrix of a complete multipartite graph, together with the vanishing of λ2 when the number of vertices exceeds the number of parts.
If this is right
- The conjecture holds for every complete multipartite graph satisfying the vertex-part condition.
- Equality in the bound is attained precisely when all partite sets have equal size.
- Dense K4-free graphs with spectral radius near the Turán maximum satisfy the conjecture for all sufficiently large n.
- The structural stability near the balanced complete tripartite graph explains why the spectral bound holds in the dense K4-free case.
Where Pith is reading between the lines
- Similar stability methods might extend the conjecture to graphs forbidding larger cliques if one can control the distance to the corresponding Turán graph.
- The explicit secular-equation spectrum may apply to other families of graphs with equitable partitions, yielding eigenvalue bounds in those classes.
- Any counterexample to the full conjecture must avoid both the multipartite class and the dense K4-free regime.
Load-bearing premise
That the graphs under consideration are either complete multipartite with more vertices than parts or K4-free graphs whose spectral radius is sufficiently close to the Turán maximum so that the stability argument applies.
What would settle it
A complete multipartite graph with more vertices than parts in which λ1² + λ2² exceeds 2(1 − 1/ω)m, or a dense K4-free graph with m = Ω(n²) that violates the inequality while remaining structurally close to the balanced tripartite Turán graph.
read the original abstract
The Bollob\'as--Nikiforov conjecture asserts that for any graph $G \neq K_n$ with $m$ edges and clique number $\omega(G)$, \[ \lambda_1^2(G) + \lambda_2^2(G) \;\leq\; 2\!\left(1 - \frac{1}{\omega(G)}\right)m, \] where $\lambda_1(G) \geq \lambda_2(G) \geq \cdots \geq \lambda_n(G)$ are the adjacency eigenvalues of $G$. We prove the conjecture for all complete multipartite graphs $K_{n_1,\ldots,n_r}$ with $n_1 + \cdots + n_r > r$. The proof computes the full spectrum via a secular equation, establishes that $\lambda_2 = 0$ whenever the graph has more vertices than parts, and then applies Nikiforov's spectral Tur\'an theorem; equality holds if and only if all parts have equal size. We also prove a stability result for $K_4$-free graphs whose spectral radius is near the Tur\'an maximum: such graphs are structurally close to the balanced complete tripartite graph, and as a consequence the conjecture holds for all $K_4$-free graphs with $m = \Omega(n^2)$ when $n$ is sufficiently large. Finally, we identify the precise obstruction preventing a Hoffman-bound approach from settling the conjecture for $K_4$-free graphs with independence number $\alpha(G) \geq n/3$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves the Bollobás-Nikiforov conjecture for all complete multipartite graphs K_{n_1,…,n_r} with n_1+⋯+n_r > r. The argument computes the full adjacency spectrum via a secular equation, shows that λ_2 vanishes whenever the number of vertices exceeds the number of parts, and applies Nikiforov’s spectral Turán theorem; equality holds precisely when all parts are equal. It further proves a quantitative stability result showing that K_4-free graphs whose spectral radius is sufficiently close to λ(T(n,3)) are structurally close to the balanced complete tripartite graph, which implies the conjecture for all K_4-free graphs with m=Ω(n²) on sufficiently large n. The paper also identifies the precise obstruction that prevents a Hoffman-bound approach from settling the conjecture when α(G)≥n/3.
Significance. If the derivations hold, the paper supplies a concrete advance on the Bollobás-Nikiforov conjecture by settling it for the entire family of complete multipartite graphs satisfying the vertex-part condition and for all sufficiently dense K_4-free graphs. The explicit secular-equation spectrum calculation, the clean characterization of equality cases, and the stability theorem near the Turán extremal are technically strong and self-contained; they rely only on standard equitable-partition and interlacing facts together with Nikiforov’s prior result. These contributions are proportionate to the difficulty of the conjecture and furnish reusable tools for further spectral Turán-type problems.
minor comments (3)
- [§2] §2, secular-equation derivation: the presentation assumes the parts are ordered n_1 ≥ ⋯ ≥ n_r without stating whether the spectrum formulas remain valid without this ordering; a one-sentence clarification would remove any ambiguity.
- [Theorem 1.3] Theorem 1.3 (stability statement): the quantitative bound on the edit distance to the balanced tripartite graph is stated in terms of λ_1(G)−λ(T(n,3)), but the dependence on n is not made fully explicit in the theorem statement itself; moving the O(·) term into the displayed statement would improve readability.
- [Abstract] Abstract, final sentence: the phrase “dense K_4-free graphs” is used without the quantitative density condition m=Ω(n²); adding a parenthetical reference to the asymptotic regime would align the abstract more closely with the main theorem.
Simulated Author's Rebuttal
We thank the referee for the careful and accurate summary of our results on the Bollobás-Nikiforov conjecture for complete multipartite graphs and dense K4-free graphs, as well as for the positive recommendation of minor revision. The report correctly captures the spectral computation via the secular equation, the application of Nikiforov's theorem, the stability result, and the discussion of the Hoffman-bound obstruction.
Circularity Check
No significant circularity in derivation chain
full rationale
The paper's central proof for complete multipartite graphs computes the spectrum explicitly via a secular equation derived from the equitable partition and characteristic polynomial, independently establishing λ₂ = 0 when n > r. It then invokes Nikiforov's prior spectral Turán theorem (an external result, not a self-citation by the same author) to bound the expression. The stability argument for dense K₄-free graphs uses standard interlacing and quantitative perturbation bounds around the Turán graph T(n,3), without fitting parameters to the target inequality or redefining quantities by construction. No load-bearing step reduces the claimed inequality to a fitted input, self-citation chain, or ansatz smuggled from prior work; the derivations remain self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Adjacency eigenvalues of graphs with equitable partitions satisfy a secular equation derived from the quotient matrix
- standard math Nikiforov's spectral Turán theorem holds for any graph
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.