Crescent configurations in normed spaces

Abstract

We study the problem of crescent configurations, posed by Erdos 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 ≤ i ≤ n - 1, there exists a distance which occurs exactly i times. Constructions of sizes n ≤ 8 have been provided by Liu, Palásti, and Pomerance. Erdos conjectured that there exists some N for which there do not exist crescent configurations of size n for all n ≥ N. We extend the problem of crescent configurations to general normed spaces (ℝ², II · II) by studying strong crescent configurations in II · II. In an arbitrary norm II · II, we construct a strong crescent configuration of size 4. We also construct larger strong crescent configurations of size n ≤ 6 in the Euclidean norm and of size n ≤ 8 in the taxicab and Chebyshev norms. When defining strong crescent configurations, we introduce the notion of line-like configurations in II · II. A line-like configuration in II · II 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 II · II circle. We prove that for n ≥ 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.