2012/11/19 by Hao Huang, Nati Linial, Huang, Hao +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1211.4532
openalex publication_date 2012/11/19 · arxiv created 2013/12/08 · arxiv updated 2013/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let r, s >= 2 be integers. Suppose that the number of blue r-cliques in a red/blue coloring of the edges of the complete graph Kn is known and fixed. What is the largest possible number of red s-cliques under this assumption? The well known Kruskal-Katona theorem answers this question for r=2 or s=2. Using the shifting technique from extremal set theory together with some analytical arguments, we resolve this problem in general and prove that in the extremal coloring either the blue edges or the red edges form a clique.