Applications and Theory of the Algorithmic Hypergraph Regularity Method

在组合学中，人们经常考虑图和超图，它们是用于对对象之间的成对和成组关系进行建模的数学结构。 这些对象的应用出现在数学、计算机科学和自然科学的许多分支中。 在某些情况下，当这些对象具有准随机属性时，它可能非常有用。 因此，拟随机图和超图理论构成了现代组合学的一个很好的研究领域。这里重要和适用的结果包括正则引理，保证所有的大型图和超图承认分解成相对较少的部分，其中大部分这些部分是准随机的。 此外，还已知可以有效地构造这些分解。 建设性正则引理形成了该奖项支持的研究的主要领域。 PI研究算法（超图）正则性引理在理论计算机科学中产生的构造性组合问题中的应用。 此外，研究提出，几个不同的理论，拟随机超图基本上是可互换的，这将说，特别是，他们都是建设性的。 这些项目和其他项目将有助于图论，组合学和理论计算机科学中现有的和长期研究的基于正则性的基础设施。 这些项目还作为大型城市大学现任研究人员指导活动的基础，这些资金有助于支持在该领域工作的公立学生。 Szemeredi正则性引理（1975）保证了所有的大型图G可以被划分成许多类，其中大多数类是ε-正则的，并且类的数量只取决于ε的选择。 四十多年来，这一结果在组合数学中具有很大的影响力和影响力，其各种用途被称为正则性方法。 Szemeredi的正则性引理在重要方面得到了扩展。 由于阿隆等人的一个扩展。给出了一个多项式时间算法来构造它保证的分区。 其他工作由几个作者将其扩展到超图设置，其中出现的分区必然是技术性的，并在不同的作者认为不同的观点。 Rodl等人考虑了r-差异的概念，而Gowers考虑了偏差的概念。 PI，Rodl和Schacht最近的工作表明，基于偏差的正则性引理可以是建设性的。该项目旨在表明差异和偏差的基本概念本质上是等价的，因此这两个正则引理都可以被算法化。 (This已知对于3-一致超图来说是正确的，其中差异和偏差也等价于第三个概念，称为极小性。） PI还考虑了上述工作在几个建设性组合问题中的一些应用，包括超图的着色，包装和测试问题等。

In combinatorics, one often considers graphs and hypergraphs, which are mathematical structures used to model pairwise and group-wise relations among objects. Applications of these objects then appear in many branches of mathematics, computer science, and the natural sciences. In some settings, it can be very useful when these objects possess quasirandom properties. As such, quasirandom graph and hypergraph theory constitutes a well-studied area of modern combinatorics. Important and applicable results here include Regularity Lemmas, which guarantee that all large graphs and hypergraphs admit decompositions into relatively few parts, where most of these parts are quasirandom. Moreover, it is also known that these decompositions can be efficiently constructed. Constructive regularity lemmas form the primary area of the research supported by this award. the PI studies applications of algorithmic (hypergraph) regularity lemmas to constructive combinatorial problems arising in theoretical computer science. Moreover, the research proposes that several distinct theories of quasirandom hypergraphs are essentially interchangeable, which would say, in particular, that all of them are constructive. These projects, and others, will contribute to an existing and long-studied regularity-based infrastructure within graph theory, combinatorics, and theoretical computer science. These projects also serve as a basis for the mentoring activities of the current researcher at a large metropolitan university, and the funds help to support public students working in this area. The Szemeredi Regularity Lemma (1975) guarantees that all large graphs G can be partitioned into a number of classes, where most of these classes are epsilon-regular, and where the number of classes depends only on the choice of epsilon. For over four decades, this result has been highly impactful and influential in Combinatorics, and its varied use became known as the Regularity Method. Szemeredi's Regularity Lemma was extended in important ways. One extension due to Alon et al. gives a polynomial-time algorithm for constructing the partition it guarantees. Other work by several authors extended it to a hypergraph setting, where the partitions which arise are necessarily technical, and where different authors considered different points of view. Rodl et al. considered a concept of r-discrepancy, while Gowers considered a concept of deviation. Recent work of the PI, Rodl and Schacht showed that the deviation-based Regularity Lemma can be made constructive. The project seeks to show that the underlying concepts of discrepancy and deviation are essentially equivalent, and therefore both regularity lemmas can be made algorithmic. (This is known to be true for 3-uniform hypergraphs, where discrepancy and deviation are also equivalent to a third concept known as minimality.) The PI also considers a handful of applications of the work above to several constructive combinatorial problems, including coloring, packing, and testing problems for hypergraphs, among others.