Combinatorics Seminar - Andrew Suk


Speaker: Andrew Suk

Title: Unavoidable patterns in simple topological graphs

Abstract: A simple topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by non-self-intersecting arcs connecting the corresponding points, with the property that any two edges have at most one point in common. In 2003, Pach-Solymosi-Toth showed that every n-vertex complete simple topological graph contains a topological subgraph on m = Omega(\log^{1/8} n) vertices that is weakly isomorphic to the complete convex geometric graph or to the complete twisted graph on m vertices. Here, we improve this bound to (log n)^{1/4 - o(1)}. I will also discuss other related problems as well.
This is joint work with Ji Zeng.