Arithmetic Progressions and the Hypergraph Regularity Method

本文提出的研究重点是确定性组合结构和随机组合结构之间的相互作用。Szemer\'edi的正则引理是这种相互作用的中心成分，它断言每个图都可以分解成不断地许多随机子图。从Szemer 'edi引理提供的这种随机行为中，人们可以找到并列举出固定同构类型的子图，最终形成所谓的图的正则性方法。该方法已被证明在图论、组合几何、组合数论和理论计算机科学中是有用的。PI和合作者最近的工作发展了所谓的超图正则性方法，将图的正则性方法扩展到一致超图，并反过来为最初由Szemer\'edi， Furstenberg和Katznelson提出的一些著名的划分定理提供了替代证明。超图正则性方法对许多极值组合问题是有用的。PI将调查此类申请。PI还旨在开发超图正则性方法的结构和算法扩展。这样的扩展将加深我们对拟随机超图理论的理解，并进一步扩大当前超图正则性方法在组合数学中的应用范围。组合学为计算机科学，特别是理论计算机科学提供了一个基本的数学基础。反过来，计算机科学中的许多难题寻求有效的算法来解决或估计基于组合的问题的解。Szemer\'edi正则引理的算法版本（在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.