pith. sign in

arxiv: 2604.17242 · v1 · submitted 2026-04-19 · 🧮 math.CO

Generalized spectral Tur\'an problems for disjoint cliques

Yi Xu , Yi-Zheng Fan This is my paper

Pith reviewed 2026-05-10 06:25 UTC · model grok-4.3

classification 🧮 math.CO
keywords generalized Turán numberspectral radiusdisjoint cliquesclique tensorTurán graphextremal graph theory
0
0 comments X

The pith

If an n-vertex kK_{r+1}-free graph maximizes the t-clique spectral radius, then for large n it is the join of K_{k-1} with the r-partite Turán graph T_r(n-k+1).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the structure of the n-vertex graph that avoids k disjoint copies of K_{r+1} yet attains the largest t-clique spectral radius. It proves this graph must be formed by joining a clique on k-1 vertices to the balanced complete r-partite graph on the remaining vertices. A reader would care because the same construction is already known to maximize the number of K_t copies, so the result shows the counting extremal graph is also extremal for the associated tensor eigenvalue. The case t=2 recovers the maximum adjacency spectral radius for the same forbidden subgraph.

Core claim

The paper proves that among all kK_{r+1}-free graphs on n vertices, the maximizer of the t-clique spectral radius is, for every sufficiently large n, the graph obtained by joining a complete graph on k-1 vertices to the r-partite Turán graph T_r(n-k+1). This supplies the spectral analogue of Gerbner's theorem on the maximum number of K_t copies in a kK_{r+1}-free graph.

What carries the argument

The t-clique tensor of a graph, a higher-order array whose entries count ordered t-cliques and whose largest eigenvalue defines the t-clique spectral radius.

If this is right

  • The same graph that maximizes the number of K_t copies also maximizes the t-clique spectral radius.
  • When t=2 the result reduces to the maximum adjacency spectral radius of kK_{r+1}-free graphs, recovering the theorem of Ni, Wang, and Kang.
  • The extremal graph for the spectral problem is unique for all large n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Stability techniques used for the counting version may transfer directly to the spectral setting.
  • The result suggests that many generalized Turán problems admit the same extremal graph for both counting and spectral-radius formulations.
  • One could compute the exact asymptotic value of the maximum t-clique spectral radius from the known structure of the join graph.

Load-bearing premise

That n is large enough for the unique maximizer to be exactly the stated join of K_{k-1} with T_r(n-k+1).

What would settle it

A kK_{r+1}-free graph on sufficiently large n whose t-clique spectral radius is strictly larger than that of K_{k-1} joined to T_r(n-k+1).

read the original abstract

The generalized Tur\'an number $\text{ex}(n, H, F)$ denotes the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Let $kK_{r+1}$ be the disjoint union of $k$ copies of the complete graph $K_{r+1}$. Recently, Gerbner determined $\text{ex}(n, K_{t},kK_{r+1})$ for all sufficiently large $n$. In this paper, we study a spectral analogue of this problem via the $t$-clique tensor of a graph. We prove that if an $n$-vertex $kK_{r+1}$-free graph $G$ maximizes the $t$-clique spectral radius, then for sufficiently large $n$, $G$ is the join of a complete graph $K_{k-1}$ and the $r$-partite Tur\'an graph $T_{r}(n-k+1)$. This establishes a spectral counterpart of Gerbner's Theorem. Moreover, in the case $t=2$, our result recovers a theorem of Ni, Wang, and Kang on the maximum spectral radius of $kK_{r+1}$-free graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper proves a spectral analogue of Gerbner's theorem: for all sufficiently large n, the unique n-vertex kK_{r+1}-free graph maximizing the spectral radius of the t-clique tensor is the join K_{k-1} ∨ T_r(n-k+1). The result recovers the t=2 case of Ni-Wang-Kang as a corollary.

Significance. If the stability and eigenvalue arguments are complete, the work supplies a structural characterization that extends spectral Turán theory to generalized problems with forbidden disjoint cliques. It demonstrates that tensor-based spectral radii can detect the same extremal graphs as the corresponding generalized Turán numbers, which is a non-trivial bridge between the two theories.

major comments (1)
  1. [Proof of the main theorem] The central claim requires a stability lemma establishing that any graph not isomorphic to K_{k-1} ∨ T_r(n-k+1) has t-clique tensor spectral radius smaller by an amount that dominates the o(1) error terms arising from the tensor eigenvalue inequalities once n exceeds some N_0(r,k,t). The manuscript asserts existence of such an N_0 but supplies neither an explicit lower bound on the stability gap nor a concrete estimate for N_0, so it is impossible to confirm that the claimed gap is Ω(1) rather than merely o(1).
minor comments (1)
  1. [Introduction] The definition of the t-clique tensor and the precise notion of its spectral radius should be recalled in the introduction (or given a dedicated preliminary section) rather than deferred entirely to the references.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting this point in the proof of the main theorem. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Proof of the main theorem] The central claim requires a stability lemma establishing that any graph not isomorphic to K_{k-1} ∨ T_r(n-k+1) has t-clique tensor spectral radius smaller by an amount that dominates the o(1) error terms arising from the tensor eigenvalue inequalities once n exceeds some N_0(r,k,t). The manuscript asserts existence of such an N_0 but supplies neither an explicit lower bound on the stability gap nor a concrete estimate for N_0, so it is impossible to confirm that the claimed gap is Ω(1) rather than merely o(1).

    Authors: We agree that the current manuscript only asserts the existence of N_0(r,k,t) without supplying explicit constants or a concrete lower bound on the stability gap in the t-clique tensor spectral radius. The stability is inherited from Gerbner's theorem on the generalized Turán number ex(n,K_t,kK_{r+1}), which yields a positive gap in the number of K_t copies; this gap must then be translated through the tensor eigenvalue bounds, whose error terms are o(1) relative to the leading term. In the revised version we will add an explicit analysis: we derive a lower bound on the spectral-radius gap of the form c(r,k,t) > 0 (independent of n) that holds for all graphs sufficiently close in edit distance to the extremal graph, and we bound the eigenvalue inequalities with concrete O(1/n) or smaller remainders. Combining these yields an explicit (albeit possibly large) N_0(r,k,t) such that the stability gap strictly dominates the error terms for all n ≥ N_0. This makes the argument fully rigorous and addresses the referee's concern. revision: yes

Circularity Check

0 steps flagged

No circularity in the claimed spectral extension of Gerbner's theorem

full rationale

The paper states a direct proof that the unique maximizer of the t-clique tensor spectral radius among kK_{r+1}-free graphs is K_{k-1} ∨ T_r(n-k+1) for large n, recovering the t=2 case of Ni-Wang-Kang as a corollary. The derivation chain invokes Gerbner's combinatorial extremal result only as the candidate graph, then applies stability and eigenvalue-gap arguments whose details are asserted to be self-contained; no equation reduces by construction to a fitted parameter, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled via self-citation. The result is therefore independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definition of the t-clique tensor and its spectral radius together with the known structure of Turán graphs; no new free parameters or invented entities appear in the abstract.

axioms (1)
  • domain assumption The t-clique tensor of a graph is a well-defined symmetric tensor whose spectral radius is a continuous, monotone function of the number of t-cliques.
    Invoked when the paper replaces the ordinary Turán count with the spectral radius of this tensor.

pith-pipeline@v0.9.0 · 5512 in / 1363 out tokens · 58821 ms · 2026-05-10T06:25:11.275269+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    M. Chen, X. Zhang, Some new results and problems in spectral extremal graph theory, J. Anhui Univ. Nat. Sci., 42 (2018), 12–25. 1

    work page 2018

  2. [2]

    Chv´atal, D

    V . Chv´atal, D. Hanson, Degrees and matchings. J. Combin. Theory Ser. B , 20 (2) (1976), 128–138. 2, 2.8

    work page 1976

  3. [3]

    Cioab ˘a, D

    S. Cioab ˘a, D. N. Desai, M. Tait, The spectral even cycle problem, Combin. Theory, 4 (1) (2024), 10. 1

    work page 2024

  4. [4]

    Cioab ˘a, L

    S. Cioab ˘a, L. Feng, M. Tait, X. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Combin., 27 (4) (2020), P4.22. 2.9

    work page 2020

  5. [5]

    Cooper, A

    J. Cooper, A. Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl. , 436 (2012), 3268–3292. 1, 1

    work page 2012

  6. [6]

    L. Fang, H. Lin, Spectral extremal results on edge blow-up of graphs, Discrete Math., 349 (2) (2026), 114835. 1

    work page 2026

  7. [7]

    Friedland, S

    S. Friedland, S. Gaubert, L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438 (2013), 738–749. 2.1

    work page 2013

  8. [8]

    Gerbner, Some exact results for non-degenerate generalized Tur ´an problems, Electron

    D. Gerbner, Some exact results for non-degenerate generalized Tur ´an problems, Electron. J. Combin., 30(4)(2023), P4.39. 1, 1.2

    work page 2023

  9. [9]

    Gernber, Generalized Tur ´an results for disjoint cliques, Discrete Math., 347(7)(2024), 114024

    D. Gernber, Generalized Tur ´an results for disjoint cliques, Discrete Math., 347(7)(2024), 114024. 1, 1.2

    work page 2024

  10. [10]

    Gerbner, C

    D. Gerbner, C. Palmer, Survey of generalized Tur ´an problems - counting subgraphs, Electron. J. Combin., 2026, Dynamic Surveys, DS27. 1

    work page 2026

  11. [11]

    Khan, Y .-Z

    M. Khan, Y .-Z. Fan, On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs, Linear Algebra Appl., 480(2015), 93–106. 2.2

    work page 2015

  12. [12]

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

    work page 2022

  13. [13]

    L. Lim, Singular values and eigenvalues of tensors: a variational approach, 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing , 2005, 129–132. 1, 1.1

    work page 2005

  14. [14]

    Liu, Spectral generalized Tur ´an problems, arXiv:2507.21689

    X. Liu, Spectral generalized Tur ´an problems, arXiv:2507.21689. 1

    work page arXiv

  15. [15]

    C. Liu, C. Bu, On a generalization of the spectral Mantel’s theorem, J. Comb. Optim. , 46(2)(2023), 14. 1, 1, 1.2, 1, 1.4, 2, 2.4, 2.5

    work page 2023

  16. [16]

    C. Liu, C. Bu, A tensor’s spectral bound on the clique number, Discrete Math., 349 (2026), 114694. 2, 2.6

    work page 2026

  17. [17]

    R. Liu, L. Miao, Spectral Tur ´an problem of non-bipartite graphs: Forbidden books, European J. Combin., 126 (2025), 104136. 1

    work page 2025

  18. [18]

    L. Liu, B. Ning, A spectral analogue of Ore’s problem on Tur ´an theorem, Linear Algebra Appl., 735 (3) (2026), 112–122. 1

    work page 2026

  19. [19]

    Moon, On independent complete subgraphs in a graph, Canad

    J. Moon, On independent complete subgraphs in a graph, Canad. J. Math., 20(1968), 95–

    work page 1968

  20. [20]

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

    work page 2023

  21. [21]

    Nikiforov, Bounds on graph eigenvalues II,Linear Algebra Appl

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

    work page 2007

  22. [22]

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

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

    work page 2010

  23. [23]

    Qi, Eigenvalues of a real supersymmetric tensor, J

    L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symb. Comput. , 40 (2005), 1302–

    work page 2005

  24. [24]

    Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl

    L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl. , 439 (2013), 228–238. 1, 1.1

    work page 2013

  25. [25]

    Rehman, S

    A. Rehman, S. Pirzada, The spectral Tur ´an problem about graphs of given size with forbidden subgraphs, AKCE Int. J. Graphs Comb., 22 (1) (2025), 91–93. 1

    work page 2025

  26. [26]

    J. Shao, H. Shan, L. Zhang, On some properties of the determinants of tensors, Linear Algebra Appl., 439 (2013), 3057–3069. 2.3

    work page 2013

  27. [27]

    Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc

    M. Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq., Tihany, 1996), Academic Press, New York, 1968, 279–

    work page 1996

  28. [28]

    Tur ´an, On an extremal problem in graph theory, Mat

    P. Tur ´an, On an extremal problem in graph theory, Mat. Lapok, 48 (1941) 436–452. 1

    work page 1941

  29. [29]

    Z. Yan, B. Yang, Y . Peng, A spectral generalized Alon-Frankl theorem,Discrete Math., 349 (2) (2026), 114785. 1

    work page 2026

  30. [30]

    Y . Yang, Q. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl., 31 (2010), 2517–2530. 2.1

    work page 2010

  31. [31]

    Y . Yang, Q. Yang, On some properties of nonnegative weakly irreducible tensors, arXiv: 1111.0713v1. 2.1

    work page arXiv

  32. [32]

    L. Yu, Y . Peng, A spectral version of the theorem of Zykov and Erd˝os, Electron. J. Combin., 32 (4) (2025), 2517–2530. 1

    work page 2025

  33. [33]

    L. Yu, Y . Peng, A spectral generalized Erd˝os-Gallai theorem, Discrete Math., 349 (1) (2026), 114672. 1 21

    work page 2026

  34. [34]

    M. Zhai, M. Liu, Extremal problems on planar graphs without k edge-disjoint cycles, Adv. Appl. Math., 157 (2024), 102701. 1

    work page 2024

  35. [35]

    Zykov, On some properties of linear complexes, Matematicheskii Sbornik , 66(2) (1949), 163–188

    A.A. Zykov, On some properties of linear complexes, Matematicheskii Sbornik , 66(2) (1949), 163–188. 1, 1

    work page 1949