A parity Erdős-Hajnal theorem for $t$-intersecting curves

Abstract

For every fixed $t\ge 1$, we prove a parity analogue of the mighty Erdős-Hajnal property for $t$-intersecting curves in the plane. Let $\mathcal{B}$ be a set of blue curves and $\mathcal{G}$ a set of green curves in the plane such that $\mathcal{B}\cup \mathcal{G}$ is a collection of $t$-intersecting curves in general position. We show that there exist subfamilies ${\mathcal{B}}^{\prime }\subseteq \mathcal{B}$ and ${\mathcal{G}}^{\prime }\subseteq \mathcal{G}$ such that $|{\mathcal{B}}^{\prime }|\ge \epsilon |\mathcal{B}|$ and $|{\mathcal{G}}^{\prime }|\ge \epsilon |\mathcal{G}|$, where $\epsilon >0$ depends only on $t$, such that either every pair in ${\mathcal{B}}^{\prime }\times {\mathcal{G}}^{\prime }$ intersects an even number of times or every such pair intersects an odd number of times. For $t=1$, this recovers the theorem of Fox, Pach, and Suk for pseudo-segments. As an application, we show that every $n$-vertex topological graph with edges forming a $t$-intersecting family and with no $k$ edges that pairwise cross an odd number of times has at most $n(\log n{)}^{O_t(\log k)}$ edges.

19 pages