The lower boundary of the $\{K_2,K_{p},K_{q}\}$-profile
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
Authors
- Grigoriy Blekherman (ORCID: https://orcid.org/0000-0003-1845-4062)
- Annie Raymond (ORCID: https://orcid.org/0000-0002-3577-7624)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16140
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint