MATH Seminar

Title: On the Erdos-Gyarfas distinct distances problem with local constraints
Seminar: Combinatorics
Speaker: Cosmin Pohoata of The California Institute of Technology
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2018-10-01 at 4:00PM
Venue: MSC E408
Download Flyer
Abstract: In 1946 Erdos asked to determine or estimate the minimum number of distinct distances determined by an n-element planar point set V. He showed that a square integer lattice determines \Theta(n/\sqrt{log n}) distinct distances, and conjectured that any n-element point set determines at least n^{1−o(1)} distinct distances. In 2010-2015, Guth and Katz answered Erdos’s question by proving that any n-element planar point set determines at least \Omega(n/log n) distinct distances. In this talk, we consider a variant of this problem by Erdos and Gyarfas. For integers n, p, q with p \geq q \geq 2, determine the minimum number D(n,p,q) of distinct distances determined by a planar n-element point set V with the property that any p points from V determine at least q distinct distance. In a recent paper, Fox, Pach and Suk prove that when q = {p \choose 2} - p + 6, D(n,p,q) is always at least n^{8/7 - o(1)}. We will discuss a recent improvement of their result and some new bounds for a related (graph theoretic) Ramsey problem of Erdos and Shelah which arise. This is joint work with Adam Sheffer.