Strict spectral supersaturation for cliques: extremal graphs and sharp thresholds

@misc{wu2026strict,
  title = {{Strict spectral supersaturation for cliques: extremal graphs and sharp thresholds}},
  author = {Qi Wu and Yong Lu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.03337},
  eprint = {2610.03337},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.03337},
  note = {CC0},
}

TY  - UNPB
TI  - Strict spectral supersaturation for cliques: extremal graphs and sharp thresholds
AU  - Qi Wu
AU  - Yong Lu
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.03337
UR  - https://arxiv.org/abs/2610.03337
AB  - For every fixed r≥3 and all sufficiently large n, we determine the largest adjacency spectral radius of an n-vertex graph with fewer than q c_r(n) copies of K_r+1, where 1≤ q<n/r. Here c_r(n) is the number of copies created by adding one edge to a largest part of the Turán graph. We also determine all extremal graphs. In most cases the extremal graph is obtained from an almost balanced complete multipartite graph by adding a star in one part. Two small values of q require separate constructions, and an additional transition occurs when r=3 and n≡2pmod3. Under the non-strict constraint, the unique extremal graph is obtained by adding a q-edge star to a largest part of the Turán graph. We determine the difference between the strict and non-strict values and prove that the sharp matching threshold is √2(r−1)/r. The proof treats separately the ranges q=o(n), q/m→γ∈(0,1), and q/m→1.
ER  -