Rutgers Discrete Mathematics Seminar

Title: Some recent results on H-free processes

Speaker: Michael Picollelli, Delaware

Date: Tuesday, April 3, 2012 2:00pm

Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ


The H-free process, for a fixed graph H, is the random graph process which starts with n isolated vertices and constructs a maximal H-free graph G_H by adding, at each step, a new edge chosen uniformly at random from those which do not create a copy of H. Recent work on these processes following Bohman's stunning analysis of the triangle-free process in 2008 has led to improved asymptotic lower bounds on a range of Ramsey and Turan numbers, and has suggested the graphs produced at each step resemble the classical Erdos-Renyi random graph (but without any copies of H!). This talk will discuss some of these results, with a focus on the case where H is a cycle - for which we now know the likely size and independence number of G_H to within constant factors.