On bipartite distinct distances in the plane

DOI10.37236/9687MaRDI QIDQ2665979zbMATH OpenOpenAlexFDO

Authors Surya Mathialagan

Publication date 22 November 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.01883

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bipartite distance energycrossing number methoddistance energydistinct distancesElekes' program

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: Given sets $mathcalP,mathcalQsubseteqmathbb{R}^2$ of sizes $m$ and $n$ respectively, we are interested in the number of distinct distances spanned by $mathcalPimesmathcalQ$. Let $D(m,n)$ denote the minimum number of distances determined by sets in $mathbb{R}^2$ of sizes $m$ and $n$ respectively, where $mleqn$. Elekes cite{CircleGrids} showed that $D(m,n)=O(sqrtmn)$ when $mleq{n}^{1/3}$. For $mgeq{n}^{1/3}$, we have the upper bound $D(m,n)=O(n/sqrtlogn)$ as in the classical distinct distances problem. In this work, we show that Elekes' construction is tight by deriving the lower bound of $D(m,n)=Omega(sqrtmn)$ when $mleq{n}^{1/3}$. This is done by adapting Sz'{e}kely's crossing number argument. We also extend the Guth and Katz analysis for the classical distinct distances problem to show a lower bound of $D(m,n)=Omega(sqrtmn/logn)$ when $mgeq{n}^{1/3}$.

Review text

Let \(D(n)\) denote the minimum number of distinct distances among \(n\) points in the plane, for all possible choices of the points. The distinct distances conjecture of \textit{P. Erdős} [Am. Math. Mon. 53, 248--250 (1946; Zbl 0060.34805)] asserts that \( D(n)= \Omega(n /\sqrt{\log n})\). He showed that an \(\sqrt{n}\times \sqrt{n}\) grid has only \(O(n /\sqrt{\log n})\) distinct distances. A recent celebrated paper of \textit{L. Guth} and \textit{N. H. Katz} [Ann. Math. (2) 181, No. 1, 155--190 (2015; Zbl 1310.52019)] essentially solved the distinct distances conjecture proving that \(D(n)= \Omega(n /{\log n})\). The paper under review studies the bipartite version of the distinct distances problem, which was first proposed by \textit{G. Elekes} [Combinatorica 15, No. 2, 167--174 (1995; Zbl 0827.52010)]: given \(m+n\) points in the plane, \(m\) of them red and \(n\) of them blue, what is \(D(m,n)\), the minimum number of distances between red and blue points, for all possible choices of the points? For \(2\leq m\leq n^{1/3}\), Elekes [loc. cit.] showed that \(D(m,n)=O(\sqrt{mn})\). The paper under review shows \(D(m,n)=\Omega(\sqrt{mn})\) for the same range, thus settling the distinct distances problem there. The proof adapts \textit{L. A. Székely}'s earlier technique for the distinct distances problem [Comb. Probab. Comput. 6, No. 3, 353--358 (1997; Zbl 0882.52007)]. For \(n^{1/3}\leq m \leq n\), the paper under review shows \(D(m,n)=\Omega(\sqrt{mn}/\log n )\) by modifying and extending the cited work of Guth and Katz.

Recommendations

• Bisector energy and few distinct distances
• Distinct distances on two lines
• On the Erdős distinct distances problem in the plane
• Bisectors and pinned distances
• On distinct sums and distinct distances.

Cites work

• A reduction for the distinct distances problem in \(\mathbb{R}^d\)
• Algebraic methods in discrete analogs of the Kakeya problem
• Circle grids and bipartite graphs of distances
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Crossing-Free Subgraphs
• Distinct distances from three points
• Distinct distances in the plane
• Distinct Distances on Algebraic Curves in the Plane
• Distinct distances on two lines
• Elementary structure of real algebraic varieties
• Extremal problems in discrete geometry
• scientific article; zbMATH DE number 6603592 (Why is no real title available?)
• scientific article; zbMATH DE number 52497 (Why is no real title available?)
• scientific article; zbMATH DE number 2145235 (Why is no real title available?)
• scientific article; zbMATH DE number 3999934 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• Incidences in three dimensions and distinct distances in the plane
• On distinct sums and distinct distances.
• On Sets of Distances of n Points
• On the Different Distances Determined by n Points
• On the Erdős distinct distances problem in the plane
• Research Problems in Discrete Geometry
• Some extremal problems in geometry
• The Erdős distance problem
• The number of different distances determined by a set of points in the Euclidean plane
• The number of different distances determined by n points in the plane

Cited in

(6)

• Circle grids and bipartite graphs of distances
• A reduction for the distinct distances problem in \(\mathbb{R}^d\)
• On distinct distances between a variety and a point set
• A refined energy bound for distinct perpendicular bisectors
• Distinct distances in homogeneous sets in Euclidean space
• Bisector energy and few distinct distances

This page was built for publication: On bipartite distinct distances in the plane

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