Optimal d-Clique Decompositions for Hypergraphs.

Abstract: 

We determine the optimal constant for the Erdős-Pyber theorem on hypergraphs. Namely, we prove that every n-vertex d-uniform hypergraph H can be written as the union of a family F of complete d-partite hypergraphs such that every vertex of H belongs to at most (n choose d)/(n lg n) graphs in F. This improves on results of Csirmaz, Ligeti, and Tardos (2014), and answers an old question of Chung, Erdős, and Spencer (1983). Our proofs yield several algorithmic consequences, such as an O(n lg n) algorithm to find large balanced bicliques near the Kővári-Sós-Turán threshold. Moreover, we show that biclique partitions provide a combinatorial representation for graphs that is information-theoretically optimal for each density. This representation allows for speed-ups on several graph queries, and a subcuadratic approximation algorithm for the densest subgraph problem.

Posted on Nov 3, 2025 in ACGO, Seminars