Randomness in High-Dimensional Combinatorics: Colorings, Robustness, and Statistics

Graphs are discrete mathematical structures that model pairwise relations between objects, and they are fundamental to combinatorics. From a geometric / topological viewpoint, they are one-dimensional objects. The pursuit of a higher-dimensional theory of many graph theoretic concepts has been a fruitful area of research. In the last half century, the introduction of the probabilistic method has had a tremendous impact on this area, and the study of randomness will be central to this project. This project will focus on developing a high-dimensional version of graph embeddings and decompositions. Graduate and undergraduate students will be trained as part of this project. The primary focus of this proposal is embeddings in and decompositions of graphs and hypergraphs, with a particular emphasis on problems in “high-dimensional combinatorics”. Hypergraph embeddings and decompositions are a central concern in modern combinatorics but also include some of the oldest combinatorial problems. For example, the famous “Knights Tour” problem, studied in the 9th century, and the “Icosian Game” of the 1800s, are both embedding problems. Both can be understood as the problem of finding a Hamilton cycle in a particular graph. Some of the most famous and influential combinatorial questions from the eighteenth and nineteenth century on Latin squares and combinatorial designs are now understood as hypergraph decomposition problems. Goals of this project include (1) using randomness to prove new embedding and decomposition results (2) proving "robust" versions of these results using the recently introduced notion of "spreadness" and (3) investigating statistical aspects of random combinatorial designs. 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.