Supersaturation: Cliques and Positive Square Energy

arXiv:2610.40570 · math.CO · Submitted 2026-10-29 · Read on arXiv

math.CO

Submitted: 2026-10-29

Updated: 2026-10-29

Comments: Comments are welcome

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: Let G be a simple graph of order n and let k r denote the number of unlabeled copies of K r in G.

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 at least2, we prove that, as n to infinity [ sqrt s+ > (1- 1r)n k r+1 at least (1 r r-1-o r(1))n r-1.] The coefficient r-(r-1) is asymptotically best possible; in particular, the triangle case gives k 3 at least 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.

Related papers