Clique supersaturation under a chromatic constraint below the Turán threshold

Abstract

A central theme in extremal graph theory is the supersaturation problem, which investigates the minimum number of copies of a target subgraph forced by prescribed edge conditions. This line of research goes back to Rademacher and Erdős for triangles, and was later extended to cliques by Lovász and Simonovits in the regime above the Turán threshold. Mubayi further extended this theory to color-critical graphs. Below the Turán threshold, a closely related existence-threshold phenomenon arises in the non-$p$-partite setting: a classical result of Brouwer shows that, for $n\ge 2p+1$, every $n$-vertex non-$p$-partite $K_{p+1}$-free graph has at most $e(T_{n,p})-\lfloor n/p\rfloor +1$ edges. Motivated by this threshold, we investigate a sharp clique-counting problem below the Turán threshold under the non-$p$-partite assumption. Let $p\ge 2$ and $s\ge 1$ be fixed integers. Let $Y_{n,p,s}$ be the graph obtained from $T_{n,p}$ by adding an edge inside a largest part and deleting all but $s$ of the edges from one endpoint of this new edge to a smallest part. Then $e(Y_{n,p,s})=e(T_{n,p})-\lfloor n/p\rfloor +s+1$. We prove that, for all sufficiently large $n$, every $n$-vertex non-$p$-partite graph $G$ with $e(G)\ge e(Y_{n,p,s})$ contains at least as many copies of $K_{p+1}$ as $Y_{n,p,s}$ does. The bound is sharp, as it is attained by the construction $Y_{n,p,s}$. Thus our result provides the exact clique-counting analogue of Brouwer's threshold for non-$p$-partite $K_{p+1}$-free graphs.

arXiv commentThe manuscript contains 17 pages and 1 figure. No external auxiliary files or extra arXiv citations are included within this comment