A sharp threshold phenomenon in string graphs

Abstract

We prove that for every $\epsilon >0$ there exists $\delta >0$ such that the following holds. Let $\mathcal{C}$ be a collection of $n$ curves in the plane such that there are at most $(\frac{1}{4}-\epsilon )\frac{n^2}{2}$ pairs of curves $\{\alpha ,\beta \}$ in $\mathcal{C}$ having a nonempty intersection. Then $\mathcal{C}$ contains two disjoint subsets $\mathcal{A}$ and $\mathcal{B}$ such that $|\mathcal{A}|=|\mathcal{B}|\ge \delta n$, and every $\alpha \in \mathcal{A}$ is disjoint from every $\beta \in \mathcal{B}$. On the other hand, for every positive integer $n$ there exists a collection $\mathcal{C}$ of $n$ curves in the plane such that there at most $(\frac{1}{4}+\epsilon )\frac{n^2}{2}$ pairs of curves $\{\alpha ,\beta \}$ having a nonempty intersection, but if $\mathcal{A},\mathcal{B}\subset \mathcal{C}$ are such that $|\mathcal{A}|=|\mathcal{B}|$ and $\alpha \cap \beta =\varnothing$ for every $(\alpha ,\beta )\in \mathcal{A}\times \mathcal{B}$, then $|\mathcal{A}|=|\mathcal{B}|=O(\frac{1}{\epsilon }\log n)$.

21 pages, 6 figures