Is It Easy to Regularize a Hypergraph With Easy Links?

Abstract A partition of a (hyper)graph is $\varepsilon $-homogeneous if the edge densities between almost all clusters are either at most $\varepsilon $ or at least $1-\varepsilon $. Suppose a $3$-graph has the property that the link of every vertex has an $\varepsilon $-homogeneous partition of size $\textrm{poly}(1/\varepsilon )$. Does this guarantee that the $3$-graph also has a small homogeneous partition? Terry and Wolf proved that such a $3$-graph has an $\varepsilon $-homogeneous partition of size given by a wowzer-type function. Terry recently improved this to a double exponential bound, and conjectured that this bound is tight. Our first result in this paper disproves this conjecture by giving an improved (single) exponential bound, which is best possible. We further obtain an analogous result for $k$-graphs of all uniformities $k \geqslant 3$. The above problem is part of a much broader programme, which seeks to understand the conditions under which a (hyper)graph has small $\varepsilon $-regular partitions. While this problem is fairly well understood for graphs, the situation is (as always) much more involved already for $3$-graphs. For example, it is natural to ask if one can strengthen our first result by only requiring each link to have $\varepsilon $-regular partitions of size $\textrm{poly}(1/\varepsilon )$. Our second result shows that surprisingly the answer is “no”, namely, a $3$-graph might only have regular partitions of tower-type size, even though the link of every vertex has an $\varepsilon $-regular partition of polynomial size.