Arithmetic Progressions and the Hypergraph Regularity Method

所提出的研究集中在确定性组合结构和随机组合结构之间的相互作用。Szemer的正则性引理是这种相互作用中的中心成分，它认为每个图都可以分解成许多连续的类随机的子图。从Szemer的EDI引理提供的这种类似随机的行为中，人们可以找到并计数固定同构类型的子图，最终达到所谓的图的正则性方法。这种方法在图论、组合几何、组合数论和理论计算机科学中都被证明是有用的。最近PI和合作者的工作发展了所谓的超图正则性方法，它将图的正则性方法推广到一致超图上，从而为最初由Szemer‘EDI，Furstenberg和Katznelson得到的一些著名的划分定理提供了另一种证明。超图正则性方法应该被证明对许多极值组合问题是有用的。PI将研究这些应用。PI还旨在开发超图正则化方法的结构和算法扩展。这些推广将加深我们对拟随机超图理论的理解，并进一步将当前的超图正则性方法作为组合数学中的一种实用工具。组合学为计算机科学，特别是理论计算机科学提供了基本的数学基础。计算机科学中的许多困难问题反过来又寻求有效的算法来解决或估计基于组合的问题的解。Szemer的正则性引理的算法版本(在Szemer的EDI证明原文10多年后发展起来)将许多用图正则性方法证明的存在结果转化为相应算法问题的构造性解决方案。特别是，图正则性方法对于理论计算机科学中重要的性质测试领域是非常有价值的。超图正则性方法的完全算法版本将为解决有关超图的算法问题提供一个重要的工具。PI将研究这样的算法扩展，并将考虑其在计算机科学问题中的一些应用。

The proposed research focuses on an interplay between deterministic combinatorial structures andrandom combinatorial structures. Szemer\'edi's regularity lemma, acentral component in this interaction, assertsthat every graph can be decomposed into constantly many random-like subgraphs. Fromthis random-like behavior provided by Szemer\'edi's lemma, one may find and enumerate subgraphsof a fixed isomorphism type, culminating in what is known as the regularitymethod for graphs. This methodhas proved useful in graph theory, combinatorial geometry, combinatorial number theory and theoretical computer science. Recent work of the PI and collaborators developed the so-called hypergraph regularity method which extends the regularity methodfor graphs to uniform hypergraphs, and in turn, provides alternative proofs to some well-knownpartition theorems originally due to Szemer\'edi, Furstenberg and Katznelson. The hypergraph regularity method should prove useful to many extremal combinatorial problems.The PI will investigate such applications. The PI also aims to develop structural and algorithmicextensions of the hypergraph regularity method. Such extensions would deepen our understanding of quasi-random hypergraph theoryand further the reach of the current hypergraph regularity methodas an applicable tool in combinatorial mathematics. Combinatorics provides a principle mathematical foundation forcomputer science, and in particular, theoretical computer science. Many difficult problems in computer science, in turn, seek efficient algorithms for solving or estimating solutions to combinatorially-based problems. The algorithmic version of Szemer\'edi's regularity lemma (developed more than 10 years after Szemer\'edi proved the original) transforms many existential results proved by the graph regularity method into constructive solutions to corresponding algorithmic questions.In particular, graph regularity methods have proved invaluable to the area of property testing, important in theoretical computer science. A fully algorithmic version of the hypergraph regularity method wouldprovide an important tool for solving algorithmic questionsconcerning hypergraphs. The PI will investigate such an algorithmic extension and willconsider some of its applications to problems in computer science.