University of Delaware
Discrete Mathematics Seminar

Recent results on H-free processes
Michael Picollelli
University of Delaware
Tuesday, February 28, 2012
Ewing Hall 336 5.00 - 6.00 pm

Abstract: For a fixed graph H, the H-free process is a random graph process which constructs a maximal H-free graph with a random number of edges by means of a simple probabilistic greedy algorithm. Analysis of these processes has led to improved (asymptotic) lower bounds on a range of Ramsey and Turan numbers, and has suggested that the graphs produced at each step `look like' the classical random graph. In this talk, I will discuss some of these results, with a focus on the developments following Bohman's stunning analysis of the triangle-free process in 2008. Only basic knowledge of probability will be assumed.