OpenAlex ·
Sharp edge-spectral supersaturation for odd cycles
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.08077
- Original
- Read it at the publisher
- Topics
Abstract
Let \(G\) be a graph with \(m\) edges and adjacency spectral radius\(ρ(G)\), and let \(N(C_{2k+1},G)\) denote the number of copies of \(C_{2k+1}\) in \(G\). For each fixed integer \(k\ge 2\), define \( g_k(m):=\frac{k-1+\sqrt{4m-k^2+1}}{2}. \) Li, Zhai and Shu [European J. Combin., 2024] determined the spectral extremal threshold for odd cycles by proving that, for all sufficiently large \(m\), every \(C_{2k+1}\)-free graph \(G\) with \(m\) edges satisfies \(ρ(G)\le g_k(m)\). We establish the asymptotically sharp supersaturation counterpart of their result. More precisely, for every fixed integer \(k\ge 2\), we prove that \[ \inf_{\substack{e(G)=m\\ ρ(G)>g_k(m)}} \frac{N(C_{2k+1},G)}{m^k} = \frac{\lceil k^2/2\rceil (k-1)!}{(k+1)^k}+o(1) \qquad\text{as }m\to\infty. \] Thus every \(m\)-edge graph whose spectral radius exceeds the \(C_{2k+1}\)-free threshold contains at least \[ \Big( \frac{\lceil k^2/2\rceil (k-1)!}{(k+1)^k}-o(1) \Big)m^k \] copies of \(C_{2k+1}\), and the leading constant is asymptotically best possible. In particular, taking \(k=2\), we obtain if \( ρ(G)>\frac{1+\sqrt{4m-3}}{2}\) then \( N(C_5,G)\ge \left(\frac{2}{9}-o(1)\right)m^2, \) with the constant \(2/9\) being asymptotically optimal. This answers a question of Chen, Li and Tang concerning the existence and the largest possible value of a constant \(C>0\) for which the same spectral condition guarantees at least \(Cm^2\) copies of \(C_5\). More generally, our result resolves a recent problem of Li, Lin, Liu and Zhang on spectral supersaturation for odd cycles. The proof combines spectral stability and resolvent analysis with estimates for odd spectral moments and a careful treatment of non-injective closed walks.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
A $(\log n)^{1/4}$ Bound for the Komlós Problem
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Sharp Metric Cotype Inequalities for $L_1$ via Nonlinear Cut Smoothing
Infinite Families of Counterexamples to a Conjecture of Liu and Qian and a Refined Inverse Theorem for Restricted Sumsets in $\mathbb{Z}_p$
Syzygy Transformations of Cluster Characters and Geometric Twists
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.