Supersaturation: Cliques and Positive Square Energy

Abstract

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\ge 2$, 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\ge 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.

arXiv commentComments are welcome