More distinct distances under local conditions
type: Item
instance of: scholarly article
title: More distinct distances under local conditions
zbMATH Open document ID: 1399.52030
author: Jacob Fox
author: János Pach
author: Andrew Suk
published in: Combinatorica
publication date: 2018-07-23T00:00:00Z
full work available at URL: ddistances080816.pdf
review text: The paper is related to the Erdős problem of distinct distances. In 1946 Erdős asked to estimate the minimum number of distinct distances determined by a set of \(n\) points on the plane. For integers \(p\) and \(q\) with \(q \leq \binom{p}2\), let \(D(n,p,q)\) denote the minimum number of distinct distances determined by a set \(V\) of \(n\) points on the plane with the property that any \(p\) points from \(V\) determine at least \(q\) distinct distances. Some lower and upper bounds have been obtained for \(D(n,p,q)\) under certain local conditions by different authors. In this paper, the following result is proved. Let \(V\) be a set of \(n\) points on the plane such that any \(p\) points induce at least \(\binom{p}2 - p + 6\) distinct distances. Then \(V\) determines at least \(n^{\frac87 - o(1)}\) distinct distances as \(n\) tends to infinity. In the proof, some graph-theoretic tools are used.
reviewed by: Elizaveta Zamorzaeva
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 6909501
zbMATH Keywords: Erdős problem
zbMATH Keywords: minimum number of distinct distances
zbMATH Keywords: \(n\) points on the plane
zbMATH Keywords: lower and upper bounds
zbMATH Keywords: local conditions
MaRDI profile type: Publication
OpenAlex ID: W2599315655
cites work: On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
cites work: On distinct distances among points in general position and other related problems
cites work: On some metric and combinatorial geometric problems
cites work: The grid revisited
cites work: A variant of the classical Ramsey problem
cites work: A semi-algebraic version of Zarankiewicz's problem
cites work: On the Erdős distinct distances problem in the plane
cites work: On a problem of K. Zarankiewicz
cites work: On Certain Sets of Integers
cites work: On edge colorings with at least \(q\) colors in every subset of \(p\) vertices
cites work: Lower bounds for incidences with hypersurfaces
cites work: On sets of integers containing k elements in arithmetic progression
cites work: The semi-chromatic number of a graph
DOI: 10.1007/S00493-016-3637-X
Recommended article: Distinct Distances in Three and Higher Dimensions
Recommended article: Distinct distances in three and higher dimensions
Recommended article: Local differentiability of distance functions
Recommended article: Localization of the Kobayashi distance
Recommended article: A note on distinct distances
Recommended article: Distinct distances in the complex plane
Recommended article: Distinct distances in the plane
Recommended article: Local spacings along curves
Recommended article: On locations and distances
description: scientific article; zbMATH DE number 6909501