# Line transversals in families of connected sets in the plane

Daniel McGinnis  and  Shira Zerbib

###### Abstract.

We prove that if a family of compact connected sets in the plane has the
property that every three members of it are intersected by a line, then there
are three lines intersecting all the sets in the family. This answers a
question of Eckhoff from 1993 [3], who proved that, under the same condition,
there are four lines intersecting all the sets. In fact, we prove a colorful
version of this result, under weakened conditions on the sets. A triple of
sets $A,B,C$ in the plane is said to be a tight if $\textrm{conv}(A\cup
B)\cap\textrm{conv}(A\cup C)\cap\textrm{conv}(B\cap C)\neq\emptyset.$ This
notion was first introduced by Holmsen in [6], where he showed that if
$\mathcal{F}$ is a family of compact convex sets in the plane in which every
three sets form a tight triple, then there is a line intersecting at least
$\frac{1}{8}|\mathcal{F}|$ members of $\mathcal{F}$. Here we prove that if
$\mathcal{F}_{1},\dots,\mathcal{F}_{6}$ are families of compact connected sets
in the plane such that every three sets, chosen from three distinct families
$\mathcal{F}_{i}$, form a tight triple, then there exists $1\leq j\leq 6$ and
three lines intersecting every member of $\mathcal{F}_{j}$. In particular,
this improves $\frac{1}{8}$ to $\frac{1}{3}$ in Holmsen’s result.

D. McGinnis: Department of Mathematics, Iowa State University, USA.
<EMAIL_ADDRESS>D. McGinnis was supported by NSF grant DMS-1839918 (RTG)

S. Zerbib: Department of Mathematics, Iowa State University, USA.
<EMAIL_ADDRESS>S. Zerbib was supported by NSF grant DMS-1953929.

##  1\. Introduction

Let $\mathcal{F}$ be a family of sets in the plane. We say that $\mathcal{F}$
has property $T(r)$ if every $r$ or fewer sets in $\mathcal{F}$ admit a line
transversal, that is, there exists a line intersecting these sets. We say that
$\mathcal{F}$ is pierced by $k$ lines if there are $k$ lines in the plane
whose union intersects all the sets in $\mathcal{F}$. The line-piercing number
of the family is the minimum $k$ so that $\mathcal{F}$ is pierced by $k$
lines.

The problem of bounding the line-piercing numbers of families of compact
convex sets in the plane with the $T(r)$ property has been investigated since
the 1960’s. In 1964 Eckhoff [1] proved that if a family of compact convex sets
satisfies the $T(4)$ property then it can be pierced by two lines. In 1974 he
gave an example of a family of compact convex sets satisfying the $T(3)$
property that is not pierced by two lines [2]. Various upper bounds on the
line-piercing numbers were proved when further restrictions on the sets are
imposed (see [3] for more details).

For a while it was not clear whether the $T(3)$ property implies a finite
universal upper bound on the line-piercing number. This question was
eventually resolved in 1975 by Kramer [9], who showed that a family of compact
convex sets in $\mathbb{R}^{2}$ with the $T(3)$ property is pierced by 5
lines. Finally, in 1993 Eckhoff [3] proved that such families are pierced by 4
lines, and asked whether this bound can be improved to 3.

Quantitative versions have been studied too. In 1980, Katchalski and Liu [7]
showed the existence of a constant $0<\alpha(r)<1$, so that every finite
family $\mathcal{F}$ of convex sets in the plane with the $T(r)$ property
admits a line intersecting $\alpha(r)|\mathcal{F}|$ of its members. In 2010
Holmsen [5] showed that
$\big{(}\frac{2}{r(r-1)}\big{)}^{\frac{1}{r-2}}\leq\alpha(r)\leq\frac{r-2}{r-1}$,
and in particular, $\frac{1}{3}\leq\alpha(3)\leq\frac{1}{2}.$

In [6], Holmsen introduced the notion of tight triples. Three compact,
connected sets in the plane $A,B,C$ are said to be a tight triple if

$\textrm{conv}(A\cup B)\cap\textrm{conv}(A\cup C)\cap\textrm{conv}(B\cap
C)\neq\emptyset.$

We will call a family of sets in the plane a family of tight triples if every
three sets in the family form a tight triple. Note that if $A,B,C$ has a line
transversal, then it is a tight triple. Holmsen [6] proved that if
$\mathcal{F}$ is a family of tight triples in which every set is compact and
convex, then there is a line intersecting at least $\frac{1}{8}|\mathcal{F}|$
members of $\mathcal{F}$.

The sets investigated in all the above results are assumed to be convex, but
the results apply also for families of connected sets. This follows from the
fact that if $S$ is a connected set in $\mathbb{R}^{2}$ and $\ell$ is a line
intersecting $\text{conv}(S)$ then $\ell$ must intersect $S$. Similarly, three
connected sets $A,B,C$ form a tight triple if and only if
$\textrm{conv}(A),\textrm{conv}(B),\textrm{conv}(C)$ form a tight triple.

In this paper we show that the line-piercing number of a family of compact
connected tight triples is at most 3. This improves the $\frac{1}{8}$ in
Holmsen’s result to $\frac{1}{3}$.

In fact, we show a colorful version of this fact.

######  Theorem 1.1.

Let $\mathcal{F}_{1},\dots,\mathcal{F}_{6}$ be families of compact connected
sets in $\mathbb{R}^{2}$. If every three sets
$A_{1}\in\mathcal{F}_{i_{1}},A_{2}\in\mathcal{F}_{i_{2}},A_{3}\in\mathcal{F}_{i_{3}}$,
$1\leq i_{1}<i_{2}<i_{3}\leq 6$, form a tight triple, then there exists
$i\in[6]$ such that the line-piercing number of $\mathcal{F}_{i}$ is at most
$3$.

In particular, if $\mathcal{F}$ is a family with the $T(3)$ property and we
take $\mathcal{F}_{i}=\mathcal{F}$ for $1\leq i\leq 6$, then Theorem 1.1
implies that $\mathcal{F}$ has line-piercing number at most three. This gives
an affirmative answer to Eckhoff’s question. This also gives another proof to
Holmsen’s result $\alpha(3)\geq 1/3$.

Our main tool is the colorful version of the topological KKM theorem [8] due
to Gale [4]. Let $\Delta^{n-1}=\\{(x_{1},\dots,x_{n})\in\mathbb{R}^{n}\mid
x_{i}\geq 0,\sum_{i=1}^{n}x_{i}=1\\}$ denote the $(n-1)$-dimensional simplex
in $\mathbb{R}^{n}$, whose vertices are the canonical basis vectors
$e_{1},\dots,e_{n}$. Let $S_{n}$ be the group of permutations on $[n]$.

######  Theorem 1.2 (The colorful KKM theorem [4]).

Let $A_{1}^{i},\dots,A_{n}^{i}$, $i\in[n]$, be open sets of $\Delta^{n-1}$,
such that for every $i\in[n]$ and for every face $\sigma$ of $\Delta^{n-1}$ we
have $\sigma\subset\bigcup_{e_{j}\in\sigma}A_{j}^{i}$. Then there exists a
permutation $\pi\in S_{n}$ such that
$\cap_{i=1}^{n}A^{\pi(i)}_{i}\neq\emptyset$.

##  2\. Proof of Theorem 1.1

Throughout the proof, addition in integers is taken modulo 6. For
$a,b\in\mathbb{R}^{2}$, let $[a,b]=\text{conv}\\{a,b\\}$ be the line segment
connecting $a,b$.

As is explained in [3], the compactness of the sets in each $\mathcal{F}_{j}$
allows us to assume that $\mathcal{F}_{j}$ is finite. Thus we may scale the
plane so that every set in $\mathcal{F}_{j}$ is contained in the unit disk $D$
for each $j$. Denote by $U$ the unit circle. Let $f(t)$ be a parameterization
of $U$ defined by $f(t)=(\textrm{cos}(2\pi t),\textrm{sin}(2\pi t))$.

A point $x=(x_{1},\dots,x_{6})\in\Delta^{5}$ corresponds to $6$ points on $U$
given by $f_{i}(x)=f(\sum_{j=1}^{i}x_{j})$ for $1\leq i\leq 6$. Let
$l_{1}(x)=l_{4}(x)=[f_{1}(x),f_{4}(x)]$,
$l_{2}(x)=l_{5}(x)=[f_{2}(x),f_{5}(x)]$, and
$l_{3}(x)=l_{6}(x)=[f_{3}(x),f_{6}(x)]$.

For $i=1,\dots,6$ let $R^{i}_{x}$ be the interior of the region bounded by
$l_{i-1}(x)$, $l_{i}(x)$ and the arc on $U$ connecting $f_{i-1}(x)$ and
$f_{i}(x)$ (see Figure 1). Notice that $R^{i}_{x}=\emptyset$ when $x_{i}=0$.
Also, it is possible that some of the regions $R^{i}_{x}$ intersect.

$f_{5}(x)$$f_{1}(x)$$f_{2}(x)$$f_{4}(x)$$f_{6}(x)=(1,0)$$f_{3}(x)$$R^{5}_{x}$$R^{6}_{x}$$R^{2}_{x}$$R^{3}_{x}$$R^{1}_{x}$$R^{4}_{x}$

$f_{6}(x)$$f_{2}(x)$$f_{3}(x)$$f_{5}(x)$$f_{1}(x)$$f_{4}(x)$$R^{6}_{x}$$R^{1}_{x}$$R^{3}_{x}$$R^{4}_{x}$$R^{2}_{x}$$R^{5}_{x}$

Figure 1. A point $x\in\Delta^{5}$ corresponds to six regions $R_{x}^{i}$. The
regions $R^{1}_{p},R^{3}_{p},R^{5}_{p}$ are pairwise disjoint (on the right)
or the regions $R^{2}_{p},R^{4}_{p},R^{6}_{p}$ are pairwise disjoint (on the
left), depending on the orientation of the triangle bounded by the lines
$l_{1}(x),l_{2}(x),l_{3}(x)$.

Set $1\leq j\leq 6$ and let $A_{i}^{j}$ be the set of points $x\in\Delta^{5}$
so that $R^{i}_{x}$ contains a set $F\in\mathcal{F}_{j}$. Since the sets
$F\in\mathcal{F}_{j}$ are closed, $A_{i}^{j}$ is open. If there is some
$x\in\Delta^{5}$ for which $x\notin\bigcup_{i=1}^{6}A_{i}^{j}$, then since the
sets in $\mathcal{F}_{j}$ are connected, every set in $\mathcal{F}_{j}$ must
intersect $\bigcup_{i=1}^{3}l_{i}(x)$, and we are done. So we assume for
contradiction that $\Delta^{5}=\bigcup_{i=1}^{6}A_{i}^{j}$ for all $j$.
Observe that if $x\in\textrm{conv}\\{e_{i}:i\in I\\}$ for some $I\subset[6]$
then $R^{k}_{x}=\emptyset$ for $k\notin I$, and therefore, $x\in\bigcup_{i\in
I}A_{i}^{j}$ for all $j$. This shows that the conditions of Theorem 1.2 hold.

Thus, by Theorem 1.2, there exists some permutation $\pi\in S_{6}$ and a point
$p=(p_{1},\dots,p_{6})\in\bigcap_{i=1}^{6}A_{i}^{\pi(i)}$. Therefore, each of
the open regions $R^{i}_{p}$ contains a set $S_{i}\in\mathcal{F}_{\pi(i)}$,
$i=1,\dots,6$, and in particular $R^{i}_{p}\neq\emptyset$ and thus $p_{i}\neq
0$ for all $i$. We claim that at least one of the triples
$\\{S_{1},S_{3},S_{5}\\}$ or $\\{S_{2},S_{4},S_{6}\\}$ is not a tight triple.
To see this, note that the regions $R^{1}_{p},R^{3}_{p},R^{5}_{p}$ are
pairwise disjoint or the regions $R^{2}_{p},R^{4}_{p},R^{6}_{p}$ are pairwise
disjoint (depending on the orientation of the triangle bounded by the lines
$l_{1},l_{2},l_{3}$, see Figure 1). Without loss of generality, we assume
$R^{1}_{p},R^{3}_{p},R^{5}_{p}$ are pairwise disjoint, and in this case, the
three sets $S_{1},S_{3},S_{5}$ is not a tight triple. This is a contradiction.

##  3\. Concluding remarks

The proof of Theorem 1.1 implies a slightly stronger result: when each
$\mathcal{F}_{i}$ is finite, one can fix a point lying on one of the three
piercing lines of $\mathcal{F}_{i}$, as long as this point is outside
$\text{conv}(\cup_{i}\mathcal{F}_{i})$.

A similar proof can be used to prove a colorful version of Eckhoff’s result
that $T(4)$ families are pierced by two lines.

######  Theorem 3.1.

Let $\mathcal{F}_{1},\dots,\mathcal{F}_{4}$ be families of compact, connected
sets in the plane such that any collection of four sets, one from each
$\mathcal{F}_{i}$, has a line transversal. Then for some $i\in[4]$,
$\mathcal{F}_{i}$ has line piercing number at most 2.

This can be proved by associating a point in $\Delta^{3}$ with two lines and
applying a similar argument as in the proof of Theorem 1.1

When each of the families $\mathcal{F}_{i}$ is finite, one may drop the
condition that the sets are compact. This is because we may replace each set
$S\in\mathcal{F}_{j}$ with a compact, convex set
$S^{\prime}\subset\text{conv}(S)$ such that the resulting family is still a
family of tight triples.

##  4\. Acknowledgement

We are grateful to Andreas Holmsen for many helpful discussions and for
telling us about Eckhoff’s paper [3]. We are also grateful to Ron Aharoni for
commenting on an early version of this paper.

## References

  * [1] J. Eckhoff, Transversalenprobleme vom Gallaischen Typ, Dissertation, Universität Göttingen, 1969\.
  * [2] J. Eckhoff, Transversatenprobleme in der Ebene, Arch. Math. 24 (1973), 195–202.
  * [3] J. Eckhoff, A Gallai-type transversal problem in the plane. Discrete Comput. Geom. 9 (1993), no. 2, 203–214.
  * [4] D. Gale.  Equilibrium in a discrete exchange economy with money.  Internat. J. Game Theory, 13(1):61–64, 1984.
  * [5] A. Holmsen, New results for T(k)-families in the plane. Mathematika 56 (2010), no. 1, 86–92.
  * [6] A. Holmsen.  Geometric transversal theory: $T(3)$-families in the plane.  In Geometry—intuitive, discrete, and convex, volume 24 of Bolyai Soc. Math. Stud., pages 187–203. János Bolyai Math. Soc., Budapest, 2013.
  * [7] M. Katchalski and A. Liu, Symmetric twins and common transversals. Pacific J. Math. 86 (1980), 513–515.
  * [8] B. Knaster, C. Kuratowski, and S. Mazurkiewicz.  Ein beweis des fixpunktsatzes für $n$-dimensionale simplexe.  Fund. Math., 14(1):132–137, 1929.
  * [9] D. Kramer, Transversalenprobleme vom Hellyschen und Gallaischen Typ, Dissertation, Universität Dortmund, 1974.