no. 14 · Friday 13 November 2026
The lower boundary of the $\{K_2,K_{p},K_{q}\}$-profile
Abstract
We determine the asymptotically sharp minimum number of $q$-cliques that appear in any $n$-vertex graph with $γn^2$ edges and $δn^{p}$ $p$-cliques for $q>p>2$. The question of determining the minimum number of $r$-cliques that appear in any $n$-vertex graph with $γn^2$ edges was previously resolved by Razborov for $r=3$, Nikiforov for $r=4$ and Reiher for all $r\geq 5$. For all $r\geq 3$, the minimum is attained by a complete multipartite graph where all parts are equal except for one that can be smaller or by a limit of such graphs. Very recently, Ma, Wang and Zhu as well as Li, Liu and Zhang showed that the same construction is also a minimizer for the number of $r$-cliques when the number of $s$-cliques is fixed for any $2\leq s<r$. A minimizer in our setting is the disjoint union of the same complete multipartite graph with an independent set. This establishes the lower boundary of the three-dimensional $\{K_2, K_p, K_q\}$-profile.
- comments
- 33 pages, 1 figure
- fields
- Combinatorics