Аннотация:
A string graph is the intersection graph of curves in the plane. Building on previous works of Fox and Pach [1, 2], we prove that there exists an absolute constant $c>0$ such that if $G$ is a string graph on $n$ vertices, then $G$ contains either a clique or an independent set of size at least $n^c$.
[1] J. Fox and J. Pach, Erdös-Hajnal-type results on intersection patterns of geo-metric objects, in Horizons of combinatorics, G. O. H. Katona et al., eds., Bolyai Soc. Stud. Math. 17, Springer, Berlin, Heidelberg, (2008), 79—103.
\newine
[2] J. Fox and J. Pach, String graphs and incomparability graphs, Advances in Mathematics 230 (2012), 1381—1401.