Matchings in the hypercube with specified edges

Abstract

Given a matching $M$ in the hypercube $Q^n$, the \emph{profile} of $M$ is the vector $\mathbf{x}=(x_1,\dots ,x_n)\in {\mathbb{N}}^n$ such that $M$ contains $x_i$ edges whose endpoints differ in the $i$th coordinate. If $M$ is a perfect matching, then it is clear that $||\mathbf{x}|{|}_1=2^{n-1}$ and it is easy to show that each $x_i$ must be even. Verifying a special case of a conjecture of Balister, Győri, and Schelp, we show that these conditions are also sufficient.

7 pages, added references to solution of Conjecture 3.2