Applications and Theory of the Algorithmic Hypergraph Regularity Method

University Of South Florida, Tampa FL

Investigators

Abstract

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.