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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Supersaturation: Cliques and Positive Square Energy

Shivaramakrishna Pragada, M. Rajesh Kannan, Abhay Jayarajan
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

Supersaturation: Cliques and Positive Square Energy

Shivaramakrishna Pragada, M. Rajesh Kannan, Abhay Jayarajan
preprint en

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\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.

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon