2024/12/07 by József Balogh, Jialin He, Balogh, József +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Commutative Algebra and Its Applications #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2412.05522
In 1966, Erdős, Goodman, and Pósa showed that if G is an n-vertex graph, then at most \lfloor n2/4 \rfloor cliques of G are needed to cover the edges of G, and the bound is best possible as witnessed by the balanced complete bipartite graph. This was generalized independently by Győri--Kostochka, Kahn, and Chung, who showed that every n-vertex graph admits an edge-decomposition into cliques of total `cost' at most 2 \lfloor n2/4 \rfloor, where an i-vertex clique has cost i. Erdős suggested the following strengthening: every n-vertex graph admits an edge-decomposition into cliques of total cost at most \lfloor n2/4 \rfloor, where now an i-vertex clique has cost i-1. We prove fractional relaxations and asymptotically optimal versions of both this conjecture and a conjecture of Dau, Milenkovic, and Puleo on covering the t-vertex cliques of a graph instead of the edges. Our proofs introduce a general framework for these problems using Zykov symmetrization, the Frankl-Rödl nibble method, and the Szemerédi Regularity Lemma.