2024/10/07 by Chao, Ting-Wei, Dong, Zichao, Shen, Zijun +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2410.04744
Suppose 0 < p ≤ ∞. For a simple graph G with a vertex-degree sequence d1, …, dn satisfying (d1p + … + dnp)1/p ≤ C, we prove asymptotically sharp upper bounds on the number of t-cliques in G. This result bridges the p = 1 case, which is the notable Kruskal--Katona theorem, and the p = ∞ case, known as the Gan--Loh--Sudakov conjecture, and resolved by Chase. In particular, we demonstrate that the extremal construction exhibits a dichotomy between a single clique and multiple cliques at p0 = t - 1. Our proof employs the entropy method.