# 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. |

See All Seminars