Matching Extendability in Hypercubes

Abstract

In a bipartite graph G, a set $S\subseteq V(G)$ is deficient if $|N(S)|<|S|$. A matching M (with vertex set U) is k-suitable if $G-U$ has no deficient set of size less than k. Let $f_k(d)$ be the largest r such that in the d-dimensional hypercube $Q_d$ every k-suitable matching with at most r edges extends to a perfect matching. We generalize results of Limaye and Sarvate by proving that $f_k(d)=k(d-k)+\binom{k-1}{2}$ for $k\leq d-3$. To this end we prove lower bounds on the sizes of neighborhoods of vertex sets in $Q_d$. We also prove that every induced matching in $Q_d$ extends to a perfect matching.