Optimal and Efficient Partite Decompositions of Hypergraphs

We study the problem of partitioning the edges of a d-uniform hypergraph H into a family F of complete d-partite hypergraphs (d-cliques). We show that there is a partition F in which every vertex v ∈ V(H) belongs to at most (1/d! + od(1))nd−1/lgn members of F. This settles the central question of a line of research initiated by Erdős and Pyber (1997) for graphs, and more recently by Csirmaz, Ligeti, and Tardos (2014) for hypergraphs. The d=2 case of this theorem answers a 40-year-old question of Chung, Erdős, and Spencer (1983). An immediate corollary of our result is an improved upper bound for the maximum share size for binary secret sharing schemes on uniform hypergraphs.