Combinatorics Seminar

When: Sunday, December 27, 10am
Where: Schreiber 309
Speaker: Po-Shen Loh, Carnegie Mellon University
Title: The Matching-Number Process


The matching number of a graph G is the maximum number \nu for which there exists a set of \nu vertex-disjoint edges contained in G. Let the k-matching process on n vertices be defined as follows: generate a uniformly random permutation of the \binom{n}{2} potential edges. Initially, start with n vertices and no edges. Process the potential edges one at a time, in the order that they appear in the permutation. If at a given iteration, the addition of that edge to the current graph would not increase its matching number above k, then add that edge. We prove that for k = o(n), asymptotically almost surely this process terminates with a graph which consists of some k vertices that are adjacent to all other vertices (including each other), and nothing more. This precisely matches the extremal construction in the classical Erdős-Gallai bound on the maximum number of edges in an n-vertex graph with matching number at most k, in this regime k = o(n).

Joint work with Michael Krivelevich and Benny Sudakov.