Extending matchings in the hypercube to perfect matchings
by
Jennifer Vandenbussche
University of Illinois at Urbana-Champaign
Coauthors: Douglas B. West

In 1996, Limaye and Sarvate proved that a matching of size at most d in the d-dimensional hypercube extends to a perfect matching if and only if it does not cover the neighborhood of an uncovered vertex. In this talk, we generalize and strengthen their result by studying Hall's Condition in the graph that remains when the endpoints of a matching are removed from Q_d.

Let f_k(d) be the minimum size of a matching M with vertex set U that does not extend to a perfect matching in Q_d even though Q_d-U does not contain a deficient set (in the sense of Hall's Theorem) of size less than k. The Limaye-Sarvate Theorem can be restated as f₁(d) = d and f₂(d) ≥ d+1. We prove that f_k(d) > k(d-k) when d ≥ k, and we give a construction to show that f₂(d) = 2d-3. A generalization of the construction provides a general upper bound on f_k(d), and we conjecture that this upper bound is sharp when d > k+2.

Date received: April 8, 2008