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

EUROCOMB’23

Abstract
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.

Pages:
669–674
References

Question posed by R. Bacher on MathLinks in 2008, currently available here: https://artofproblemsolving.com/community/c6h183554

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.
https://doi.org/10.1016/j.ejc.2010.11.008

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.
https://doi.org/10.1017/S0963548320000620

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.
https://doi.org/10.1007/s11856-012-0020-5

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.
https://doi.org/10.1016/j.disc.2016.06.018

Mička, O. (2017). Hypercube problems. http://ktiml.mff.cuni.cz/ 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.
https://doi.org/10.1080/00029890.2009.11920936

Metrics

0

Views

0

PDF views