Finding pairwise disjoint vector pairs in F2n with a prescribed sequence of differences


We consider the following question by Balister, Győri and Schelp: given $2^{n-1}$ nonzero vectors in $\mathbb{F}_2^n$ with zero sum, is it always possible to partition $\mathbb{F}_2^n$ into pairs such that the difference between the two elements of the $i$-th pair is equal to the $i$-th given vector? An analogous question in $\mathbb{F}_p$ was resolved by Preissmann and Mischler in 2009. In this paper, we prove the conjecture in $\mathbb{F}_2^n$ in the case when there are at most $n-2\log n-1$ distinct values among the given differences, and also in the case when at least a fraction $\frac{28}{29}$ of the differences are equal.


Question posed by R. Bacher on MathLinks in 2008, currently available here:

Balister, P. N., Győri, E., & Schelp, R. H. (2011). Coloring vertices and edges of a graph by nonempty subsets of a set. European Journal of Combinatorics, 32(4), 533-537.

Correia, D. M., Pokrovskiy, A., & Sudakov, B. (2021). Short proofs of rainbow matching results. arXiv preprint arXiv:2108.07734.

Gao, P., Ramadurai, R., Wanless, I. M., & Wormald, N. (2021). Full rainbow matchings in graphs and hypergraphs. Combinatorics, Probability and Computing, 1-19.

Karasev, R. N., & Petrov, F. V. (2012). Partitions of nonzero elements of a finite field into pairs. Israel Journal of Mathematics, 192(1), 143-156.

Kohen, D., & Sadofschi, I. (2010). A New Approach on the Seating Couples Problem. arXiv:1006.2571

Kohen, D., & Sadofschi, I. (2016). On a generalization of the seating couples problem. Discrete Mathematics, 339(12), 3017-3019.

Mička, O. (2017). Hypercube problems. gregor/hypercube/lecture17.pdf

Preissmann, E., & Mischler, M. (2009). Seating Couples Around the King's Table and a New Characterization of Prime Numbers. The American Mathematical Monthly, 116(3), 268-272.





PDF views