Combinatorics Seminar
When: Sunday, December 27, 10am
Where: Schreiber 309
Speaker: Po-Shen Loh, Carnegie Mellon University
Title: The Matching-Number Process
Abstract:
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.