Abstract:The hypergraph regularity lemma -- the extension of Szemeredi's graph regularity lemma to the setting of $k$-uniform hypergraphs -- is one of the most celebrated combinatorial results obtained in the ...The hypergraph regularity lemma -- the extension of Szemeredi'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-Rodl-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.
We show that such Ackermann-type bounds are unavoidable for every $k \ge 2$, thus confirming a prediction of Tao. Prior to our work, the only result of this type was Gowers' famous lower bound for graph regularity.Read More
Publication Year: 2018
Publication Date: 2018-04-16
Language: en
Type: preprint
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot