Hypergraph regularity algorithms and applications

点击翻译按钮获取中文摘要

The PI proposes algorithmic versions of the recent hypergraph regularity methods of Rodl, Schacht, Skokan and the PI, and of Gowers. For graphs, Szemeredi's Regularity Lemma was made algorithmic by Alon, Duke, Lefmann, Rodl and Yuster. For 3-uniform hypergraphs, Haxell, Rodl and the PI established an algorithmic hypergraph regularity lemma (compatible with a counting lemma). Using this work, Poerschke, Rodl, Schacht and the PI derived algorithmic 3-uniform versions of Gowers' regularity lemma and that of Frankl and Rodl. The PI proposes algorithmic k-uniform versions of each of these regularity lemmas. Moreover, the PI proposes that the three concepts of regularity considered by these sets of authors are all equivalent, which plays an important role in the development of the desired algorithm. It also plays an important role in the applications of such algorithmic regularity lemmas, since then it follows that all three regularity lemmas admit a corresponding counting lemma. The PI then proposes work on several algorithmic hypergraph problems. Hypergraph regularity methods have lead to important solutions to quite a few problems across the areas of extremal combinatorics, theoretical computer science, number theory and discrete geometry. These methods have, in a strong sense, provided a general infrastructure for solving certain problems. An algorithmic version of the hypergraph regularity method would expand that infrastructure to constructive procedures for solving algorithmic hypergraph problems.