Boris Bukh (Carnegie Mellon)

Topological Version of Pach's Overlap Theorem

Abstract for the Combinatorics and Geometry/Topology Seminars
2018 May 1

Consider the collection of all the simplices spanned by some n-point set in Rd. There are several results showing that simplices defined in this way must overlap very much. In this talk I focus on the generalization of these results to 'curvy' simplices.

Specifically, Pach showed that every d+1 sets of points, Q1, ..., Qd+1, in Rd contain linearly-sized subsets Pi in Qi such that all the transversal simplices that they span intersect. In joint work with Alfredo Hubard, we show, by means of an example, that a topological extension of Pach's theorem does not hold with subsets of size C(log n)1/(d-1). We show that this is tight in dimension 2, for all surfaces other than S2. Surprisingly, the optimal bound for S2 is (log n)1/2. This improves upon results of Barany, Meshulam, Nevo, Tancer.

To the Combinatorics Seminar Web page.