1 Introduction↩︎

Balister, Győri, and Schelp [1] considered the following partitioning problem: we are given a sequence \(\boldsymbol{d_1},\ldots, \boldsymbol{d_{2^{n-1}}}\) of elements of \(\mathbb{F}_2^n\) and our aim is to partition \(\mathbb{F}_2^n\) into pairs \(\{\boldsymbol{a_i},\boldsymbol{b_i}\}\) such that \(\boldsymbol{a_i} - \boldsymbol{b_i} = \boldsymbol{d_i}\) for each \(i \in \left[2^{n-1}\right]\). They noted that, since we are working over \(\mathbb{F}_2^n\), for such a partition \[\label{e:null} \sum_{i=1}^{2^{n-1}} \boldsymbol{d_i} = \sum_{i=1}^{2^{n-1}} \boldsymbol{a_i} - \boldsymbol{b_i} = \sum_{i=1}^{2^{n-1}} \boldsymbol{a_i} + \boldsymbol{b_i} = \sum_{\boldsymbol{v} \in \mathbb{F}_2^n} \boldsymbol{v} = \boldsymbol{0}.\tag{1}\] They conjectured that this necessary condition was also sufficient.

Similar problems of partitioning groups into pairs with prescribed differences have also been considered in \(\mathbb{F}_p\) for \(p>2\) prime [2], [3], \(\mathbb{F}_p^n\) [4] and cyclic groups [5].

Balister, Győri, and Schelp [1] showed that Conjecture 1 holds under certain assumptions on the differences \(\boldsymbol{d_i}\): namely if the first half of the differences are identical, and the second half come in identical pairs. More recently, Kovács [6], [7] gave further evidence towards Conjecture 1.

In this note we consider another natural restriction of Conjecture 1, where we insist that each difference \(\boldsymbol{d_i}\) must be some unit vector, i.e., of the form \(\boldsymbol{e_i}\) for some \(i\). We note that, since there are precisely \(n\) unit vectors, this is not quite covered by Theorem 2 [i:one]. In this case, Conjecture 1 has a simple reformulation in terms of matchings in the hypercube \(Q^n\).

Given a matching \(M \subseteq Q^n\) we say the profile of \(M\) is the vector \(\boldsymbol{x}=(x_1,\ldots, x_n) \in \mathbb{N}^n\) such that \(M\) contains \(x_i\) edges whose endpoints differ in the \(i\)th coordinate, and we are interested in which tuples \(\boldsymbol{x} \in \mathbb{N}^n\) are achievable as the profile of some matching. We call such tuples admissible. In this case, the obvious necessary condition for a tuple to be the profile of a perfect matching is that each unit vector appears an even number of times as a matching edge, i.e., each \(x_i\) is even, in which case we say that \(\boldsymbol{x}\) is even, and Conjecture 1 would imply that this condition is also sufficient. The aim of this short note is to verify the conjecture in this case. Let us call a tuple \(\boldsymbol{x} \in \mathbb{N}^n\) perfect if \(||\boldsymbol{x}||_1 := \sum_i x_i = 2^{n-1}\).

After distributing an initial version of the manuscript it was brought to the author’s attention, that Conjecture 1 and related questions have also been considered independently in other contexts. Firstly, in the setting of set-sequential trees where work of Golowich and Kim [8] shows that Conjecture 1 holds when there are at most \(n\) distinct \(\boldsymbol{d}_i\), which implies Theorem 3. Similar questions have also been considered in the context of batch codes in information theory, although a subtle difference here is that a solution to a request vector does not correspond to a matching in \(Q^d\), but rather a subgraph in which every vertex except the origin has degree at most one. In this setting, Wang, Kiah and Cassuto [9] and Wang, Kiah, Cassuto and Bruckner [10] prove a statement analogous, but not equivalent, to Theorem 3 using a very similar inductive argument. More recently Hollmann, Khathuria, Riet, and Skachek [11] observed that an old theorem of Hall [12] can be used to prove that certain codes are batch codes, and in particular a straightforward adaptation of their methods shows that Conjecture 1 holds in the case where all the vectors \(\boldsymbol{d_i}\) lie outside of some fixed hyperplane \(H\) (see [11]), which also implies Theorem 3. However, since we believe the reformulation in terms of matchings in \(Q^n\) leads to interesting questions (see Section 3), and our proof is short and simple, we hope the work in this note may still be of interest.

The structure of the paper is as follows. In Section 2 we prove Theorem 3 and in Section 3 we discuss some related questions.

2 Main result↩︎

We first note that by symmetry the ordering of the coordinates of \(\boldsymbol{x}\) is irrelevant, and so we may assume from this point forwards that the coordinates appear in non-decreasing order, i.e., \(x_1 \leq x_2 \leq \ldots \leq x_n\). Given \(\boldsymbol{x},\boldsymbol{z} \in \mathbb{N}^{n}\) we say that \(\boldsymbol{z}\) precedes \(\boldsymbol{x}\), which we write as \(\boldsymbol{z} \preceq \boldsymbol{x}\), if \(z_i \leq x_i\) for all \(i \in [n]\). Clearly the set of admissible tuples is down-closed in the partial order \(\preceq\). In particular, Theorem 3 is equivalent to the statement that every even tuple is admissible. Finally, given \(\boldsymbol{x} \in \mathbb{N}^{n}\) and \(\boldsymbol{z} \in \mathbb{N}^{m}\) we will write \((\boldsymbol{x},\boldsymbol{z})\) for the vector in \(\mathbb{N}^{n+m}\) obtained by concatenation \(\boldsymbol{x}\) and \(\boldsymbol{z}\).

The following simple observation underpins our proof.

Lemma 1 lends itself well to an inductive argument — given a perfect even tuple \(\boldsymbol{x} \in \mathbb{N}^{n+1}\), if \(x_i \equiv 0 \mod 4\) for all \(i \in [n]\), then \(\boldsymbol{y} := \left( \frac{x_1}{2},\frac{x_2}{2},\ldots,\frac{x_n}{2}\right)\) is an even tuple in \(\mathbb{N}^{n}\) and we can deduce the admissability of \(\boldsymbol{x}\) from that of \(\boldsymbol{y}\). However, it is not clear what to do if some of the coordinates of \(\boldsymbol{y}\) are odd.

The key idea here is that, if \(x_{n+1}\) is sufficiently large, then \(\boldsymbol{y}\) will not be perfect, and so we might hope to find an even tuple \(\boldsymbol{y'}\) which \(\preceq\)-dominates \(\boldsymbol{y}\) with \(||\boldsymbol{y'}||_1 \leq 2^{n-1}\). The admissability of \(\boldsymbol{y'}\) would then imply the admissability of \(\boldsymbol{y}\) and thus the admissability of \(\boldsymbol{x}\).

So, for example, to show that \((0,2,4,4,6)\) is admissible, by Lemma 2 it is sufficient to show that \((0,1,2,2)\) is admissible, however \((0,1,2,2) \preceq (2,2,2,2)\) and we know (cf. Figure 1) that \((2,2,2,2)\) is admissible.

Let us make the preceding idea formal with the following lemma. Given \(\boldsymbol{x} \in \mathbb{N}^n\), let us write \(o(\boldsymbol{x})\) for the number of coordinates of \(\boldsymbol{x}\) except the last which are congruent to \(2 \mod 4\).

Proof of Theorem 3. We first note that by 1 every perfect admissible tuple is even.

For the other direction, let us suppose towards a contradiction that the theorem does not hold, and let \(\boldsymbol{x} \in \mathbb{N}^{n+1}\) be a perfect even tuple which is not admissible, with \(n\) as small as possible. Let \(\boldsymbol{y} = \left(\frac{x_1}{2},\frac{x_2}{2},\ldots, \frac{x_n}{2}\right)\). Note that, \(\boldsymbol{x} = (2\boldsymbol{y},x_{n+1})\) and, since \(\boldsymbol{x}\) is perfect, \(x_{n+1} = 2^n - 2||\boldsymbol{y}||_1\). Furthremore, since \(\boldsymbol{x}\) is not admissible, by Lemma 1 neither is \(\boldsymbol{y}\).

If \(\boldsymbol{x}\) is such that \(x_{n+1} \geq 2n\), then since \(o(\boldsymbol{x}) \leq n\), it follows from Lemma 2 that there exists a perfect even \(\boldsymbol{y'} \succeq \boldsymbol{y}\). However, since \(\boldsymbol{y}\) is not admissible, neither is \(\boldsymbol{y'} \in \mathbb{N}^n\), contradicting our choice of \(\boldsymbol{x}\).

Hence, we may assume that \(x_{n+1} < 2n\). However, if \(n+1 \geq 8\), then since \(x_1\leq x_2 \leq \ldots \leq x_{n+1}\), \[\label{e:dim} x_{n+1} \geq \frac{2^n}{n+1} \geq 2n,\tag{2}\] and hence we may assume that \(n+1 \leq 7\).

This reduces the proof to a finite case check, and in fact more precise applications of Lemma 2 will deal with all but three of the remaining cases. In the table below we list all perfect even tuples \(\boldsymbol{x} \in \mathbb{N}^{n+1}\) with \(3\leq n+1 \leq 7\) such that \(x_{n+1} < 2n\). For tuples listed in blue, \(x_{n+1} \geq 2o(\boldsymbol{x})\), and so by Lemma 2 these tuples cannot be minimal counterexamples. The remaining tuples are listed in red.

\(n+1=3\)	\((0,2,2)\)
\(n+1=4\)	\((0,0,4,4)\), \((0,2,2,4)\), \((2,2,2,2)\)
\(n+1=5\)	\((0,0,4,6,6)\), \((0,2,2,6,6)\), \((0,2,4,4,6)\),
	\((2,2,2,4,6)\), \((0,4,4,4,4)\), \((2,2,4,4,4)\)
\(n+1=6\)	\((0,0,8,8,8,8)\),\((0,2,6,8,8,8)\),\((0,4,4,8,8,8)\),\((2,2,4,8,8,8)\),
	\((0,4,6,6,8,8)\), \((2,2,6,6,8,8)\),\((2,4,4,6,8,8)\),
	\((4,4,4,4,8,8)\), \((0,6,6,6,6,8)\), \((2,4,6,6,6,8)\),
	\((4,4,4,6,6,8)\), \((2,6,6,6,6,6)\), \((4,4,6,6,6,6)\)
\(n+1=7\)	\((4,10,10,10,10,10,10)\color{black}\),\((6,8,10,10,10,10,10)\),\((8,8,8,10,10,10,10)\)

So, the only three cases we have to construct by hand are \((0,2)\), \((2,2,2,2)\) and \((2,6,6,6,6,6)\). At this point it is slightly easier to apply Lemma 1 to see that it remains to show that \((1)\), \((1,1,1)\) and \((3,3,3,3,1)\) are admissible, where in fact we show the stronger statement that \((3,3,3,3,3)\) is admissible.

The first is trivial. The second is only slightly less trivial and is given already in Figure 1. The third is a fun exercise and one possible solution is given in Figure 2.

 ◻

3 Discussion↩︎

As we noted in Section 2, if \(\boldsymbol{x}\) is an admissible tuple and \(\boldsymbol{y} \preceq \boldsymbol{x}\), then \(\boldsymbol{y}\) is also admissible. In particular, Theorem 3 also tells us a lot about the admissible profiles of non-perfect matchings.

However, whilst Theorem 3 fully characterises the perfect admissible tuples, there are admissible tuples which are not \(\preceq\)-dominated by any perfect admissible tuples, for example two of the base cases in the proof of Theorem 3. It is relatively easy to see that Conjecture 1 would imply that all tuples \(\boldsymbol{x} \in \mathbb{N}^n\) with \(||\boldsymbol{x}||_1 < 2^{n-1}\) are admissible.

In fact, it was pointed out by a referee that this already follows from the work of Hollmann, Khathuria, Riet, and Skachek [11].

It would also be interesting to characterise which tuples are the profiles of Hamilton cycles in \(Q^d\). Since each Hamilton cycle can be split into two matchings, it is clear that any such tuple must be the sum of two perfect admissible tuples, and so in particular must also be even. Furthermore, clearly no direction can appear more than \(2^{n-1}\) times, Finally, if some \(x_i=0\), then all edges are either contained in the hyperplane \(H_i =\{ \boldsymbol{a} \in \{0,1\}^n \colon a_i=0\}\) or its complement, which is a contradiction as a Hamilton cycle is connected and spanning. Hence, each \(x_i \geq 1\) and so, since \(\boldsymbol{x}\) must be even, each \(x_i \geq 2\). We conjecture that these are the only restrictions.

A different generalisation would be to consider decomposing the hypercube into \(2\)-dimensional faces with specified orientations. More concretely, given a decomposition \(D\) of \(E\left(Q^n\right)\) into \(4\)-cycles, the profile of this decomposition is the weighting \(w\) of \(K_n\) where the weight \(w(ij)\) of an edge is the number of \(4\)-cycles in \(D\) where the antipodal points differ in coordinates \(i\) and \(j\). It is easy to see that 1 implies that for any \(i\) the total number of faces with an edge in direction \(i\) must be even, i.e., \(\sum_{j \neq i} w(ij) = 0 \mod 2\). Indeed, if we consider the intersection of such a decomposition with the subcube whose \(i\)th coordinate is \(0\) then we can easily construct a perfect matching with \(\sum_{j \neq i} w(ij)\) edges in direction \(i\). However, it is a simple exercise to check that the weighting \(w\) of \(K_4\) given by \[w(ij) = \begin{cases} 2 \qquad \text{ if } ij= 12 \text{ or } 34,\\ 0 \qquad \text{ otherwise} \end{cases}\] is not the profile of any such decomposition, and so, at least in small dimensions, there are other obstructions.

Another interesting question would be to characterise the admissible profiles for matchings of the middle layer graph, the induced subgraph \(M_n\) of \(Q^{2n+1}\) on the middle two layers. A similar argument as in 1 shows that if \(\boldsymbol{x}\) is the profile of a perfect matching on \(M_n\) then \(x_i \equiv \binom{2n+1}{n+1} \mod 2\) for each \(i\in [2n+1]\). An application of Lucas’ theorem shows that these binomial coefficients are odd if and only if \(n+1\) is a power of \(2\).

However, there is another necessary condition beyond this parity condition and the trivial condition that \(||\boldsymbol{x}||_1 = \frac{|V(M_n)|}{2}\). Indeed, since only \(\binom{2n}{n}\) vertices in each layer are incident to an edge in a fixed direction, we require that \(x_i \leq \binom{2n}{n}\) for each \(i \in [2n+1]\). In fact, since the \(\binom{2n}{n-1}\) vertices in the lower layer which are not adjacent to an edge in direction \(\boldsymbol{e_i}\) are only adjacent to the vertices in the upper layer which are adjacent to an edge in direction \(\boldsymbol{e_i}\), and therefore must be matched to a subset of these vertices via edges in some direction not equal to \(\boldsymbol{e_i}\), the matchings can contain at most \(\binom{2n}{n} - \binom{2n}{n-1} = \binom{2n-1}{n-1}\) edges in direction \(\boldsymbol{e_i}\).

For \(n=1\), it is easy to verify that these two conditions, together with the trivial condition that \(||\boldsymbol{x}||_1 = \frac{|V(M_n)|}{2} = \binom{2n+1}{n+1}\), are also sufficient, since \((1,1,1)\) is the only tuple satisfying these conditions.

Finally, another intriguing generalisation would be to look at matchings on other polytopes. For example, each of the edges in the \(n\)-dimensional permutahedron Perm\((n)\), embedded in \(\mathbb{R}^{n+1}\) as the convex hull of all permutation vectors, is parallel to some vector of the form \(\boldsymbol{e_i} - \boldsymbol{e_j}\) with \(i,j \in [n+1]\). Let us define the profile of a matching of Perm\((n)\) to be the weighting \(w\) of \(K_{n+1}\) where \(w(ij)\) is the number of edges parallel to the vector \(\boldsymbol{e_i} - \boldsymbol{e_j}\).

Note that, since Perm\((n)\) can also be viewed as the Cayley graph of \(S_{n+1}\) whose generating set is the set of adjacent transposition \(S = \{ (i,i+1) \colon i \in [n]\}\), it is possible to phrase this as a question similar to Conjecture 1 about the symmetric group \(S_{n+1}\), where the ‘differences’ between permutations are required to be adjacent transpositions.

In the case \(n=2\) there are only \(2\) matchings, each of which use an edge in each direction once. For \(n=3,4\) computational evidence suggests that each direction must be used an even number of times, and that, if we view the profile \(w\) as a vector in \(\mathbb{R}^{\binom{n+1}{2}}\), then the set of admissible vectors are the even interior points of some convex polytope. For \(n=3\), this polytope is determined by the inequalities \[\begin{align} &w(12) + w(34) = w(13) + w(24) = w(14)+w(23)=4;\\ &w(ij) \geq 0 \text{ for all } i,j, \end{align}\] which essentially say that each pair of orthogonal directions has to be used exactly four times in the matching. For \(n=4\) we were able to calculate a list of \(1080\) inequalities which determine the polytope, but it is not clear if there is a more enlightening description.

Acknowledgements↩︎

The author would like to thank Maurício Collares for pointing out the relevance of Lucas’ theorem, as well as for providing computational evidence to motivate the questions in Section 3 and Thang Nguyen for bringing the references [13], [14] to his attention. The author would also like to thank the anonymous referees for their valuable suggestions and in particular for providing a proof of Theorem 4. The author was supported in part by the Austrian Science Fund (FWF) [10.55776/].

References↩︎