Pseudorandom Structures in Graphs and Combinatorics

Miami University, Oxford OH

Investigators

Abstract

Many combinatorial problems in mathematics are motivated by numerous practical applications in computer science and network design such as partitioning, covering, packing, sequencing, routing, clustering, sorting, and degree constrained spanning trees. These problems can arise from studying either physical structures such as optical networks or more abstract structures such as social networks. Broadly speaking, the PI seeks to better understand the mathematical structures (graphs, directed/oriented graphs, hypergraphs, designs) at the heart of these problems by exploiting the dichotomy between order and randomness. Furthermore, this project will provide research opportunities for undergraduate and masters students. The PI and his collaborators will explore new territory in Ramsey theory and Dirac/Hajnal-Szemerédi theory. In Ramsey theory we are given a mathematical structure (say a collection of sets) and we want to know under what circumstances is it true that no matter how the structure is partitioned into smaller parts, one of those smaller parts must contain a desired substructure. Dirac/Hajnal-Szemerédi theory is about the study of sufficient conditions which guarantee the existence of certain spanning substructures within a host structure. In both settings the goal is to find a desired substructure and in both settings the PI's goal is to develop general methods for doing so. These methods will typically have the following flavor: either the host structure is highly ordered in some sense or else has psuedorandom properties which can be exploited to build a robust "scaffolding" which can in turn be used to construct the desired substructure. The PI will build upon a body of work including fractional relaxations, regularity, expansion (and various other measures of psuedorandomness), and absorption. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.