On a topological version of Pach's overlap theorem

Abstract

Pach showed that every $d+1$ sets of points $Q_1,\dots ,Q_{d+1}\subset {\mathbb{R}}^d$ contain linearly-sized subsets $P_i\subset Q_i$ such that all the transversal simplices that they span intersect. 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 ${\mathbb{S}}^2$. Surprisingly, the optimal bound for ${\mathbb{S}}^2$ in the topological version of Pach's theorem is of the order $(\log n{)}^{1/2}$. We conjecture that, among higher-dimensional manifolds, spheres are similarly distinguished. This improves upon the results of Bárány, Meshulam, Nevo and Tancer.

9 pages, 2 figures

References in corpus (2)

• Hypergraph containers
• Graphs with many r-cliques have large complete r-partite subgraphs