Crescent configurations in normed spaces. (English) Zbl 1465.52027
Summary: We study the problem of crescent configurations, posed by Erdős in 1989. A crescent configuration is a set of \(n\) points in the plane such that: 1) no three points lie on a common line, 2) no four points lie on a common circle, 3) for each \(1 \le i \le n-1\), there exists a distance which occurs exactly \(i\) times. Constructions of sizes \(n \le 8\) have been provided by Liu, Palásti, and Pomerance. Erdős conjectured that there exists some \(N\) for which there do not exist crescent configurations of size \(n\) for all \(n \ge N\).
We extend the problem of crescent configurations to general normed spaces \((\mathbb{R}^2, \Vert \cdot \Vert)\) by studying strong crescent configurations in \(\Vert \cdot \Vert\). In an arbitrary norm \(\Vert\cdot \Vert\), we construct a strong crescent configuration of size 4. We also construct larger strong crescent configurations of size \(n \le 6\) in the Euclidean norm and of size \(n \le 8\) in the taxi cab and Chebyshev norms. When defining strong crescent configurations, we introduce the notion of line-like configurations in \(\Vert \cdot \Vert\). A line-like configuration in \(\Vert \cdot \Vert\) is a set of points whose distance graph is isomorphic to the distance graph of equally spaced points on a line. In a broad class of norms, we construct line-like configurations of arbitrary size.
Our main result is a crescent-type result about line-like configurations in the Chebyshev norm. A line-like crescent configuration is a line-like configuration for which no three points lie on a common line and no four points lie on a common \(\Vert \cdot \Vert\) circle. We prove that for \(n \ge 7\), every line-like crescent configuration of size \(n\) in the Chebyshev norm must have a rigid structure. Specifically, it must be a perpendicular perturbation of equally spaced points on a horizontal or vertical line.
We extend the problem of crescent configurations to general normed spaces \((\mathbb{R}^2, \Vert \cdot \Vert)\) by studying strong crescent configurations in \(\Vert \cdot \Vert\). In an arbitrary norm \(\Vert\cdot \Vert\), we construct a strong crescent configuration of size 4. We also construct larger strong crescent configurations of size \(n \le 6\) in the Euclidean norm and of size \(n \le 8\) in the taxi cab and Chebyshev norms. When defining strong crescent configurations, we introduce the notion of line-like configurations in \(\Vert \cdot \Vert\). A line-like configuration in \(\Vert \cdot \Vert\) is a set of points whose distance graph is isomorphic to the distance graph of equally spaced points on a line. In a broad class of norms, we construct line-like configurations of arbitrary size.
Our main result is a crescent-type result about line-like configurations in the Chebyshev norm. A line-like crescent configuration is a line-like configuration for which no three points lie on a common line and no four points lie on a common \(\Vert \cdot \Vert\) circle. We prove that for \(n \ge 7\), every line-like crescent configuration of size \(n\) in the Chebyshev norm must have a rigid structure. Specifically, it must be a perpendicular perturbation of equally spaced points on a horizontal or vertical line.
MSC:
| 52C10 | Erdős problems and related topics of discrete geometry |
References:
| [1] | If |p y − q y | > |p x − q x | and q y > p y , we say that [p, q] is type y. |
| [2] | If |p y − q y | > |p x − q x | and p y > q y , we say that [p, q] is type y . |
| [3] | If |p x − q x | = |p y − q y |, q x > p x and q y > p y , we say that [p, q] is type b xy . |
| [4] | If |p x − q x | = |p y − q y |, p x > q x and q y > p y , we say that [p, q] is type b x y . |
| [5] | If |p x − q x | = |p y − q y |, p x > q x and p y > q y , we say that [p, q] is type b x y . |
| [6] | If |p X. − Q. X | = |p Y. − Q. Y |, Q. X > P. X And P. Y > Q. Y. |
| [7] | Let [p 1 , . . . , p n ] be a line-like configuration. The type of [p 1 , . . . , p n ] is a string a 1 a 2 . . . a n−1 , with a i ∈ T , where for all 1 ≤ i ≤ n − 1 we have that [p i , p i+1 ] is type a i . |
| [8] | Let a 1 a 2 . . . a n−1 and c 1 c 2 . . . c k−1 be types. We say that the type a 1 a 2 . . . a n−1 contains the type c 1 c 2 . . . c k−1 if c 1 c 2 . . . c k−1 is a substring of a 1 a 2 . . . a n−1 . |
| [9] | We say that the type a 1 a 2 . . . a k−1 is realizable if there exists a line-like crescent configuration [p 1 , . . . , p k ] with type a 1 a 2 . . . a k−1 . |
| [10] | Let m ≥ 1. We say that a 1 a 2 . . . a k−1 is m-extendable if there exist a k , a k+1 , . . . , a k+m−1 ∈ T so that a 1 a 2 . . . a k−1 a k a k+1 . . . a k+m−1 is realizable. |
| [11] | The following are isometries of L ∞ : reflection about a horizontal line, reflec-tion about a vertical line, reflection about a line with slope ±1. |
| [12] | A type a 1 a 2 . . . a n−1 is realizable if and only if a n−1 a n−2 . . . a 1 is realizable. The following are simple example arguments making use of these symmetries. |
| [13] | 3. Classifying Line-like Crescent Configurations in Non-strictly Convex Norms |
| [14] | For the definition of line-like crescent configurations, see Definition 4.4. For the definition of perpendicular perturbations, see Definition 4.1. |
| [15] | D. Burt, E. Goldstein, S. Manski, S.J. Miller, E.A. Palsson, and H. Suh, Crescent Configura-tions, Integers 16 (2016), #A38. · Zbl 1354.52018 |
| [16] | P. Brass, Erdős distance problems in normed spaces, Comput. Geom. 6, no. 4 (1996), 195-214. · Zbl 0860.52008 |
| [17] | R. Durst, M. Hlavacek, C. Huynh, S.J. Miller, E.A. Palsson, Classification of Crescent Con-figurations. https://arxiv.org/abs/1610.07836. |
| [18] | P. Erdős, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248-250. · Zbl 0060.34805 |
| [19] | P. Erdős, Distances with specified multiplicities, Amer. Math. Monthly 96 (1989), 447. |
| [20] | J. Garibaldi, Erdős distance problem for convex metrics, manuscript (2004). https://web.archive.org/we\b/20050215212626/\https://www.math\.ucla.edu/ jlucas/ dissertation.pdf |
| [21] | L. Guth, N. H. Katz, On the Erdős distinct distances problem in the plane, Ann. of Mathe-matics 181 (2015), 155-190. · Zbl 1310.52019 |
| [22] | A. Liu, On the “seven points” problem of P. Erdős, New Zealand J. Math. 15 (1986), 29-33. · Zbl 0651.51016 |
| [23] | J. Matoušek, The number of unit distances is almost linear for most norms, Adv. Math. 226, no. 3 (2011), 2618-2628. · Zbl 1214.52005 |
| [24] | H. Martini, K. Swanepoel, G. Weiß, The geometry of Minkowski spaces -a survey, part I, Expo. Math. 19, no. 2 (2001), 97-142. · Zbl 0984.52004 |
| [25] | I. Palásti, On the seven points problem of P. Erdős, Stud. Sci. Math. Hungar. 22 (1987), 447-448. · Zbl 0561.51001 |
| [26] | I. Palásti, Lattice point examples for a question of Erdős, Period. Math. Hungar. 20 (1989), 231-235. · Zbl 0687.52004 |
| [27] | L. Székely, Crossing Numbers and Hard Erdős Problems in Discrete Geometry, Combin. Probab. Comput. 11 (1993), 1-10. |
| [28] | P. Valtr, Strictly convex norms allowing many unit distances and related touching questions, manuscript (2005). https://kam.mff.cuni.cz/ valtr/n.pdf |
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.
