A Tight Bound for Hypergraph Regularity II

The hypergraph regularity lemma – the extension of Szemer'edi’s graph regularity lemma to the setting of $k$-uniform hypergraphs – is one of the most celebrated combinatorial results obtained in the past decade. By now there are several (very different) proofs of this lemma, obtained by Gowers, by Nagle-R"odl-Schacht-Skokan and by Tao. Unfortunately, what all these proofs have in common is that they yield regular partitions whose order is given by the $k$-th Ackermann function. In a recent paper we have shown that these bounds are unavoidable for $3$-uniform hypergraphs. In this paper we extend this result by showing that such Ackermann-type bounds are unavoidable for every $k\ge 2$, thus confirming a prediction of Tao.