Finding a perfect matching of F_2^n with prescribed differences
Benedek Kovács · Ars Mathematica Contemporanea · 2024
We consider the following question by Balister, Győri and Schelp: given 2n-1 nonzero vectors in F2n with zero sum, is it always possible to partition the elements of F2n into pairs such that the difference between the two elements of the i-th pair is equal to the i-th given vector for every i? An analogous question in Fp, which is a case of the so-called "seating couples" problem, has been resolved by Preissmann and Mischler in 2009. In this paper, we prove the conjecture in F2n in the case when the number of distinct values among the given difference vectors is at most n-2log(n)-1, and also in the case when at least a fraction 1/2+ε of the given vectors are equal (for all ε>0 and n sufficiently large based on ε).