Nov 3, 3:30pm, Wean 8220

Patrick Bennett, CMU

A natural barrier in random greedy hypergraph matching

Patrick Bennett, CMU

A natural barrier in random greedy hypergraph matching

Abstract:

Let r be a fixed constant and let H be an r-uniform, D-regular hypergraph
on N vertices. Assume further that D tends to infinity as N tends to infinity and that co-degrees of
pairs of vertices in H are at most L where L = o(D / log^5 N). We consider
the
random greedy algorithm for forming a matching in H. We choose a matching
at random by iteratively choosing edges uniformly at random to be in the
matching and deleting all edges that share at least one vertex with a chosen
edge before moving on to the next choice. This process terminates when there
are no edges remaining in the graph. We show that with high probability the
proportion of vertices of H that are not saturated by the final matching is
at
most (L/D)^[1/2(r-1) + o(1)]. This point is a natural barrier in the
analysis of the
random greedy hypergraph matching process.

Joint work with Tom Bohman.