Random Processes and Constrained Combinatorial Structures

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

This project aims to use randomized algorithms to address the fundamental combinatorial problem of constructing interesting objects, counting such objects, and studying their (typical) structure. Beginning in the mid-twentieth century, the use of randomness and the probabilistic method revolutionized the combinatorialist's toolbox. More recently, the application of randomized processes has facilitated many breakthroughs and landmark results. The study and use of these processes has deep connections to functional analysis, entropy theory, and discrete probability. By nature, the use of these processes also opens the door to computer experimentation. As such, many aspects of this project are suitable for collaboration with students of all levels. One focus of the project is the study of graphs and hypergraphs where, in the standard random models, different constraints compete at the same scale. For instance, consider Latin squares, that is, n x n matrices in which every row and column is a permutation of the symbols {1,2,...,n}. It is straightforward to verify that if one chooses each symbol independently and uniformly at random then in each row and column, a constant fraction of the symbols will be repeated. For this reason (and others), probabilistic constructions of Latin squares proved challenging. Nevertheless, recent advances allowed the use of sophisticated randomized algorithms in constructing Latin squares, which are but one example of the rich family of combinatorial designs. Despite this progress, many mysteries remain regarding even the most basic properties of random Latin squares (and related objects). For example, how many 2x2 Latin subsquares does a typical random order-n Latin square have? A second focus of the project is the study of threshold phenomena in random hypergraphs. Of particular interest is characterizing at which densities random binomial graphs contain certain spanning structures, such as combinatorial designs. A recently proved connection between "fractional expectation-thresholds" and thresholds introduces an exciting avenue for using randomized constructions to prove threshold results. This project will develop and extend techniques based on randomized processes to answer these constructive, enumerative, and structural questions. 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.