***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Michael Simkin (Hebrew U.)

Thursday 4th October, 3:00 in Fine Hall 224.

Title: Perfect matchings in random subgraphs of regular bipartite graphs

The classical theory of Erdős–Rényi random graphs is concerned primarily 
with random subgraphs of K_n or K_{n,n}. Lately, there has been much
interest in understanding random subgraphs of other graph families, 
such as regular graphs.

We study the following problem: Let G be a k-regular bipartite graph with 2n
vertices. Consider the random process where, beginning with 2n isolated
vertices, G is reconstructed by adding its edges one by one in a uniformly
random order. An early result in the theory of random graphs states that if
G=K_{n,n}, then with high probability a perfect matching appears at the same
moment that the last isolated vertex disappears. We show that if k = Ω(n) then
this holds for any k-regular bipartite graph G. This improves on a result of
Goel, Kapralov, and Khanna, who showed that with high probability a perfect
matching appears after O(n log(n)) edges have been added to the graph. On the
other hand, if k = o(n / (log(n) log log(n))), we construct a family of
k-regular bipartite graphs in which isolated vertices disappear long before 
the appearance of perfect matchings.

Joint work with Roman Glebov and Zur Luria.

		----------------------------------

Next week: Jinyoung Park

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)