Supersaturation: Cliques and Positive Square Energy
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality