Odd-distance sets and right-equidistant sequences in the maximum and Manhattan metrics. (English. Russian original) Zbl 1505.54044
Dokl. Math. 106, No. 2, 340-342 (2022); translation from Dokl. Ross. Akad. Nauk, Mat. Inform. Protsessy Upr. 506, 45-48 (2022).
Summary: We solve two related extremal-geometric questions in the \(n\)-dimensional space \(\mathbb{R}_{\infty }^n\) equipped with the maximum metric. First, we prove that the maximum size of a right-equidistant sequence of points in \(\mathbb{R}_{\infty }^n\) equals \({{2}^{{n + 1}}} - 1\). A sequence is right-equidistant if each of the points is at the same distance from all the succeeding points. Second, we prove that the maximum number of points in \(\mathbb{R}_{\infty }^n\) with pairwise odd distances equals \(2^n \). We also obtain partial results for both questions in the \(n\)-dimensional space \(\mathbb{R}_1^n\) with the Manhattan distance.
MSC:
| 54E35 | Metric spaces, metrizability |
Keywords:
maximum metric; Manhattan metric; equilateral dimension; odd-distance sets; right-equidistant sequencesReferences:
| [1] | Alon, N.; Pudlák, P., Equilateral sets in \(l_p^n\), Geom. Funct. Anal., 13, 467-482 (2003) · Zbl 1034.46015 · doi:10.1007/s00039-003-0418-7 |
| [2] | Bandelt, H.-J.; Chepoi, V.; Laurent, M., Embedding into rectilinear spaces, Discrete Comput. Geom., 19, 595-604 (1998) · Zbl 0973.51012 · doi:10.1007/PL00009370 |
| [3] | Blokhuis, A.; Wilbrink, H. A., Alternative proof of Sine’s theorem on the size of a regular polygon in \(\mathbb{R}_{}^n\) with the \(l_{\infty }^{} \)-metric, Discrete Comput. Geom., 7, 433-434 (1992) · Zbl 0753.51011 · doi:10.1007/BF02187853 |
| [4] | Dilworth, R. P., A decomposition theorem for partially ordered sets, Ann. Math., 51, 161-166 (1950) · Zbl 0038.02003 · doi:10.2307/1969503 |
| [5] | Erdős, P.; Rogers, C. A., Covering space with convex bodies, Acta Arith., 7, 281-285 (1962) · Zbl 0213.05802 · doi:10.4064/aa-7-3-281-285 |
| [6] | N. Frankl, A. Kupavskii, and A. Sagdeev, “Max-norm Ramsey theory” (2021). arXiv preprint 2111.08949. · Zbl 1471.05110 |
| [7] | Ardal, H.; Maňuch, J.; Rosenfeld, M.; Shelah, S.; Stacho, L., The odd-distance plane graph, Discrete Comput. Geom., 42, 132-141 (2009) · Zbl 1200.05059 · doi:10.1007/s00454-009-9190-2 |
| [8] | Graham, R. L.; Rothschild, B. L.; Straus, E. G., Are there n + 2 points in E^n with odd integral distances?, Am. Math. Mon., 81, 21-25 (1974) · Zbl 0277.10021 |
| [9] | Guy, R. K., Unsolved problems: An olla-podrida of open problems, often oddly posed, Am. Math. Mon., 90, 196-200 (1983) · doi:10.1080/00029890.1983.11971188 |
| [10] | Koolen, J.; Laurent, M.; Schrijver, A., Equilateral dimension of the rectilinear space, Des. Codes Cryptogr., 21, 149-164 (2000) · Zbl 0970.51016 · doi:10.1023/A:1008391712305 |
| [11] | Naszódi, M.; Pach, J.; Swanepoel, K., Arrangements of homothets of a convex body, Mathematika, 63, 696-710 (2017) · Zbl 1379.52003 · doi:10.1112/S0025579317000122 |
| [12] | Petty, C. M., Equilateral sets in Minkowski spaces, Proc. Am. Math. Soc., 29, 369-374 (1971) · Zbl 0214.20801 · doi:10.1090/S0002-9939-1971-0275294-8 |
| [13] | Polyanskii, A., Pairwise intersecting homothets of a convex body, Discrete Math., 340, 1950-1956 (2017) · Zbl 1376.52016 · doi:10.1016/j.disc.2017.04.002 |
| [14] | Smyth, C., Thirty Essays on Geometric Graph Theory (2013), New York: Springer, New York |
| [15] | Swanepoel, K. J., Cardinalities of k-distance sets in Minkowski spaces, Discrete Math., 197, 759-767 (1999) · Zbl 0939.52007 · doi:10.1016/S0012-365X(98)00276-3 |
| [16] | Swanepoel, K. J., A problem of Kusner on equilateral sets, Arch. Math., 83, 164-170 (2004) · Zbl 1062.52017 · doi:10.1007/s00013-003-4840-8 |
| [17] | Swanepoel, K. J.; Villa, R., Maximal equilateral sets, Discrete Comput. Geom., 50, 354-373 (2013) · Zbl 1287.46011 · doi:10.1007/s00454-013-9523-z |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
