A sharp fixed-size spectral bound for $kK_3$-free graphs

Joyentanuj Das; Yamini V

REVIEW 2 major objections 4 minor 21 references

A sharp fixed-size spectral bound for $kK_3$-free graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read For every fixed $k$, every sufficiently large $kK_3$-free graph with $m$ edges has spectral radius at most $(k-1)+\sqrt{m-k(k-1)}$, and the bound is attained exactly by a $(2k-1)$-clique joined to an independent set.

desk verdict Sharp fixed-size spectral bound for k disjoint triangles, with a genuinely second-order proof; solid modulo a minor constant slip in Lemma 8. read the letter →

arxiv 2608.05869 v1 pith:JB6KKTGL submitted 2026-08-06 math.CO

Joyentanuj Das , Yamini V This is my paper · ORCID

classification math.CO MSC 05C5005C35

keywords spectralradiusBrualdi–Hoffman–TuránproblemTurándisjointtrianglesPerron–FrobeniustheoremextremalgraphtheoryfixedsizekK3-freegraphs

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 proves a sharp, fixed-size spectral bound for graphs containing no $k$ vertex-disjoint triangles: for every fixed $k\ge2$ and all sufficiently many edges $m$, the adjacency spectral radius $\lambda(G)$ is at most $(k-1)+\sqrt{m-k(k-1)}$. Equality holds exactly when $2k-1$ divides $m$ and the graph is, up to isolated vertices, the join of a clique of size $2k-1$ with an independent set of size $m/(2k-1)-(k-1)$. This settles the Brualdi-Hoffman-Tur\'an problem for $kK_3$-free graphs for every fixed $k$, and it shows that the fixed-size extremal structure differs from the known fixed-order extremal graph. The proof is an induction on $k$ built on exact second-order structure rather than on first-order spectral stability, which is shown to be too weak because a near-extremal family lies only $\Theta(m^{-1/2})$ below the target.

What carries the argument

The central mechanism is an exact defect identity attached to a vertex $u^*$ of maximum Perron coordinate. Splitting the vertices into $A=N(u^*)$, $B=V\setminus N[u^*]$, and then into a high-degree core $C$ and a low-degree part $L$, the identity (Lemma 8) expresses the slack in the spectral inequality as a sum of six nonnegative defect terms whose total is bounded by $\binom{q}{2}$, where $q=|C|-2(k-1)$. When $q=0$ all defects vanish and the extremal join structure emerges; when $q>0$ the defect bound is converted, via a missing-Perron-mass argument and the Erd\H{o}s-Gallai matching theorem, into a bounded outer layer $B$, a finite core, and eventually a contradiction by constructing $k$ disjoint triangles. A cone-exclusion claim, proved from the inductive hypothesis, guarantees that $G-u^*$ itself contains $k-1$ disjoint triangles, seeding the reduction.

What would settle it

Exhibit, for some fixed $k\ge3$, an infinite family of $kK_3$-free graphs with $m$ edges whose spectral radius exceeds $(k-1)+\sqrt{m-k(k-1)}$ by a positive amount that does not vanish as $m$ grows (or even by a positive multiple of $m^{-1/2}$). Alternatively, find any $m\ge M_0(k)$ with $2k-1\nmid m$ and a $kK_3$-free graph attaining the bound, since the theorem declares the bound strict in every nondivisible residue class.

Watch

Extended reading notes

Core claim

For any integer $k\ge2$ there is a threshold $M_0(k)$ such that every $kK_3$-free graph with $m\ge M_0(k)$ edges satisfies $\lambda(G)\le(k-1)+\sqrt{m-k(k-1)}$. The bound is sharp exactly when $2k-1$ divides $m$: writing $q=m/(2k-1)-(k-1)$, the unique extremal graph up to isolated vertices is $K_{2k-1}\vee qK_1$, a $(2k-1)$-clique joined to an independent set of size $q$. The paper establishes this for all $k\ge3$ by induction from the known $k=2$ case. It derives an exact nonnegative defect identity at a maximum Perron vertex, uses it to bound the outer layer by a constant and reduce the graph to a bounded core with finitely many independent twin classes, then applies a Perron-vector concentration identity and the Erd\H{o}s-Gallai matching theorem to force the unique extremal core. The argument also shows that first-order spectral stability cannot settle the problem, because the family $K_{k-1}\vee K_{c,c}$ lies only $\Theta(m^{-1/2})$ below the target.

Load-bearing premise

The proof is an induction on $k$, so everything rests on the inductive hypothesis that the same bound already holds at level $k-1$, starting with the published $k=2$ base case; if that hypothesis fails, the cone-exclusion claim and the existence of $k-1$ disjoint triangles in $G-u^*$ can no longer be derived.

Editorial extensions

If this is right

For every fixed $k$ and all sufficiently large $m$, the extremal spectral radius of $kK_3$-free graphs with $m$ edges is exactly $(k-1)+\sqrt{m-k(k-1)}$ when $2k-1\mid m$, and strictly smaller otherwise.
The equality graph is unique up to isolated vertices: $K_{2k-1}\vee qK_1$ with $q=m/(2k-1)-(k-1)$.
The fixed-size extremal graph differs from the fixed-order extremal graph $K_{k-1}\vee T_{n-k+1,2}$, so the two problems have genuinely different answers.
The proof introduces a reusable reducing scheme---defect identity to bounded outer layer, then to a finite core with independent twin classes, then Perron-vector concentration, then matching theory---which may apply to other disconnected forbidden graphs.
Two open problems remain: the exact value for each residue class $m\pmod{2k-1}$, and the analogous fixed-size problem for $kK_s$-free graphs with $s\ge4$.

Reading between the lines

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

The defect-identity and bounded-core scheme seems likely to transfer to other fixed-size spectral problems where the forbidden family is a disjoint union of cliques or other matching-type graphs; the paper hints at this but does not claim it.
The $\Theta(m^{-1/2})$ gap suggests that any exact fixed-size spectral theorem for non-bipartite forbidden graphs will require second-order arguments of this kind, since first-order stability theorems are structurally insufficient.
The equality characterization implies a sharp spectral analogue of the Erd\H{o}s-Gallai matching bound in this setting: the clique of size $2k-1$ is exactly the largest core that can avoid $k$ disjoint triangles when the remainder is independent.
A testable extension is to compute the leading constant of the gap for nondivisible $m$; the method here already predicts the extremal graph will be a small perturbation of $K_{2k-1}\vee qK_1$, and the defect identity may yield the exact gap.

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

Bottom line: this is the real result. For every fixed k≥3 the paper proves the sharp m-edge spectral bound for kK3-free graphs and characterizes the extremal graphs as K_{2k-1} joined to an independent set. That was open for k≥3; only k=2 was known. It is not a routine extension. The proof is a genuine second-order analysis, and the near-extremal construction showing a Θ(m^{-1/2}) gap explains why first-order stability cannot do the job.

The main ingredients are the exact nonnegative defect identity (16), the bounded-outer-layer argument via missing Perron mass, the finite-core reduction with independent twin classes, and the Erdős–Gallai matching punchline. I checked the key algebra—the defect identity, Lemma 6's cone-exclusion cubic, and Lemma 10—and it is coherent. The induction on k is legitimate: the level-(k-1) bound is only invoked on subgraphs with enough edges, and the small-edge cases are handled separately. The equality characterization is complete, including the divisibility condition and isolated vertices. The exposition is long but modular; the intermediate lemmas carry enough data to be checked independently.

Soft spots are minor. The stress-test note is right about Lemma 8: the displayed C0=3r N_core is not implied by the preceding bounds; e(S_hi) ≤ binom(3r,2) and E_U ≤ 3r(N_core-1), so the sum can exceed C0. This is only a fixed O_r(1) threshold that needs to be large enough, so enlarging the constant repairs the proof without touching the induction. One limitation worth stating: M0(k) is recursive and non-explicit, so the theorem is a sufficiently-large statement. That is normal for the area, but worth knowing when citing.

The citation pattern is honest: the k=2 result by Wang, Jia and Ni is credited and used as base, and the fixed-order extremal structure is correctly distinguished from the fixed-size one. The paper also states plainly what it does not resolve—nondivisible sizes and higher cliques.

Who should read it: spectral extremal graph theorists, and anyone working on Brualdi–Hoffman–Turán problems for disconnected forbidden graphs. I would send it to a competent referee; it deserves serious reading rather than desk rejection, and I would accept it after the Lemma 8 constant is fixed.

Referee Report

2 major / 4 minor

Summary. The paper proves that for every fixed k≥2 and all sufficiently large m, every m-edge kK3-free graph G satisfies λ(G)≤(k−1)+sqrt(m−k(k−1)), with equality precisely when (2k−1) divides m and the nontrivial part of G is K_{2k−1} joined to an independent set. The proof is by induction on k, using the published k=2 result of Wang–Jia–Ni as the base. The core of the paper is a four-step reduction: a defect identity at a maximum Perron vertex, a bounded-outer-layer argument, a finite-core reduction via independent twin classes, and a matching-theoretic identification of the extremal core. The introduction also gives a nearly extremal family K_{k−1}∨K_{c,c} showing that the spectral gap from the target is only Θ(m^{−1/2}), which motivates the second-order analysis.

Significance. If the proof is correct, the result is a significant contribution to the fixed-size spectral Turán problem: it resolves the Brualdi–Hoffman–Turán problem for all disjoint-triangle families kK3, not just the k=2 base case, and it gives a complete equality characterization. The paper also makes a useful methodological point, namely that the fixed-size extremal graph differs structurally from the fixed-order extremal graph and that first-order spectral stability is insufficient at the O(√m) scale. The proof is modular and self-contained, and it leverages an exact defect identity and a finite-core/twin-class reduction that are genuinely nonstandard. The theorem is non-effective in the sense that M0(k) is defined recursively rather than explicitly, but this is consistent with the stated existence form of the result.

major comments (2)

[§3, Lemma 9] The proof of the bound |H|≤4D+r−1 contains an unjustified adjacency claim. The set H0 is defined as the set of vertices of H that are complete to W, but the subsequent triangle construction also requires every chosen h∈H0 to be adjacent to the fresh vertices of Z_W. The sentence “every required edge is present because u* and every vertex of H0 are complete to both W and Z_W” is not supported by the preceding argument: H0 was only shown complete to W, and vertices of Z_W have no demonstrated adjacency to vertices of B. Without the missing edge h−z, the triangles {h,w,z} used to force |H0|≤β−1 may fail, so the conclusion |B|≤8D+r−1 is not proved. This step is load-bearing because Lemma 10 defines the finite core K using |B|=O_r(1); the finite-core exclusion and the final contradiction for q>0 depend on it.
[§3, Lemma 10] The finite-core reduction assumes |B|=O_r(1) from Lemma 9. Since Lemma 9's bound is not established by the current proof (see the previous comment), the reduction to the bounded set K and the subsequent Perron-vector concentration argument do not currently go through for the q>0 case. This is the central gap in the inductive step for k≥3.

minor comments (4)

[§3, Lemma 8] The proof uses e(S_hi)+E_U≤C0 with C0=3rN_core, but (18) only gives E_U<3rN_core, while e(S_hi) can be as large as binom(3r,2). Thus the displayed C0 is not large enough for the displayed equality. This is a local technical slip: replacing C0 by binom(3r,2)+3rN_core (or any sufficiently large O_r(1) constant) preserves inequality (20) and all subsequent large-m arguments, since C0 is only used as a fixed constant.
[§3, Lemma 8(iv)] The sentence “By Lemma 1, at least 2r−1 edges are missing from G[W]” refers to the matching extremum result, which is Proposition 1 in the paper, not Lemma 1 (the edge-shifting lemma). Please correct the cross-reference.
[§3, Lemma 9] In the same lemma, the notation H0 is introduced without an explicit statement of its cardinality; the proof later asserts “all but at most 4D vertices of H are complete to W”, and it would help to label this set explicitly and to state |H0|≥|H|−4D before the packing argument.
[§1, Problem 2] The statement of Problem 2 says “s≥4”, while the preceding discussion of higher disjoint cliques uses kK_s with general s; the parameter naming is slightly confusing and should be aligned.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a well-founded induction over k with an external base, and no fitted parameter is relabeled as a prediction.

full rationale

The paper's derivation is self-contained given standard tools (Perron-Frobenius, Rayleigh quotient, the Wu-Xiao-Hong edge shift, and the Erdos-Gallai matching theorem) plus the external 2K3 base case of Wang, Jia, and Ni [18]. The only use of the level-(k-1) theorem is through Lemma 6's cone-exclusion claim, where the threshold M_cone(k-1) is fixed after M0(k-1) and before M0(k); the induction is therefore well-founded recursion, not circularity. No parameter is fitted to the target: the defect identity (16) is exact, its defect terms vanish only in the q=0 limit, and the target graph K_{2k-1} joined with an independent set is independently verified in Lemma 2 to satisfy the bound. The paper also does not rename a known result: it explicitly contrasts the fixed-size extremizer with the fixed-order extremizer and notes the k=2 case was already known. There is no load-bearing self-citation and no imported uniqueness theorem from the authors' prior work. The only small point I checked is the constant C0 in Lemma 8; the estimate is valid because e(S_hi)-sigma^2 is nonpositive, so the bound E_U <= C0 suffices. In any event, such a bounded-constant repair would concern correctness, not circularity. Overall, no circular step was found.

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

The proof introduces no fitted parameters and no invented entities. The central claim rests on standard tools (Perron-Frobenius, Rayleigh quotient, Erdos-Gallai matching theorem, Wu-Xiao-Hong edge-shifting lemma) and on the published k=2 base case. The recursive thresholds M_0(k) are existential and not fitted to data.

assumptions (5)

standard math Perron-Frobenius theorem for irreducible nonnegative matrices
Used to define the unique positive Perron vector of a connected graph and to justify the eigenequations throughout Section 3.
standard math Variational characterization of the spectral radius via Rayleigh quotient
Used in Lemma 1, Lemma 4, and the cone-exclusion claim to compare eigenvalues.
standard math Erdos-Gallai matching theorem
Used in Proposition 1 and Lemma 10 to bound edges in graphs with bounded matching number.
standard math Wu-Xiao-Hong edge-shifting lemma
Used in Lemma 4 and Lemma 6 to show extremal graphs are connected and to rule out vertices outside the neighborhood of the maximum-Perron vertex.
domain assumption Published k=2 base case of Wang, Jia, Ni [18]
The induction for k>=3 assumes the sharp 2K_3-free bound with equality characterization as its base case; this result is external to the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A sharp fixed-size spectral bound for $kK_3$-free graphs." pith.science (2026). https://pith.science/paper/JB6KKTGL

@misc{pith2026260805869,
  author       = {Pith},
  title        = {Pith review of: A sharp fixed-size spectral bound for $kK_3$-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JB6KKTGL}},
  note         = {Machine review of arXiv:2608.05869}
}

abstract

For a fixed integer $k\ge2$, we establish a sharp adjacency-spectral upper bound for sufficiently large $m$-edge $kK_3$-free graphs. We prove \[ \lambda(G)\le (k-1)+\sqrt{m-k(k-1)}. \] Moreover, equality holds precisely when $(2k-1)\mid m$ and, up to isolated vertices, $G$ is the join of $K_{2k-1}$ with an independent set of $m/(2k-1)-(k-1)$ vertices. The case $k=2$ was previously known; our argument establishes every fixed $k\ge3$. The proof requires information beyond first-order spectral stability. We derive an exact nonnegative defect identity at a maximum Perron vertex, use it to bound the entire outer layer by a constant, and reduce the remaining graph to a bounded core with finitely many independent twin classes. A Perron-vector concentration identity and the Erd\H{o}s--Gallai matching theorem then force the unique extremal core. A nearly extremal family lies only $\Theta(m^{-1/2})$ below the target, showing why an exact second-order analysis is necessary.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

[1]

Chen, A.-M

M.-Z. Chen, A.-M. Liu, X.-D. Zhang,Spectral extremal results forbidding linear forests, Graphs Combin. 35 (2) (2019) 335–351

work page 2019
[2]

Chen, A.-M

M.-Z. Chen, A.-M. Liu, X.-D. Zhang,On the spectral radius of graphs without a star forest, Discrete Math. 344 (4) (2021) 112269

work page 2021
[3]

Erd˝ os, T

P. Erd˝ os, T. Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356

work page 1959
[4]

L. Fang, H. Lin, M. Zhai,Stable structure and extremal eigenvalues of degenerate Tur´ an prob- lems, Discrete Math. 349 (2026) 115299

work page 2026
[5]

L. Feng, G. Yu, X.-D. Zhang,The spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (1) (2007) 133–138

work page 2007
[6]

X. Lei, S. Li,Spectral extremal problem on disjoint color-critical graphs, Electron. J. Combin. 31 (1) (2024)

work page 2024
[7]

S. Li, Y. Yu,Spectral extrema of graphs with fixed size: Forbidden triangles and pentagons, Discrete Math. 347 (11) (2024) 114151. 31

work page 2024
[8]

S. Li, S. Zhao, L. Zou,Spectral extrema of graphs with fixed size: Forbidden a fan graph, a friendship graph, or a theta graph, J. Graph Theory 110 (4) (2025) 483–495

work page 2025

Show all 21 references

[9]

X. Li, M. Zhai, J. Shu,A Brualdi–Hoffman–Tur´ an problem on cycles, European J. Combin. 120 (2024) 103966

2024
[10]

Y. Li, W. Liu, L. Feng,A survey on spectral conditions for some extremal graph problems, Adv. Math. (China) 51 (2) (2022) 193–258

2022
[11]

Y. Li, H. Liu, S. Zhang,An edge-spectral Erd˝ os–Stone–Simonovits theorem and its stability, arXiv:2508.15271, 2025

2025 arXiv
[12]

Y. Li, H. Liu, S. Zhang,Edge-spectral Tur´ an theorems for color-critical graphs with applica- tions, arXiv:2511.15431v2, 2025

2025
[13]

J. Lu, L. Lu, Y. Li,Spectral radius of graphs forbiddenC 7 orC △ 6 , Discrete Math. 347 (2) (2024) 113781

2024
[14]

Z. Ni, J. Wang, L. Kang,Spectral extremal graphs for disjoint cliques, Electron. J. Combin. 30 (1) (2023)

2023
[15]

Nikiforov,Bounds on graph eigenvalues II, Linear Algebra Appl

V. Nikiforov,Bounds on graph eigenvalues II, Linear Algebra Appl. 427 (2–3) (2007) 183–189

2007
[16]

Nikiforov,The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl

V. Nikiforov,The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (9) (2010) 2243–2256

2010
[17]

J. Wang, Z. Ni, L. Kang, Y. Fan,Spectral extremal graphs for edge blow-up of star forests, Discrete Math. 347 (10) (2024) 114141

2024
[18]

J. Wang, M. Jia, Z. Ni,On the spectral radius of2K 3-free graphs with fixed size, Discrete Appl. Math. 394 (2026) 1–8

2026
[19]

B. Wu, E. Xiao, Y. Hong,The spectral radius of trees onkpendant vertices, Linear Algebra Appl. 395 (2005) 343–349

2005
[20]

M. Zhai, H. Lin, J. Shu,Spectral extrema of graphs with fixed size: Cycles and complete bipartite graphs, European J. Combin. 95 (2021) 103322

2021
[21]

Zhang, L

Y. Zhang, L. Wang,Spectral extrema of graphs with fixed size: Forbidden star forests, Discrete Math. 349 (5) (2026) 114976. 32

2026

Pith tools

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

[1] [1]

Chen, A.-M

M.-Z. Chen, A.-M. Liu, X.-D. Zhang,Spectral extremal results forbidding linear forests, Graphs Combin. 35 (2) (2019) 335–351

work page 2019

[2] [2]

Chen, A.-M

M.-Z. Chen, A.-M. Liu, X.-D. Zhang,On the spectral radius of graphs without a star forest, Discrete Math. 344 (4) (2021) 112269

work page 2021

[3] [3]

Erd˝ os, T

P. Erd˝ os, T. Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356

work page 1959

[4] [4]

L. Fang, H. Lin, M. Zhai,Stable structure and extremal eigenvalues of degenerate Tur´ an prob- lems, Discrete Math. 349 (2026) 115299

work page 2026

[5] [5]

L. Feng, G. Yu, X.-D. Zhang,The spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (1) (2007) 133–138

work page 2007

[6] [6]

X. Lei, S. Li,Spectral extremal problem on disjoint color-critical graphs, Electron. J. Combin. 31 (1) (2024)

work page 2024

[7] [7]

S. Li, Y. Yu,Spectral extrema of graphs with fixed size: Forbidden triangles and pentagons, Discrete Math. 347 (11) (2024) 114151. 31

work page 2024

[8] [8]

S. Li, S. Zhao, L. Zou,Spectral extrema of graphs with fixed size: Forbidden a fan graph, a friendship graph, or a theta graph, J. Graph Theory 110 (4) (2025) 483–495

work page 2025