Hostname: page-component-7b7567c8c-mnklg Total loading time: 0 Render date: 2026-11-12T19:04:16.733Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of:Extremal combinatoricsDiscrete geometry

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: kupavskii@yandex.ru)
NABIL H. MUSTAFA
Affiliation:
Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, ESIEE Paris, France (e-mail: mustafan@esiee.fr)
KONRAD J. SWANEPOEL
Affiliation:
Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, UK (e-mail: k.swanepoel@lse.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 2 , March 2019, pp. 280 - 286
Copyright
Copyright © Cambridge University Press 2018 

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