On Erdős Chains in the Plane

2020/10/27 by Passant, Jonathan
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2010.14210

Abstract

Let P be a finite point set in ℝ² with the set of distance n-chains defined as Δ_n(P)=\(|p₁-p₂|,|p₂-p₃|,…,|p_n-p_n+1|):p_i ∈ P\. We show that for 2≤ n=O_|P|(1) we have |Δ_n(P)|\gtrsim \frac|P|ⁿlog^{(13)/(2)(n-1)}|P|. Our argument uses the energy construction of Elekes and a general version of Rudnev's rich-line bound implicit in Rudnev's recent hinge paper which allows one to iterate efficiently on highly intersecting nested subsets of Guth-Katz lines. Let G is a simple connected graph on m=O(1) vertices with m≥ 2. Define the graph-distance set Δ_G(P) as Δ_G(P) = \ (|p_i-p_j|)_\i,j\∈ E(G) : p_i,p_j ∈ P\. Combining with results of Guth and Katz and Rudnev with the above, if G has a Hamiltonian path we have |Δ_G(P)| \gtrsim \frac|P|^m-1polylog|P|. \endabstract

Related

• Almost sharp bounds on the number of discrete chains in the plane
• Finite point configurations in the plane, rigidity and Erdos problems
• Interpolation of point configurations in the discrete plane
• A new bound on Erdős distinct distances problem in the plane over prime fields
• On the Erdos distinct distance problem in the plane