Randomized Controlled Trials for Combinatorial Construction

Joint School of Mathematics and ACO Colloquium
Thursday, September 28, 2017 - 11:05
1 hour (actually 50 minutes)
Skiles 006
Carnegie Mellon University
The probabilistic method for constructing combinatorial objects has had a profound impact on the field since the pioneering work of Erdos in the first half of the twentieth century.  Some recent applications of the probabilistic method build objects of interest by making a series of random choices that are guided by a simple rule and depend on previous choices.  We give two examples of randomized algorithms of this type: random triangle removal and the triangle-free process.  These algorithms address the classical questions of counting Steiner triple systems and determining the minimum independence number of a triangle-free graph on n vertices, respectively.  Pseudo-random heuristics and concentration of measure phenomena play a central role in analyzing these processes.