Applications and Theory of the Algorithmic Hypergraph Regularity Method

在组合学中，人们经常考虑图和超图，它们是用于对对象之间的成对和群明智关系建模的数学结构。这些对象的应用随后出现在数学、计算机科学和自然科学的许多分支中。在某些情况下，当这些对象具有准随机属性时，它可能非常有用。因此，准随机图和超图理论构成了现代组合学中一个研究得很好的领域。这里重要和适用的结果包括正则引理，它保证所有大图和超图都可以分解成相对较少的部分，其中大多数部分是准随机的。此外，我们还知道，这些分解可以有效地构造。建设性规则引理构成了该奖项支持的研究的主要领域。PI研究算法（超图）正则引理在理论计算机科学中的构造组合问题中的应用。此外，研究提出了几个不同的准随机超图理论本质上是可互换的，这将特别地说，所有这些理论都是建设性的。这些项目和其他项目将为图论、组合学和理论计算机科学中现有的、长期研究的基于规则的基础设施做出贡献。这些项目也为目前大城市大学的研究人员的指导活动提供了基础，这些资金有助于支持在这一领域工作的公立学生。Szemeredi正则引理（1975）保证了所有的大图G可以被划分成许多类，其中大多数类是正则的，并且类的数量只取决于选择的。四十多年来，这个结果在组合学中非常有影响力和影响力，它的各种用途被称为正则方法。Szemeredi的正则性引理得到了重要的推广。Alon等人的一个扩展给出了一个多项式时间算法来构造它所保证的分区。其他几位作者的工作将其扩展到超图设置，其中出现的分区是必要的技术，并且不同的作者考虑不同的观点。Rodl等人考虑了r-差异的概念，而Gowers则考虑了偏差的概念。PI、Rodl和Schacht最近的工作表明，基于偏差的正则引理可以是建设性的。该项目旨在表明差异和偏差的基本概念本质上是等价的，因此两个规则引理都可以通过算法来实现。（这对于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.