The ACO Seminar (2025–2026)

We will consider the problem of writing an arbitrary graph as an edge-disjoint union of complete bipartite graphs, and its natural generalization to hypergraphs. At a very high level, the question at hand is to what extent we can summarize complicated structures by decomposing them into very structured pieces. I will present several optimal asymptotic bounds and algorithms, with applications to graph compression, SAT solving, cryptographic secret sharing, and approximations for the densest subgraph problem. More concretely, our main result is 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), gives the best upper bound for some secret sharing questions, and answers several 40-year-old questions of Chung, Erdős, and Spencer (1983). The heart of our proof is a simple idea from word combinatorics, which allows us to balance the number of d-cliques each vertex belongs to. This talk is based on joint work with Andrew Krapivin, Benjamin Przybocki, and Nicolás Sanhueza-Matamala.