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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The lower boundary of the $\{K_2,K_{p},K_{q}\}$-profile

Grigoriy Blekherman, Annie Raymond
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

The lower boundary of the $\{K_2,K_{p},K_{q}\}$-profile

Grigoriy Blekherman, Annie Raymond
preprint en

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

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon