Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings

Frankl, Nóra; Kupavskii, Andrey; Sagdeev, Arsenii

doi:10.1090/proc/16254

Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings
HTML articles powered by AMS MathViewer

by Nóra Frankl, Andrey Kupavskii and Arsenii Sagdeev;

Proc. Amer. Math. Soc. 151 (2023), 2353-2362

DOI: https://doi.org/10.1090/proc/16254

Published electronically: March 14, 2023

HTML | PDF | Request permission

Abstract:

In 2008, Schmidt and Tuller stated a conjecture concerning optimal packing and covering of integers by translates of a given three-point set. In this note, we confirm their conjecture and relate it to several other problems in combinatorics.

References

Maria Axenovich, John Goldwasser, Bernard Lidický, Ryan R. Martin, David Offner, John Talbot, and Michael Young, Polychromatic colorings on the integers, Integers 19 (2019), Paper No. A18, 17. MR 3928556
Siddhartha Bhattacharya, Periodicity and decidability of tilings of $\Bbb Z^2$, Amer. J. Math. 142 (2020), no. 1, 255–266. MR 4060876, DOI 10.1353/ajm.2020.0006
Béla Bollobás, Svante Janson, and Oliver Riordan, On covering by translates of a set, Random Structures Algorithms 38 (2011), no. 1-2, 33–67. MR 2768883, DOI 10.1002/rsa.20346
Peter Brass, William Moser, and János Pach, Research problems in discrete geometry, Springer, New York, 2005. MR 2163782
Ethan M. Coven and Aaron Meyerowitz, Tiling the integers with translates of one finite set, J. Algebra 212 (1999), no. 1, 161–174. MR 1670646, DOI 10.1006/jabr.1998.7628
Paul Erdős, Some results on additive number theory, Proc. Amer. Math. Soc. 5 (1954), 847–853. MR 64798, DOI 10.1090/S0002-9939-1954-0064798-9
N. Frankl, A. Kupavskii, and A. Sagdeev, Max-norm Ramsey Theory, arXiv:2111.08949, 2022.
Marcel J. E. Golay, Notes on the representation of $1,\,2,\,\ldots ,\,n$ by differences, J. London Math. Soc. (2) 4 (1972), 729–734. MR 297732, DOI 10.1112/jlms/s2-4.4.729
Andrey Kupavskii and Arsenii Sagdeev, All finite sets are Ramsey in the maximum norm, Forum Math. Sigma 9 (2021), Paper No. e55, 12. MR 4298642, DOI 10.1017/fms.2021.50
A. B. Kupavskii and A. A. Sagdeev, Ramsey theory in the $n$-space with Chebyshev metric, Uspekhi Mat. Nauk 75 (2020), no. 5(455), 191–192 (Russian); English transl., Russian Math. Surveys 75 (2020), no. 5, 965–967. MR 4154851, DOI 10.4213/rm9958
Daphne Der-Fen Liu and Xuding Zhu, Fractional chromatic number and circular chromatic number for distance graphs with large clique size, J. Graph Theory 47 (2004), no. 2, 129–146. MR 2082743, DOI 10.1002/jgt.20020
G. G. Lorentz, On a problem of additive number theory, Proc. Amer. Math. Soc. 5 (1954), 838–841. MR 63389, DOI 10.1090/S0002-9939-1954-0063389-3
D. J. Newman, Complements of finite sets of integers, Michigan Math. J. 14 (1967), 481–486. MR 218324, DOI 10.1307/mmj/1028999851
Donald J. Newman, Tesselation of integers, J. Number Theory 9 (1977), no. 1, 107–111. MR 429720, DOI 10.1016/0022-314X(77)90054-3
Joshua H. Rabinowitz and Viera Krňanová Proulx, An asymptotic approach to the channel assignment problem, SIAM J. Algebraic Discrete Methods 6 (1985), no. 3, 507–518. MR 791178, DOI 10.1137/0606050
Wolfgang M. Schmidt and David M. Tuller, Covering and packing in $\Bbb Z^n$ and $\Bbb R^n$. I, Monatsh. Math. 153 (2008), no. 3, 265–281. MR 2379671, DOI 10.1007/s00605-007-0500-6
Wolfgang M. Schmidt and David M. Tuller, Covering and packing in $\Bbb Z^n$ and $\Bbb R^n$. II, Monatsh. Math. 160 (2010), no. 2, 195–210. MR 2644221, DOI 10.1007/s00605-009-0099-x
Sherman Stein, Tiling, packing, and covering by clusters, Rocky Mountain J. Math. 16 (1986), no. 2, 277–321. MR 843054, DOI 10.1216/RMJ-1986-16-2-277
G. Weinstein, Some covering and packing results in number theory, J. Number Theory 8 (1976), no. 2, 193–205. MR 435022, DOI 10.1016/0022-314X(76)90101-3