Circle grids and bipartite graphs of distances

DOI10.1007/BF01200753MaRDI QIDQ1894698zbMATH OpenOpenAlexFDO

Authors György Elekes

Publication date 11 December 1995

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01200753

zbMATH Keywords

distancesgeometric graphspoint sets

Mathematics Subject Classification ID

Distance in graphs (05C12) Erd?s problems and related topics of discrete geometry (52C10)

Review text

Given two point sets \(A\) and \(B\) of size \(n\) and \(t\), respectively, let \(f_t (n)\) be the minimum number of distinct distances realized by one point of each set. If \(t \geq 2\), then \(f_t(n) \geq \lceil \sqrt {n/2} \rceil\). If \(t \geq 3\) and \(n \geq 4t^3\), it is shown that \(f_t (n) \leq \sqrt {nt} + 3t/2\). The latter bound is new and follows by a construction that uses circular grids. A second result of the paper concerns largest distances. Given a set \(A\) of \(n\) points, let \(G\) be the graph with arcs between nodes (the points) for the \(k\) largest different distances between two points of \(A\) (so \(G\) may have many more than \(k\) arcs). Given integers \(t\) and \(k\) let \(g_t (k)\) be the maximum value for \(n\) such that a point set \(A\) exists with \(K_{t,n} \subset G\). It is shown that for \(t \geq 3\) and \(k \geq 2t^2\) we have \(g_t (k) \geq (k - 2t)^2/(2t)\).

Recommendations

• On bipartite distinct distances in the plane
• The grid revisited
• scientific article; zbMATH DE number 1054775
• Point sets with distinct distances
• The two largest distances in finite planar sets

Cites work

• n points in the plane can determine \(n^{3/2}\) unit circles
• On the graph of large distances

Cited in

(17)

• Distinct distance sets in a graph
• Graham's problem on shortest networks for points on a circle
• Maximal sets of given diameter in the grid and the torus
• On point sets with many unit distances in few directions
• The Elekes-Szabó problem and the uniformity conjecture
• On distinct distances between a variety and a point set
• Almost-equidistant sets
• How to find groups?
• Distinct distances in homogeneous sets in Euclidean space
• On bipartite distinct distances in the plane
• Distinct distances on non-ruled surfaces and between circles
• A combinatorial distinction between unit circles and straight lines: how many coincidences can they have?
• Distinct Distances in Three and Higher Dimensions
• Distinct Distances Between a Circle and a Generic Set
• Distinct angle problems and variants
• On the dimension of exceptional parameters for nonlinear projections, and the discretized Elekes-Rónyai theorem
• On the graph of large distances

This page was built for publication: Circle grids and bipartite graphs of distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894698)