The proposed research focuses on an interplay between deterministic combinatorial structures and random combinatorial structures. Szemer'edi's regularity lemma, a central component in this interaction, asserts that every graph can be decomposed into constantly many random-like subgraphs. From this random-like behavior provided by Szemer'edi's lemma, one may find and enumerate subgraphs of a fixed isomorphism type, culminating in what is known as the regularity method for graphs. This method has 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 method for graphs to uniform hypergraphs, and in turn, provides alternative proofs to some well-known partition 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 algorithmic extensions of the hypergraph regularity method. Such extensions would deepen our understanding of quasi-random hypergraph theory and further the reach of the current hypergraph regularity method as an applicable tool in combinatorial mathematics.
Combinatorics provides a principle mathematical foundation for computer 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 would provide an important tool for solving algorithmic questions concerning hypergraphs. The PI will investigate such an algorithmic extension and will consider some of its applications to problems in computer science.
