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 P V(H) belongs to at most ( 1 d! + o d (1))n d´1 / lg n members of F . Together with a simple information-theoretic lower bound, 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). Furthermore, our construction is algorithmically efficient: such optimal partitions can be constructed in time O(n d /d!). An immediate corollary of our result is an improved upper bound for the maximum share size for binary secret sharing schemes on uniform hypergraphs.

Building on results of Nechiporuk (1969), we prove that every graph with fixed edge density γ P (0, 1) has a biclique partition of total weight at most ( 1 2 + o(1)) ¨h2 (γ) n 2 lg n , where h 2 is the binary entropy function. This result is asymptotically tight and answers a further question of Chung, Erdős, and Spencer. Our construction implies that such biclique partitions can be constructed in time O(m), which answers a question of Feder and Motwani (1995) and also improves upon results of Mubayi and Turán (2010) as well as Chavan, Rabinia, Grosu, and Brocanelli (2025). Using similar techniques, we also give an n 1+o(1) algorithm for finding a subgraph K t,t with t = (1 ´o(1)) γ h 2 (γ) lg n, which matches the celebrated Kővári-S ós-Turán guarantee for small γ.

Our results show that biclique partitions are information-theoretically optimal representations for graphs at every fixed density, which makes them a natural succinct data structure. We show that with this succinct representation one can answer independent set queries and cut queries in time O(n 2 / lg n); prior work of Bansal, Williams, and Vassilevska Williams gave subquadratic algorithms for independent set queries at the cost of ω(n 2 ) preprocessing. We also show that if we increase the space usage by a constant factor, we can compute a modification of Charikar's 2-approximation algorithm for the densest subgraph problem that runs in time O(n 2 / lg α) and gives a 2α-approximation for any α ą 1, thus establishing the first approximation guarantees that can be obtained in subquadratic time.

Finally, we show that graphs with polynomially bounded shattering, a class including graphs of bounded VC-dimension, admit biclique partitions of weight O(n 2´1/(d+1) ), where d is the shattering exponent, which extends recent results of Cardinal and Yuditsky (2025).