Natan Rubin: Two questions on crossings in geometric (hyper-)graphs

Description of video

Date: 10/14/22
Speaker :Rubin Natan

We consider two long standing open problems in the study of edge intersections in geometric (hyper-)graphs.
1. Given a geometric graph with n vertices and n^{1+o(1)}t edges, do there exist t pairwise crossing edges?
2. Estimate the largest possible number f_d(n,h) so that a (d+1)-uniform geometric hypergraph in d-space with at least n^{d+1}h hyperedges (i.e., d-simplices) must contain f_d(n,h) simplices that are pierced by a single point.
The first question continues a long line of quasi-planarity results which positively settle it for near-constant t, whereas the second question comes hand in hand with the study of weak epsilon-nets and k-sets. (Any progress on the second question, a.k.a. the second selection theorem, would lead to better bounds for k-sets in dimension 5 and higher. )
The existing methods offer satisfactory and highly non-trivial answers for the very dense scenarios of both questions, which have been found lacking in the “intermediate range”.
The talk is partly based on joint work with J. Pach and G. Tardos.