String graphs have the Erdős–Hajnal property

Abstract

The following Ramsey-type question is one of the central problems in combinatorial geometry. Given a collection of certain geometric objects in the plane (e.g. segments, rectangles, convex sets, arcwise connected sets) of size $n$, what is the size of the largest subcollection in which either any two elements have a nonempty intersection, or any two elements are disjoint? We prove that there exists an absolute constant $c>0$ such that if $\mathcal{C}$ is a collection of $n$ curves in the plane, then $\mathcal{C}$ contains at least $n^c$ elements that are pairwise intersecting, or $n^c$ elements that are pairwise disjoint. This resolves a problem raised by Alon, Pach, Pinchasi, Radoičić and Sharir, and Fox and Pach. Furthermore, as any geometric object can be arbitrarily closely approximated by a curve, this shows that the answer to the aforementioned question is at least $n^c$ for any collection of $n$ geometric objects.