A positive fraction mutually avoiding sets theorem

Abstract

Two sets $A$ and $B$ of points in the plane are \emph{mutually avoiding} if no line generated by any two points in $A$ intersects the convex hull of $B$, and vice versa. In 1994, Aronov, Erd\H os, Goddard, Kleitman, Klugerman, Pach, and Schulman showed that every set of $n$ points in the plane in general position contains a pair of mutually avoiding sets each of size at least $\sqrt{n/12}$. As a corollary, their result implies that for every set of $n$ points in the plane in general position one can find at least $\sqrt{n/12}$ segments, each joining two of the points, such that these segments are pairwise crossing. In this note, we prove a fractional version of their theorem: for every $k>0$ there is a constant ${\epsilon }_k>0$ such that any sufficiently large point set $P$ in the plane contains $2k$ subsets $A_1,\dots ,A_k,B_1,\dots ,B_k$, each of size at least ${\epsilon }_k|P|$, such that every pair of sets $A=\{a_1,\dots ,a_k\}$ and $B=\{b_1,\dots ,b_k\}$, with $a_i\in A_i$ and $b_i\in B_i$, are mutually avoiding. Moreover, we show that ${\epsilon }_k=\Omega (1/k^4)$. Similar results are obtained in higher dimensions

10 pages, 2 figures