Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-13T14:56:21.798Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounding the Size of an Almost-Equidistant Set in Euclidean Space

Part of: Discrete geometry Extremal combinatorics

Published online by Cambridge University Press:  13 June 2018

ANDREY KUPAVSKII ,
NABIL H. MUSTAFA  and
KONRAD J. SWANEPOEL
ANDREY KUPAVSKII
Affiliation:
Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Region, 141700, Russia and University of Birmingham, B15 2TT, Birmingham, UK (e-mail: [email protected])
NABIL H. MUSTAFA
Affiliation:
Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, ESIEE Paris, France (e-mail: [email protected])
KONRAD J. SWANEPOEL
Affiliation:
Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

A set of points in d-dimensional Euclidean space is almost equidistant if, among any three points of the set, some two are at distance 1. We show that an almost-equidistant set in ℝd has cardinality O(d4/3).

MSC classification

Primary: 52C10: Erdős problems and related topics of discrete geometry
Secondary: 05D10: Ramsey theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 2 , March 2019 , pp. 280 - 286
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

The work of Andrey Kupavskii was supported by Russian Foundation for Basic Research grant 18-01-00355.

†

The work of Nabil H. Mustafa in this paper has been supported by the grant ANR SAGA (JCJC-14-CE25-0016-01).

References

[1] Ajtai, M., Komlós, J. and Szemerédi, E. (1980) A note on Ramsey numbers. J. Combin. Theory Ser. A 29 354–360.Google Scholar
[2] Alon, N. (2003) Problems and results in extremal combinatorics I. Discrete Math. 273 31–53.Google Scholar
[3] Balko, M., Pór, A., Scheucher, M., Swanepoel, K. and Valtr, P. (2017) Almost-equidistant sets. arXiv:1706.06375Google Scholar
[4] Bezdek, K. and Lángi, Z. (1999) Almost equidistant points on S d−1. Period. Math. Hungar. 39 139–144.Google Scholar
[5] Bezdek, K., Naszódi, M. and Visy, B. (2003) On the mth Petty numbers of normed spaces. In Discrete Geometry: In Honor of W. Kuperberg's 60th Birthday (Bezdek, A., ed.), Vol. 253 of Monographs and Textbooks in Pure and Applied Mathematics, Dekker, pp. 291–304.Google Scholar
[6] Deaett, L. (2011) The minimum semidefinite rank of a triangle-free graph. Linear Algebra Appl. 434 1945–1955.Google Scholar
[7] Györey, B. (2004) Diszkrét metrikus terek beágyazásai (in Hungarian). Master's thesis, Eötvös Loránd University, Budapest.Google Scholar
[8] Larman, D. G. and Rogers, C. A. (1972) The realization of distances within sets in Euclidean space. Mathematika 19 1–24.Google Scholar
[9] Nechushtan, O. (2002) On the space chromatic number. Discrete Math. 256 499–507.Google Scholar
[10] Polyanskii, A. (2017) On almost-equidistant sets. arXiv:1707.00295Google Scholar
[11] Pudlák, P. (2002) Cycles of nonzero elements in low rank matrices. Combinatorica 22 321–334.Google Scholar
[12] Rosenfeld, M. (1991) Almost orthogonal lines in Ed. In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift (Gritzmann, P. and Sturmfels, B., eds), Vol. 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 489–492.Google Scholar