= Perfect matching criterion for a regular pair with minimum degree
Let $(X,Y)$ be a <regular pair of vertex sets> with parameter $\epsilon$, equal class sizes $n$, density greater than $\epsilon$, and every vertex having at least $\epsilon n$ neighbors across the pair. Then it has a <perfect matching>. To prove <Hall's marriage theorem>[Hall's condition], take $S\subseteq X$. If $0<|S|\leq\epsilon n$, one vertex already supplies at least $|S|$ neighbors. If $\epsilon n<|S|\leq(1-\epsilon)n$ and $|N(S)|<|S|$, the two large sets $S$ and $Y\setminus N(S)$ have density zero, contradicting <regular pair of vertex sets>[regularity] and the positive density surplus. Finally, if $|S|>(1-\epsilon)n$, every vertex of $Y$ has a neighbor in $S$, so $N(S)=Y$. The empty subset satisfies Hall's condition directly.
Back to article page
