A Family of Convex Sets in the Plane Satisfying the (4, 3)-Property can be Pierced by Nine Points

Abstract

We prove that every finite family of convex sets in the plane satisfying the (4, 3)-property can be pierced by nine points. This improves the bound of 13 proved by Kleitman et al. (Combinatorica 21(2), 221–232 (2001)).

1 Introduction

For positive integers $p\ge q$, a family of sets $\mathscr {C}$ is said to satisfy the (p, q)-property if for every p sets, some q have a point in common. We say that $\mathscr {C}$ can be pierced by m points if there exists a set of size at most m intersecting every element in $\mathscr {C}$. The piercing number $\tau (\mathscr {C})$ of $\mathscr {C}$ is the minimum m so that $\mathscr {C}$ can be pierced by m points.

In 1957 Hadwiger and Debrunner [2] conjectured that for every given positive integers $p\ge q > d$, there exists a (smallest) constant $HD _d(p,q)$ such that every finite family $\mathscr {C}$ of convex sets in $\mathbb {R}^d$ satisfying the (p, q)-property has $\tau (\mathscr {C})\le HD _d(p,q)$. This conjecture was proved by Alon and Kleitman in 1992 [1].

In general, the bounds on $HD _d(p,q)$ given by Alon and Kleitman’s proof are far from optimal. The first case where $HD _d(p,q)$ is not known is when $d=2$, $p=4$, and $q=3$. In this case, the bound in $HD _d(p,q)$ given by the Alon–Kleitman proof is 343, while there is no known example of a family of convex sets in the plane that satisfy the (4, 3)-property and cannot be pierced by three points. We note that improvements on general upper bounds for $HD _d(p,q)$ were made in [4].

In 2001, Gyárfás et al. [5] proved that $HD _2(4,3)\le 13$, and since then this bound has seen no improvement. In this paper we prove that $HD _2(4,3)\le 9$:

Theorem 1.1

If $\mathscr {C}$ is a finite family of convex sets in $\mathbb {R}^2$ such that for any four sets, three have a point in common, then $\tau (\mathscr {C})\le 9$.

The main tools in the proof are the following two theorems, and a geometrical analysis. Let $\varDelta ^{n-1}\subset \mathbb {R}^n$ denote the $n-1$-dimensional simplex with vertex set $e_1,\dots ,e_n$ (the standard basis vectors in $\mathbb {R}^n$). The following version of the KKM Theorem was proven in [7].

Theorem 1.2

Let $A_1,\dots ,A_{n}$ be open sets such that for every $I\subseteq \{1,\dots ,n\}$, $\bigcup _I A_i\supseteq {\text {conv}}{\{e_i\,|\,i\in I\}}$. Then $\bigcap _{i=1}^{n} A_i\ne \emptyset$.

We note that Theorem 1.2 stated for closed sets $A_1,\dots ,A_n$ is the original KKM Theorem, which was proven in [6].

A matching in a family of sets $\mathscr {F}$ is a subset of pairwise disjoint sets in $\mathscr {F}$. The matching number $\nu (\mathscr {F})$ is the maximum size of a matching in $\mathscr {F}$. Let $L_1,L_2$ be two homeomorphic copies of the real line. A 2-interval is a union $I_1\cup I_2$, where $I_i$ is an interval on $L_i$.

Theorem 1.3

(Tardos [8]) If $\mathscr {F}$ is a family of 2-intervals then $\tau (\mathscr {F}) \le 2\nu (\mathscr {F})$.

2 Using the KKM Theorem

Let $\mathscr {C}$ be a finite family of convex sets satisfying the (4, 3)-property. We may assume that the sets are compact by considering a set S containing a point in each intersection of sets in $\mathscr {C}$, and replacing every set $C\in \mathscr {C}$ by ${\text {conv}}{\{s\in S \mid s\in C\}}$. Furthermore, we may assume that each set in $\mathscr {C}$ has a non-empty interior. To see this, let $B_\epsilon$ be the closed ball of radius $\epsilon$ with the center at the origin, and let $\mathscr {C}_\epsilon =\{C+B_\epsilon \mid C\in \mathscr {C}\}$. Then $\mathscr {C}_\epsilon$ also satisfies the (4, 3)-property. It follows from the compactness of the sets in $\mathscr {C}$ that if $\mathscr {C}_\epsilon$ can be pierced by nine points for all $\epsilon >0$, then $\mathscr {C}$ can be pierced by nine points. Therefore, we may assume each set in $\mathscr {C}$ has a non-empty interior. In particular, $\mathscr {C}$ contains neither points nor line segments.

We may clearly assume $|\mathscr {C}| \ge 4$. We scale the plane so that all the sets in $\mathscr {C}$ are contained in the open unit disk, which we denote by D. Let f be a parameterization of the unit circle defined by

$$f(t)=(\cos 2\pi t,\sin 2\pi t)$$

for $t\in [0,1]$. For two points a, b in the plane, let $\overline{ab}$ be the line through a and b and let [a, b] be the line segment with a and b as endpoints.

Let $\varDelta =\varDelta ^3={\text {conv}}{\{e_1,e_2,e_3,e_4\}}\subset \mathbb {R}^4$ be the standard 3-dimensional simplex, and let $x=(x_1,x_2,x_3,x_4)\in \varDelta$. Note that $x_i\in [0,1]$ and $\sum _{i=1}^4 x_i=1$. For $1\le i\le 4$, define $R^i_x$ to be the interior of the region bounded by the arc along the circle from $f\bigl (\sum _{j=1}^{i-1}x_j\bigr )$ to $f\bigl (\sum _{j=1}^{i}x_j\bigr )$ (an empty sum is understood to be 0) and by the line segments $[(1,0),f(x_1+x_2)]$ and $[f(x_1),f(x_1+x_2+x_3)]$ (see Fig. 1). Notice that if $x_i=0$, then $R^i_x=\emptyset$.

Fig. 1

A point $x\in \varDelta ^3$ corresponds to four regions $R_x^i$

For every $1\le i\le 4$ define a subset $A_i$ of $\varDelta$ as follows: $x\in \varDelta ^3$ is in $A_i$ if and only if there exist three sets $C_1,C_2,C_3\in \mathscr {C}$ such that $C_1\cap C_2 \cap C_3\ne \emptyset$ and $C_j\cap C_k \subset R^i_x$ for all $1\le j<k\le 3$ (see Fig. 2). Observe that $A_i$ is open. For every $x\in \varDelta$ and $C\in \mathscr {C}$ let $I_C$ be the (possibly empty) 2-interval

$$\begin{aligned} (C\cap [(1,0),f(x_1+x_2)])\cup (C\cap [f(x_1),f(x_1+x_2+x_3)]). \end{aligned}$$

Lemma 2.1

Suppose there exists $x\in \varDelta \setminus \bigcup _{i=1}^4A_i$. Then there exist two points a, b such that if $a,b\notin C$ then $I_C\ne \emptyset$.

Proof

Assume that $x\in \varDelta \setminus \bigcup _{i=1}^4A_i$. Note that since $\mathscr {C}$ does not contain three pairwise non-intersecting sets, at most two of the regions $R^i_x$ can contain a set in $\mathscr {C}$.

We claim for every $i\le 4$, the region $R^i_x$ contains at most two sets in $\mathscr {C}$. Indeed, assume to the contrary that $R^i_x$ contains three sets $C_1,C_2,C_3 \in \mathscr {C}$. Then $C_1\cap C_2 \cap C_3=\emptyset$ since $x\notin A_i$. Applying the (4, 3) property to $C_1,C_2,C_3$ and some additional set $F\in \mathscr {C}$, we obtain that $C_j\cap C_k \cap F \ne \emptyset$ for some $1\le j<k \le 3$, and all pairwise intersections of $C_j,C_k,F$ are contained in $R^i_x$, contradicting $x\notin A_i$.

If there is only one region $R^i_x$ containing sets in $\mathscr {C}$, then since there are at most two such sets, there are two points that pierce them. If there are two regions $R^i_x$ and $R^j_x$ containing sets in $\mathscr {C}$, then if there are two sets contained in $R^i_x$ (or $R^j_x$), they must intersect. Otherwise these two sets together with a set in $R^j_x$ (or $R^i_x$, respectively) will be three pairwise non-intersecting sets, a contradiction since $\mathscr {C}$ has the (4, 3)-property. Therefore, there is a point piercing the sets contained in $R^i_x$ and a point piercing the sets in $R^j_x$ and we are done. $\square$

Fig. 2

Three sets $C_1,C_2,C_3\in C$ with $C_1\cap C_2 \cap C_3\ne \emptyset$ and $C_j\cap C_k \subset R^1_x$ for all $1\le j< k \le 3$, implying $x=(x_1,x_2,x_3,x_4) \in A_1$

Theorem 2.2

If there exists $x\in \varDelta \setminus \bigcup _{i=1}^4A_i$, then $\tau (\mathscr {C})\le 8$.

Proof

Let $\mathscr {D}= \{C\in \mathscr {C}\mid I_C \ne \emptyset \}$. We will show that $\tau (\mathscr {D})\le 6$. Together with Lemma 2.1 this will imply the theorem.

Let $\mathscr {I}=\{I_C\,|\,C\in \mathscr {D}\}$. Let $C_1,C_2,C_3,C_4\in \mathscr {D}$ be four sets. Some three, say $C_1,C_2,C_3$, intersect by the (4, 3)-property. Since $x\notin \bigcup _{i=1}^4 A_i$, the intersection of two of these three sets, say $C_1 \cap C_2$, must intersect either $[(1,0),f(x_1+x_2)]$ or $[f(x_1),f(x_1+x_2+x_3)]$. In other words, $I_{C_1} \cap I_{C_2} \ne \emptyset$. This shows that $\mathscr {I}$ has no four pairwise disjoint elements, implying $\nu (\mathscr {I})\le 3$. Thus, by Theorem 1.3, $\tau (\mathscr {D})\le \tau (\mathscr {I})\le 6$. $\square$

By Theorem 2.2 we may assume that $\varDelta \subset \bigcup _{i=1}^4 A_i$. We claim that in this case the sets $A_1,\dots ,A_4$ satisfy the conditions of Theorem 1.2. Indeed, let $I\subset [4]$, and let $y\in {\text {conv}}{\{e_i \,|\,i\in I\}}$. Then for all $j\in [4]\setminus I$, we have $R_y^j=\emptyset$, implying $y\notin A_j$. Since $y \in \bigcup _{i=1}^4 A_i$, we have that $y \in \bigcup _{i\in I} A_i$. Thus, by Theorem 1.2 we have:

Theorem 2.3

If $\varDelta \subset \bigcup _{i=1}^4 A_i$, then there exists $x\in \bigcap _{i=1}^4 A_i$.

For the rest of the paper we fix $x \in \bigcap _{i=1}^4 A_i$. Let $R^i_x=R^i$, and let $f_1=(1,0)$, $f_2=f(x_1)$, $f_3=f(x_1+x_2)$, and $f_4=f(x_1+x_2+x_3)$. Let c be the intersection point of $[f_1,f_2]$ and $[f_2,f_4]$, and let $\mathscr {C}^* = \{C\in \mathscr {C}\mid c \notin C \}$. Note that $\bigcap _{i=1}^4 A_i$ is an open set, so we may shift x slightly to ensure that c does not lie on the boundary of any set in $\mathscr {C}$ and neither of the segments $[f_1,f_3]$ or $[f_2,f_4]$ meets the boundary of any set in $\mathscr {C}$ and contains the set in one of its closed halfspaces. We use $\overline{R^i}$ to denote the topological closure of $R^i$.

Proposition 2.4

If $C\in \mathscr {C}^*$, then there exists some i for which $C\cap R^i=\emptyset$.

Proof

Assume C has a point $p_i$ in each $R^i$. Then since C is convex, it contains the points $q_1=[p_1,p_2] \cap [f_2,f_4]$ and $q_2=[p_3,p_4]\cap [f_2,f_4]$. Since $q_1$ and $q_2$ lie in two different hyperplanes defined by the line $\overline{f_1f_3}$, C must contain c, a contradiction.

$\square$

Let $\mathscr {C}_i$ denote the family of sets in $\mathscr {C}^*$ that are disjoint from $R^i$. By Proposition 2.4, we have $\mathscr {C}^*=\bigcup _{i=1}^4\mathscr {C}_i$. In the remainder of the paper we prove the following:

Theorem 2.5

For every $i\le 4$, $\tau (\mathscr {C}_i) \le 2$.

This will imply that $\mathscr {C}$ can be pierced by nine points: two points for each $\mathscr {C}_i$ and the point c.

3 Piercing $\mathscr {C}_i$ by Two Points

In this section we prove Theorem 2.5. Without loss of generality we prove the theorem for $\mathscr {C}_1$.

3.1 Preliminary Definitions and Observations

Let $C_1,C_2,C_3 \in \mathscr {C}$ be the three sets witnessing the fact that $x\in A_1$; so $C_1\cap C_2 \cap C_3\ne \emptyset$ and $C_j\cap C_k \subset R^1$ for all $1\le j< k \le 3$.

If there are two sets $F_1,F_2\in \mathscr {C}_1$ that do not intersect, then $F_1,F_2,C_1,C_2$ do not satisfy the (4, 3)-property. Thus every two sets in $\mathscr {C}_1$ intersect. Also, if for some $1\le i \le 3$ we have $C_i\subset R^1$, then again by the (4, 3)-property every three sets in $\mathscr {C}_1$ have a common point. This implies by Helly’s theorem [3] that $\tau (\mathscr {C}_1)=1$. So we may assume that no $C_i$ is contained in $R^1$.

Let $L_1$ be the line $\overline{f_1f_3}$ and let $L_2$ be the line $\overline{f_2f_4}$ (see Fig. 3).

Fig. 3

The lines $L_1$ (in red) and $L_2$ (in blue)

By our assumption $C_i$ is not contained in $R^1$ for $1\le i\le 3$, and thus $C_i \setminus R^1$ has at least one non-empty connected component. The next proposition shows that $C_i \setminus R^1$ has at most two connected components.

Proposition 3.1

For every $1\le i \le 3$, the set $C_i \setminus R^1$ has at most two connected components. Moreover, if $C_i \setminus R^1$ has two components, then the components are $C_i\cap \overline{R^2}$ and $C_i\cap \overline{R^4}$ and hence are convex.

Proof

If $C_i$ contains c, then $C_i \setminus R^1$ has one component because the line segment from any point in $\mathbb {R}^2\setminus R^1$ to c is contained in $\mathbb {R}^2\setminus R^1$. So assume $C_i$ does not contain c. Then it must have a point in either $\overline{R^2}$ or $\overline{R^4}$, without loss of generality, in $\overline{R^2}$.

Suppose $C_i$ contains a point in $\overline{R^3}$. Since $C_i$ does not contain c but contains points in the three regions $\overline{R^1},\overline{R^2},\overline{R^3}$, then by Proposition 2.4 it cannot contain a point in $\overline{R^4}$. Thus $C_i\setminus R^1=C_i\cap (\overline{R^2}\cup \overline{R^3})$. This means that $C_i\setminus R^1$ is an intersection of two convex sets, hence it is convex and has only one component.

Thus, if $C_i\setminus R^1$ has more than one component, then $C_i$ does not have a point in $\overline{R^3}$. In this case the components of $C_i\setminus R^1$ are $C_i\cap \overline{R^2}$ and $C_i\cap \overline{R^4}$ both of which are convex. $\square$

Let $Z=[f_1,c]\cup [c,f_2]$. We think of Z as starting at $f_1$ and ending at $f_2$. Thus a point $a\in Z$ comes before a point $b\in Z$ if the distance along Z from a to $f_1$ on Z is smaller than the distance from b to $f_1$ on Z.

Let $I_i^1=C_i \cap [f_1,c]$, $I_i^2=C_i\cap [c,f_2]$, and $I_i=C_i\cap Z$. Because each $C_i$ has a non-empty interior and our choice of c, none of $I_i^1$, $I_i^2$, or $I_i$ consists of a single point, or has c as one of its endpoints. It is possible, however, that one of $I_i^1$ or $I_i^2$ are empty.

For any interval (i.e., connected set) I on Z, let r(I) be the endpoint of I that comes first on Z, and let $\ell (I)$ be the other endpoint. Given a convex set C and a point p on the boundary of C, a supporting line for C at p is a line L passing through p that contains C in one of the closed halfspaces defined by L. For $1\le i\le 3$, let $C_i'=C_i\setminus R^1$.

Definition 3.2

Let X be a connected component of $C_i'$, and let $I=X\cap Z$ (so I is an interval on Z). Define $S_i^r(I)$ and $S_i^\ell (I)$ to be some supporting line for $C_i$ at the point r(I) and $\ell (I)$, respectively (see Fig. 4).

Because we chose $x\in \bigcap _i A_i$ so that neither $L_1$ nor $L_2$ meet the boundary of any set in $\mathscr {C}$ and contains the set in one its halfspaces, $S_i^r(I)$ and $S_i^\ell (I)$ are not equal to $L_1$ or $L_2$ for all i.

Fig. 4

Definition 3.2: the lines $S_i^\ell (I_i)$ (in blue) and $S_i^r(I_i)$ (in red)

Definition 3.3

Assume $C_i'$ has two components $X_1=C_i'\cap \overline{R^4}$ and $X_2=C_i'\cap \overline{R^2}$. We define $S_i'$ to be a piece-wise linear curve as follows (see Fig. 5):

$$\begin{aligned} S_i'=(S_i^\ell (I_i^1)\cap \overline{R^4})\cup [\ell (I_i^1),r(I_i^2)]\cup (S_i^r(I_i^2)\cap \overline{R^2}). \end{aligned}$$

Note that $S_i'$ lies in the closed halfspace defined by the line between the points $r(I_i^1)$ and $\ell (I_i^2)$ containing $f_1$ and $f_2$.

Fig. 5

Definition 3.3: The piece-wise linear curve $S_i'$ (in red)

3.2 Five Lemmas

For two intervals I and J of Z, we say that I comes before J on Z if the point $\ell (I)$ comes before r(J) on Z. Recall that D is the open unit disc.

Lemma 3.4

Let $1\le i\ne j\le 3$. Let X be a component of $C_i'$ and $I=X\cap Z$. Let Y be a component of $C_j'$ and $J=Y\cap Z$. Suppose that $F\subset D$ such that $F\cap R^1=\emptyset$, $F\cap X\ne \emptyset$ and $F\cap Y \ne \emptyset$. If I comes before J on Z, then $F\cap S_i^\ell (I)\ne \emptyset$ and $F\cap S_j^r(J) \ne \emptyset$ (see Fig. 6).

Proof

We will show that $F\cap S_i^\ell (I)\ne \emptyset$. The fact that $F\cap S_j^r(J) \ne \emptyset$ will follow similarly.

Let $p\in C_i\cap C_j$. Let $a\in F\cap X$ and $b\in F\cap Y$. Note that the segment [a, p] lies in $C_i$ and hence the point of intersection, $i_a$, of [a, p] with Z does not come after $\ell (I)$ on Z. Similarly, the point of intersection, $i_b$, of [b, p] with Z does not come before $\ell (J)$ on Z. Since $[a,b]\subset F\subset D\setminus R^1$, the triangle with the vertices a, b, and p (a, b, and p cannot lie on a line because $C_i\cap C_j\subset R^1$) contains the interval $[i_a,i_b]$ on Z. Since $S^\ell _i(I)$ passes through $\ell (I)$, either $S^\ell _i(I_i)$ intersects the interior of the triangle or it contains the segment [a, p]. If $S^\ell _i(I)$ intersects the interior of the triangle, then it cannot intersect [a, p] since $S^\ell _i(I)$ is a supporting line for $C_i$. Therefore, $S^\ell _i(I)$ must intersect [a, b] which is contained in F. If $S^\ell _i(I)$ contains the segment [a, p], then $S^\ell _i(I)$ contains a, which is in F. This concludes the proof. $\square$

Fig. 6

Lemma 3.4

Similar arguments can be applied to prove the following lemma.

Lemma 3.5

Let $1\le i\ne j\le 3$. Assume that $C_i'$ has two components $X_1=C_i'\cap \overline{R^4}$ and $X_2=C_i'\cap \overline{R^2}$. Let Y be a component of $C_j'$ and $J=Y\cap Z$. Suppose $F \subset D$ is a convex set such that $F\cap R^1=\emptyset$ and $F\cap Y\ne \emptyset$. If $F\cap X_1\ne \emptyset$ and J comes after $I_i^1$ on Z, or if $F\cap X_2\ne \emptyset$ and $I_i^2$ comes after J on Z, then $F\cap S_i'\ne \emptyset$ (see Fig. 7).

Proof

Assume that F intersects $X_1$ and J comes after $I_i^1$ on Z. By Lemma 3.4, F intersects $S_i^\ell (I_i^1)$. However, if F intersects $S_i^\ell (I_i^1)\cap \overline{R^2}$, then by convexity, F intersects $R^1$, a contradiction. Therefore, F intersects $S_i^\ell (I_i^1)\cap \overline{R^4}\subset S_i'$. Similarly, if F intersects $X_2$ and $I_i^2$ comes after J on Z, then F intersects $S_i^r(I_i^2)\cap \overline{R^2}\subset S_i'$. $\square$

Fig. 7

Lemma 3.5

Let $C_i'$ have two components. We say that a set $F\subset D$ lies above $S_i^\ell (I^1_i)$ in $\overline{R^2}$ if F is contained in the open halfspace defined by $S_i^\ell (I^1_i)$ containing $C_i$ and $F\subset \overline{R^2}$ (see Fig. 8).

Similarly, we say that a set $F\subset D$ lies above $S_i^r(I^2_i)$ in $\overline{R^4}$ if F is contained in the open halfspace defined by $S_i^r(I^2_i)$ containing $C_j$ and $F\subset \overline{R^4}$ (see Fig. 10).

Fig. 8

The set F (in green) lies above $S_i^\ell (I_i^1)$ (in red) in $\overline{R^2}$

Fig. 9

Lemma 3.6. The relevant lines for the first and second statement in Lemma 3.6 (in red and blue respectively)

Fig. 10

The set F (in green) lies above $S_i^r(I_i^2)$ (in red) in $\overline{R^4}$

Lemma 3.6

Assume that for $1\le i\ne j\le 3$, $C_i'$ and $C_j'$ both have two components: $X_1=C_i'\cap \overline{R^4}$, $X_2=C_i'\cap \overline{R^2}$, $Y_1=C_j'\cap \overline{R^4}$, and $Y_2=C_j'\cap \overline{R^2}$. Assume that $I_i^1$ comes before $I_j^1$ on Z and $I_i^2$ comes before $I_j^2$ on Z. Then one of the following statements hold (see Fig. 9):

• For every two distinct sets $F_1,F_2\in \mathscr {C}_1$, if $F_1\cap F_2$ intersects $C_i'$ and $C_j'$ or $F_1\cap F_2$ intersects $Y_2$, then $(F_1\cap F_2) \cap S_i^\ell (I_i^1) \ne \emptyset$.

• For every two distinct sets $F_1,F_2\in \mathscr {C}_1$, if $F_1\cap F_2$ intersects $C_i'$ and $C_j'$ or $F_1\cap F_2$ intersects $X_1$, then $(F_1\cap F_2) \cap S_j^r(I_j^2)\ne \emptyset$.

Proof

First note that $X_1$ lies above $S_j^r(I_j^2)$ in $\overline{R^4}$ and $Y_2$ lies above $S_i^\ell (I_i^1)$ in $\overline{R^2}$. For instance, if $X_1$ contains a point p in the closed halfspace defined by $S_j^r(I_j^2)$ not containing $C_j$, then the segment $[p,r(I_i^2)]$ intersects $[c,f_1]$ at a point that comes after $r(I_j^1)$ on Z, contradicting the fact that $I_i^1$ comes before $I_j^1$ on Z. A similar argument applies to the corresponding statement for $Y_2$.

We will show that either there is no pair of sets in $\mathscr {C}_1$ whose intersection intersects $Y_2$ and lies above $S_i^\ell (I_i^1)$ in $\overline{R^2}$, or there is no pair of sets in $\mathscr {C}_1$ whose intersection intersects $X_1$ and lies above $S_j^r(I_j^2)$ in $\overline{R^4}$. This will imply the lemma as shown in the last two paragraphs of this proof.

Assume for contradiction that there exist two distinct sets $F_1,F_2\in \mathscr {C}_1$ such that $F_1\cap F_2$ lies above $S_j^r(I_j^2)$ in $\overline{R^4}$ and $X_1\cap (F_1\cap F_2)\ne \emptyset$, and two distinct sets $F_3,F_4\in \mathscr {C}_1$ such that $F_3\cap F_4$ lies above $S_i^\ell (I_i^1)$ in $\overline{R^2}$ and $Y_2\cap (F_3\cap F_4)\ne \emptyset$.

Note that neither $F_3$ nor $F_4$ can be equal to $F_1$ or $F_2$. For instance, if $F_3=F_1$, then $F_1$ contains a point p above $S_j^r(I_j^2)$ in $\overline{R^4}$, and a point q in $Y_2$. Since $q\in R^2$ and lies in the same halfspace defined by $S_j^r(I_j^2)$ as p, the segment [p, q] intersects $R^1$. However, this is a contradiction to the fact that $F_1\in \mathscr {C}_1$. Therefore, the sets $F_1,F_2,F_3,F_4$ are pairwise distinct.

By the (4, 3)-property, three sets out of $F_1,F_2,F_3,F_4$ have a common point. If $F_1,F_2,F_3$ intersect, then $F_3$ intersects $Y_2$ and has a point above $S_j^r(I_j^2)$ in $\overline{R^4}$, which implies that $F_3$ has a point in $R^1$, a contradiction. Similarly, $F_1,F_2,F_4$ cannot intersect. An analogous argument show that neither $F_1,F_3,F_4$ nor $F_2,F_3,F_4$ can intersect. Therefore, there is no pair of sets in $\mathscr {C}_1$ whose intersection intersects $Y_2$ and lies above $S_i^\ell (I_i^1)$ in $\overline{R^2}$, or there is no pair of sets in $\mathscr {C}_1$ whose intersection intersects $X_1$ and lies above $S_j^r(I_j^2)$ in $\overline{R^4}$.

Assume that there is no pair of sets in $\mathscr {C}_1$ whose intersection lies above $S_i^\ell (I_i^1)$ in $\overline{R^2}$ and intersects $Y_2$, and take $L=S_i^\ell (I_i^1)$. Let F be the intersection of any pair of sets in $\mathscr {C}_1$. If F intersects $Y_2$, then by the above F does not lie above L in $\overline{R^2}$. This implies that F intersects L since $Y_2$ lies above L in $\overline{R^2}$. If F intersects $Y_1$ and $X_1$, then F intersects L by Lemma 3.4. If F intersects $Y_1$ and $X_2$, then F intersects L since $Y_1$ lies in the halfspace defined by L that does not contain $C_i$.

If there is no pair of sets in $\mathscr {C}_1$ whose intersection lies above $S_j^r(I_j^2)$ in $\overline{R^4}$ and intersects $X_1$, then a similar argument shows that the corresponding statements follow for $S_j^r(I_j^2)$. $\square$

Lemma 3.7

If $F\in \mathscr {C}_1$ and $C_i'$ has two components, then $F\cap S_i'$ is an interval.

Proof

Clearly, $F\cap (S_i'\cap \overline{R^2})$, $F\cap (S_i'\cap \overline{R^4})$ are intervals, and $F\cap S_i'=(S_i'\cap \overline{R^2})\cup (S_i'\cap \overline{R^4})$, so it suffices to show that F cannot intersect both $S_i'\cap \overline{R^2}$ and $S_i'\cap \overline{R^4}$. Suppose it does. Let T be the line passing through $\ell (I_i^1)$ and $r(I_i^2)$. By the definition of $S_i'$, both $S_i'\cap \overline{R^2}$ and $S_i'\cap \overline{R^4}$ lie on the closed halfspace defined by T containing $f_1$ and $f_2$. Since F is convex, this implies that F has a point in $R^1$, a contradiction. $\square$

Lemma 3.8

Let $F_1,F_2\in \mathscr {C}_1$, then $F_1\cap F_2$ intersects at least two of $C_1,C_2,C_3$.

Proof

Suppose $F_1\cap F_2$ does not intersect $C_1$. Since $C_1\cap C_2\subset R^1$ and $F\cap R^1=\emptyset$, by the (4, 3)-property for the sets $C_1,C_2,F_1,F_2$, we have that $C_2$ must intersect $F_1\cap F_2$. Similarly, $C_3$ intersects $F_1\cap F_2$. $\square$

3.3 Proof of Theorem 2.5

We wish to show that $\tau (\mathscr {C}_1)\le 2$. We split into four cases. In each case and subcase, we find two homeomorphic copies of the real line $T_1$ and $T_2$, and show that the family of 2-intervals $\mathscr {I}=\{(F\cap T_1)\cup (F\cap T_2)\mid F\in \mathscr {C}_1\}$ satisfies $\nu (\mathscr {I})=1$. By Theorem 1.3, this implies $\tau (\mathscr {I})\le 2$. The curves $T_1, T_2$ will be of the form $S_i^\ell (I)$ or $S_i^r(I)$ for some interval I on Z, or $S_i'$, and Lemma 3.7 ensures that $\mathscr {I}$ is indeed a family of 2-intervals. Recall that $I_i^1=C_i \cap [f_1,c]$, $I_i^2=C_i\cap [c,f_2]$, and $I_i=C_i\cap Z$.

Also, if $C_i'$ and $C_j'$ have two components, $i\ne j$, $I_i^1$ comes before $I_j^1$ on Z, and $I_i^2$ comes before $I_j^2$ on Z, then one of the two statements in Lemma 3.6 holds. If the first statement holds, the curve obtained by applying Lemma 3.6to $C_i$ and $C_j$ will be understood to be $S_i^\ell (I_i^1)$. Otherwise, the curve obtained by applying Lemma 3.6 to $C_i$ and $C_j$ will be understood to be $S_j^r(I_j^2)$.

Throughout, $F_1,F_2\in \mathscr {C}_1$ are two arbitrary, distinct sets, and $F=F_1\cap F_2$. Because of Lemma 3.8, we assume that F intersects two of the $C_i$’s throughout. Recall in order to show that $\nu (\mathscr {I})=1$, we must show that F intersects $T_1\cup T_2$ or, in other words, that F intersects $T_1$ or $T_2$.

Case 1: $C_i'$ has one component for each i (see Fig. 11). Notice in this case each $I_i$ is an interval on Z. Assume without loss of generality that $I_1$ comes before $I_2$ and $I_2$ comes before $I_3$ on Z. Set $T_1=S_1^\ell (I_1)$ and $T_2=S_2^\ell (I_2)$. By Lemma 3.4, F intersects $T_1$ or $T_2$ (recall we assume that F intersects two of the $C_i$’s). It follows that our collection of 2-intervals, $\mathscr {I}$, has matching number 1.

Fig. 11

Case 1: each $C_i'$ has one component

Case 2: One of the $C_i'$’s has two components. We can assume without loss of generality that $C_3'$ has two components, and that $I_1$ comes before $I_2$ on Z.

• Subcase 2.1. If the order of the intervals on Z is $I_1,I_2,I_3^1,I_3^2$, then set $T_1=S_1^\ell (I_1)$ and $T_2=S_2^\ell (I_2)$ (see Fig. 12). Similarly to Case 1, it follows from Lemma 3.4 that $\mathscr {I}$ has matching number 1.

• Subcase 2.2. If the order of the intervals is $I_1, I_3^1, I_2, I_3^2$, then set $T_1=S_1^\ell (I_1)$ and $T_2=S_3'$ (see Fig. 13). If F intersects $C_1$ and $C_2$, then F intersects $T_1$ by Lemma 3.4. If F intersects $C_1$ and $C_3$, then F intersects $T_1$ by Lemma 3.4. If F intersect $C_2$ and $C_3$, then F intersects $T_2$ by Lemma 3.5.

• Subcase 2.3. If the order of the intervals is $I_1, I_3^1, I_3^2, I_2$, then set $T_1=S_1^\ell (I_1)$ and $T_2=S_2^r(I_2)$ (see Fig. 14). Similarly to Case 1, it follows from Lemma 3.4 that $\mathscr {I}$ has matching number 1.

• Subcase 2.4. If the order of the intervals is $I_3^1, I_1,I_2,I_3^2$, then set $T_1=S_1^\ell (I_1)$ and $T_2=S_3'$ (see Fig. 15). If F intersects $C_1$ and $C_2$, then F intersects $T_1$ by Lemma 3.4. If F intersect $C_3$ and $C_1$ or $C_2$, then F intersects $T_2$ by Lemma 3.5. Therefore, $\mathscr {I}$ has matching number 1.

The remaining subcases of Case 2 are symmetrical. For instance, the case where the order of the intervals is $I_3^1,I_3^2,I_1,I_2$ follows similarly to the case where the order of the intervals is $I_1,I_2,I_3^1,I_3^2$.

Fig. 12

Subcase 2.1

Fig. 13

Subcase 2.2

Fig. 14

Subcase 2.3

Fig. 15

Subcase 2.4

Fig. 16

Subcase 3.1

Fig. 17

Subcase 3.2. Here, the curve in blue is one of the two possibilities for $T_2$

Fig. 18

Subcase 3.3

Case 3: Two of the $C_i'$’s have two components. Without loss of generality, assume $C_2'$ and $C_3'$ have two components.

• Subcase 3.1. Assume the order of the intervals is $I_1,I_2^1,I_3^1, I_3^2, I_2^2$, then set $T_1=S_1^\ell (I_1)$ and $T_2=S_2'$ (see Fig. 16). If F intersects $C_1$ and one of $C_2$ or $C_3$, then F intersects $T_1$ by Lemma 3.4. If F intersects $C_2$ and $C_3$, then F intersects $T_2$ by Lemma 3.5. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 3.2. If the order of the intervals is $I_1,I_2^1,I_3^1, I_2^2, I_3^2$, then set $T_1=S_1^\ell (I_1)$ and $T_2$ to be the line obtained by applying Lemma 3.6 to $C_2$ and $C_3$ (see Fig. 17). If F intersects $C_1$ and one of $C_2$ or $C_3$, then F intersects $T_1$ by Lemma 3.4. If F intersects $C_2$ and $C_3$, then F intersects $T_2$ by Lemma 3.6. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 3.3. If the order of the intervals is $I_2^1,I_1,I_3^1, I_3^2, I_2^2$, then set $T_1=S_1^\ell (I_1)$ and $T_2=S_2'$ (see Fig. 18). If F intersects $C_1$ and $C_3$, then F intersects $T_1$ by Lemma 3.4. If F intersect $C_2$ and one of $C_1$ or $C_3$, then F intersects $T_2$ by Lemma 3.5. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 3.4. If the order of the intervals is $I_2^1,I_1,I_3^1, I_2^2, I_3^2$, then set $T_1=S_1^\ell (I_1)$ and $T_2$ to be the line obtained by applying Lemma 3.6 to $C_2$ and $C_3$ (see Fig. 19). If F intersects $C_2$ and $C_3$, then F intersects $T_2$ by Lemma 3.6. If F intersects $C_1$ and $C_3$ or $C_1$ and $C_2'\cap \overline{R^2}$, then F intersects $T_1$ by Lemma 3.4. If $T_2=S_2^\ell (I_2^1)$ and F intersects $C_1$ and $C_2'\cap \overline{R^4}$, then F intersects $T_2$ by Lemma 3.4. If $T_2=S_3^r(I_3^2)$ and F intersects $C_1$ and $C_2'\cap \overline{R^4}$, then F intersects $T_2$ by Lemma 3.6. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 3.5. If the order of the intervals is $I_2^1,I_3^1,I_1, I_3^2, I_2^2$, then set $T_1=S_2'$ and $T_2=S_3'$ (see Fig. 20). If F intersects $C_2$ and one of $C_1$ or $C_3$, then F intersects $T_1$ by Lemma 3.5. If F intersects $C_1$ and $C_3$, then F intersects $T_2$ by Lemma 3.5. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 3.6. If the order of the intervals is $I_2^1,I_3^1,I_1, I_2^2, I_3^2$, then set $T_1=S_2'$ and $T_2=S_3'$ (see Fig. 21). If F intersects $C_1$ and one of $C_2$ or $C_3$, then F intersects $T_1$ or $T_2$, respectively, by Lemma 3.5. If F intersects $C_2'\cap \overline{R^2}$ and $C_3$, then F intersects $T_2$ by Lemma 3.5. If F intersects $C_2$ and $C_3'\cap \overline{R^4}$, then F intersects $T_1$ by Lemma 3.5. Finally, F cannot intersect $C_2'\cap \overline{R^4}$ and $C_3'\cap \overline{R^2}$, otherwise, since $C_3'\cap \overline{R^2}$ lies above $S_2^\ell (I_2^1)$ in $\overline{R^2}$ (this fact was mentioned in the proof of Lemma 3.5), F has a point in $R^1$ by convexity. Therefore, $\mathscr {I}$ has matching number 1.

The remaining subcases are symmetrical to one of the above cases.

Fig. 19

Subcase 3.4. Here, the blue curve is one of two possibilities for $T_2$

Fig. 20

Subcase 3.5

Fig. 21

Subcase 3.6

Fig. 22

Subcase 4.1

Fig. 23

Subcase 4.2

Fig. 24

Subcase 4.3. Here, the blue curve is one of two possibilities for $T_2$

Fig. 25

Subcase 4.4. Here, the blue curve is one of two possibilities for $T_2$

Fig. 26

Subcase 4.5. The curve in blue is one of two possibilities for $T_2$

Case 4: Each $C_i'$ has two components.

• Subcase 4.1. If the order of the intervals is $I_1^1,I_2^1,I_3^1,I_3^2,I_2^2,I_1^2$, then set $T_1=S_1'$ and $T_2=S_2'$ (see Fig. 22). If F intersects $C_1$ and one of $C_2$ or $C_3$, then F intersects $T_1$ by Lemma 3.5. If F intersects $C_2$ and $C_3$, then F intersects $T_2$ by Lemma 3.5. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 4.2. If the order of the intervals is $I_1^1,I_2^1,I_3^1,I_3^2,I_1^2,I_2^2$, then set $T_1=S_1'$ and $T_2=S_2'$ (see Fig. 23). Similarly to Subcase 3.6 (where $C_1,C_2,C_3$ here are analogous to $C_2,C_3,C_1$ from Subcase 3.6, respectively), it follows from Lemma 3.5 that $\mathscr {I}$ has matching number 1.

• Subcase 4.3. If the order of the intervals is $I_1^1,I_2^1,I_3^1,I_1^2,I_2^2,I_3^2$, then set $T_1=S_2'$ and $T_2$ to be the line obtained by applying Lemma 3.6 to $C_1$ and $C_3$ (see Fig. 24). If F intersects $C_1$ and $C_3$, then F intersects $T_2$ by Lemma 3.6. If F intersects $C_2$ and one of $C_1'\cap \overline{R^2}$ or $C_3'\cap \overline{R^4}$, then F intersects $T_1$ by Lemma 3.5. If $T_2=S_1^\ell (I_1^1)$ and F intersects $C_3'\cap \overline{R^2}$, then F intersects $T_2$ by Lemma 3.6. If F intersects $C_2'\cap \overline{R^4}$ and $C_1'\cap \overline{R^4}$, then F intersects $T_2$ by Lemma 3.4. If $T_2=S_3^r(I_3^2)$ and F intersects $C_1'\cap \overline{R^2}$, then F intersects $T_2$ by Lemma 3.6. If F intersects $C_2'\cap \overline{R^2}$ and $C_3'\cap \overline{R^2}$, then F intersects $T_2$ by Lemma 3.4. Similary to the reasoning in Subcase 3.6, F does not intersect $C_2'\cap \overline{R^2}$ and $C_1'\cap \overline{R^4}$, and F does not intersect $C_2'\cap \overline{R^4}$ and $C_3'\cap \overline{R^2}$. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 4.4. If the order of the intervals is $I_1^1,I_2^1,I_3^1,I_2^2,I_3^2,I_1^2$, then set $T_1=S_1'$ and $T_2$ to be the line obtained by applying Lemma 3.6 to $C_2$ and $C_3$ (see Fig. 25). If F intersects $C_1$ and one of $C_2$ or $C_3$, then F intersects $T_1$ by Lemma 3.5. If F intersects $C_2$ and $C_3$, then F intersects $T_2$ by Lemma 3.6. Therefore, $\mathscr {I}$ has matching number 1.

• Subcase 4.5. If the order of the intervals is $I_1^1,I_2^1,I_3^1,I_2^2,I_1^2,I_3^2$, then set $T_1=S_1'$ and $T_2$ to be the line obtained by applying Lemma 3.6 to $C_2$ and $C_3$ (see Fig. 26). If F intersects $C_1$ and $C_2$, then F intersects $T_1$ by Lemma 3.5. If F intersects $C_2$ and $C_3$, then F intersects $T_2$ by Lemma 3.6. If F intersects $C_1$ and $C_3'\cap \overline{R^4}$, then F intersects $T_1$ by Lemma 3.5. If $T_2=S_2^\ell (I_2^1)$, then if F intersects $C_3'\cap \overline{R^2}$, F intersects $T_2$ by Lemma 3.6. If $T_2=S_3^r(I_3^2)$, then if F intersects $C_1'\cap \overline{R^2}$ and $C_3'\cap \overline{R^2}$, F intersects $T_2$ by Lemma 3.4. Similarly to the reasoning in Subcase 3.6, F cannot intersect $C_3'\cap \overline{R^2}$ and $C_1'\cap \overline{R^4}$. Therefore, $\mathscr {I}$ has matching number 1.

Again, the remaining possible subcases are symmetrical to one of the above subcases.