Combinatorics Seminar

When: Sunday, November 9, 10am Where: Schreiber 309 Speaker: Guy Wolfovitz, University of Haifa Title: Lower bounds for the size of maximal H-free graphs

Abstract:

For a fixed graph H, let the H-free process be defined as follows. Traverse the edges of the complete graph over the vertex set [n], according to the order imposed by a uniformly random permutation. Each traversed edge is added to an (initially empty) evolving graph over the vertex set [n], unless its addition creates a copy of H. Denote by M_n(H) the graph thus produced.

In this talk we describe an analysis of the above process for graphs H that are regular, strictly 2-balanced. The analysis implies a lower bound on the expected number of edges in M_n(H). In turn, this implies some new lower bounds for Turan numbers of complete, balanced bipartite graphs K_{r,r}, for r > 4. We will also mention some other new results concerning H-free processes.