Hypergraph regularity algorithms and applications

PI提出了Rodl、Schacht、Skokan和PI以及Gowers最近的超图正则性方法的算法版本。对于图，Szemeredi的正则引理是由Alon， Duke, Lefmann， Rodl和Yuster提出的算法。对于3-均匀超图，Haxell， Rodl和PI建立了一个算法超图正则引理（与计数引理兼容）。利用这项工作，Poerschke, Rodl， Schacht和PI推导出了Gowers的正则引理和Frankl和Rodl的正则引理的算法3-uniform版本。PI提出了这些规律性引理的k-一致算法版本。此外，PI提出了这些作者集合所考虑的三个正则性概念都是等价的，这在期望算法的发展中起着重要作用。它在这类算法正则引理的应用中也起着重要的作用，因为它可以得出所有三个正则引理都承认一个相应的计数引理。PI随后提出了几个算法超图问题的研究工作。超图正则性方法已经为极值组合学、理论计算机科学、数论和离散几何等领域的许多问题提供了重要的解决方案。这些方法在很大程度上提供了解决某些问题的通用基础结构。超图正则性方法的算法版本将把该基础结构扩展为解决算法超图问题的建设性程序。

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.