Supersaturation: Cliques and Positive Square Energy
Let $G$ be a simple graph of order $n$ and let $k_r$ denote the number of unlabeled copies of $K_r$ in $G$. Let $s^+$ denote the sum of the squares of the positive adjacency eigenvalues of $G$. For every fixed integer $r\geq2$, we prove that, as $n \to \infty$ \[ \sqrt{s^+}>\left(1-\frac1r\right)n \quad\Longrightarrow\quad k_{r+1}\geq \left(\frac1{r^{r-1}}-o_r(1)\right)n^{r-1}. \] The coefficient $r^{-(r-1)}$ is asymptotically best possible; in particular, the triangle case gives $k_3\geq n/2-o(n)$. The proof combines positive square energy stability, the clique removal lemma, and a sharp clique count around a maximum $r$-cut. The triangle case requires an additional block-matrix argument.
Authors
- Shivaramakrishna Pragada
- M. Rajesh Kannan (ORCID: https://orcid.org/0000-0001-8038-1795)
- Abhay Jayarajan
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-10-29
- DOI
- https://doi.org/10.48550/arxiv.2610.40570
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint