Arithmetic Progressions and the Hypergraph Regularity Method

点击翻译按钮获取中文摘要

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.