Helly-type problems

Abstract

In this paper we present a variety of problems in the interface between combinatorics and geometry around the theorems of Helly, Radon, Carathéodory, and Tverberg. Through these problems we describe the fascinating area of Helly-type theorems and explain some of their main themes and goals.

1. Helly, Carathéodory, and Radon theorems

In this paper, we present a variety of problems in the interface between combinatorics and geometry around the theorems of Helly, Radon, Carathéodory, and Tverberg.

Helly’s theorem Hel23 asserts that for a family $\{K_1,K_2,\ldots , K_n\}$ of convex sets in $\mathbb{R}^d$, where $n \ge d+1$, if every $d+1$ of the sets have a point in common, then all of the sets have a point in common. The closely related Carathéodory theorem Car07 states that for $S \subset \mathbb{R}^d$, if $x \in \operatorname {conv} S$, then $x \in \operatorname {conv} R$ for some $R \subset S$, $|R| \le d+1$.

The more general colorful Carathéodory theorem Bár82 says the following. Let $S_1$, $S_2$, …, $S_{d+1}$ be $d+1$ sets (or colors if you wish) in $\mathbb{R}^d$. Suppose that $x \in \bigcap _{i=1}^{d+1}\operatorname {conv} S_i$. Then there is a transversal $T=\{x_1,\ldots ,x_{d+1}\}$ of the system $S_1$, …, $S_{d+1}$, meaning that $x_1 \in S_1$, $x_2 \in S_2$, …, $x_{d+1} \in S_{d+1}$ such that $x \in \operatorname {conv} T$. A transversal is also called a rainbow set when $S_1$, …, $S_{d+1}$ are considered as colors. The uncolored version, that is, when $S_1=S_2=\cdots =S_{d+1}$, is the classic result of Carathéodory. There is a closely related colorful version of Helly’s theorem due to Lovász that appeared in Bár82.

Tverberg’s theorem Tve66 states the following. Let $x_1$, $x_2$, …, $x_m$ be points in $\mathbb{R} ^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1$, $S_2$, …, $S_r$ of $\{1,2,\ldots ,m\}$ such that $\bigcap _{j=1}^r\operatorname {conv} \{x_i: i \in S_j\} \ne \emptyset$. This was a conjecture by Birch, who also proved the planar case in a slightly different form. The bound of $(r-1)(d+1)+1$ in the theorem is sharp as can easily be seen from the configuration of points in a sufficiently general position.

The case $r=2$ is Radon’s theorem Rad21, another classic from 1921, which was used by Radon to prove Helly’s theorem. Helly’s original proof (published later) was based on a separation argument. Sarkaria Sar92 gave a simple proof of Tverberg’s theorem based on the colorful Carathéodory theorem.

This paper describes the fascinating area of Helly-type theorems and explains some of their main themes and goals through a large and colorful bouquet of problems and conjectures. Some of these problems are very precise and clear-cut; see, for instance, Sierksma’s conjecture (Conjecture 4.1), the cascade conjecture (Conjecture 5.1), and Problem 3.2 about volumes of intersections. Some of them are rather vague; see, for instance, Problem 2.1 about intersection patterns of Euclidean convex sets, Problem 3.9 about the mutual position of convex sets, and Problem 5.5 about topological conditions for the existence of Tverberg partitions. We hope to see the answers to many of the questions presented here in the near future. Often, results from convexity give a simple and strong manifestation of theorems from topology: Helly’s theorem manifests the nerve theorem from algebraic topology, and Radon’s theorem can be regarded as an early linear version of the Borsuk–Ulam theorem. One of our main themes is to further explore these connections to topology. Helly-type theorems also offer complex and profound combinatorial connections and applications that represent a second theme of this paper.

For a wider perspective and many other problems we refer the reader to survey papers by Danzer, Grünbaum, and Klee DGK63; Eckhoff Eck79 and Eck93; Tancer Tan13; De Loera, Goaoc, Meunier, and Mustafa DLGMM19; and the forthcoming book of Bárány Bár.

Here is a quick summary of the paper. Section 2 defines the nerve that records the intersection pattern of convex sets in $\mathbb{R}^d$, describes some of its combinatorial and topological properties, and considers various extensions of Helly’s theorem, such as the fractional Helly theorem, which asserts that if a fraction $\alpha$ of all sets in a family of convex sets have a nonempty intersection, then there is a point that belongs to a fraction $\beta (\alpha ,d)$ of the sets in the family. Section 3 considers various refinements and generalizations of Helly theorems, such as the study of dimensions of intersections of convex sets and the study of Helly-type theorems for unions of convex sets. Section 4 presents various extensions and refinements of Tverberg’s theorem, starting with Sierksma’s conjecture on the number of Tverberg partitions. Section 5 studies the cascade conjecture about the dimensions of the Tverberg points and considers several connections with graph theory including a speculative connection with the four-color theorem. Section 6 deals with other Tverberg-type problems. Section 7 brings problems related to the Carathéodory theorem and weak-epsilon nets, and Section 8 gives a glance at common transversals; rather than piercing a family of sets by a single point or a few points, we want to stab them with a single or a few $j$-dimensional affine spaces. Final conclusions are drawn in the last section.

2. Around Helly’s theorem

2.1. Nerves, representability, and collapsibility

We start this section with the following basic definition: for a finite collection of sets $\mathcal{F} = \{K_1,K_2,\dots ,K_n\}$, the nerve of $\mathcal{F}$ is a simplicial complex defined by

$$\begin{equation*} {\mathcal{N}}({\mathcal{F}}) =\{S \subset [n]: \bigcap _{i \in S}K_i \ne \emptyset \}. \end{equation*}$$

Helly’s theorem can be seen as a statement about nerves of convex sets in $\mathbb{R}^d$, and nerves come in to play in many extensions and refinements of Helly’s theorem.

A missing face $S$ of a simplicial complex $\mathcal{K}$ is a set of vertices of $\mathcal{K}$ that is not a face, but every proper subset of $S$ is a face. Helly’s theorem asserts that a $d$-representable complex does not have a missing face with more than $d+1$ vertices.

A simplicial complex is $d$-representable if it is the nerve of a family of convex sets in $\mathbb{R}^d$.

Problem 2.1.

Explore $d$-representable simplicial complexes.

We refer the reader to the survey on $d$-representable complexes by Tancer Tan13.

Let $\mathcal{K}$ be a simplicial complex. A face $F \in \mathcal{K}$ is free if it is contained in a unique maximal face. An elementary $d$-collapse step is the removal from $\mathcal{K}$ of a free face $F$ with at most $d$ vertices and all faces containing $F$. A simplicial complex is $d$-collapsible if it can be reduced to the empty complex by a sequence of elementary $d$-collapse steps. Wegner proved Weg75 that every $d$-representable complex is $d$-collapsible. The converse does not hold even for $d=1$: 1-representable complexes are the clique complex of interval graphs, and 1-collapsible complexes are the clique complexes of chordal graphs.

Here, a clique complex of a graph $G$ is a simplicial complex whose faces correspond to the sets of vertices of complete subgraphs of $G$. Chordal graphs are graphs with no induced cycles of length greater than $3$. Intersection patterns of intervals (which are the same as 1-representable complexes) were completely characterized by Lekkerkerker and Boland LB62. They proved that interval graphs are characterized by being chordal graphs with the additional property that among every three vertices, one is a vertex or is adjacent to a vertex in any path between the other two. They also described interval graphs in terms of a list of forbidden induced subgraphs.

2.2. The upper bound theorem

For a finite collection of sets

$$\begin{equation*} {\mathcal{F}} = \{K_1,K_2,\dots ,K_n\},\ n \ge d+1,\ \text{in } \mathbb{R}^d, \end{equation*}$$

let ${\mathcal{N}}={\mathcal{N}}({\mathcal{F}})$ be the nerve of $\mathcal{F}$. We put $f_k({\mathcal{N}})=|\{S \in {\mathcal{N}}: |S|=k+1\}|$. (The vector $(f_0({\mathcal{N}}), f_1({\mathcal{N}}),\dots )$ is called the $f$-vector of ${\mathcal{N}}$, and is sometimes referred to also as the $f$-vector of $\mathcal{F}$ and written as $f(\mathcal{F})$.) Helly’s theorem states that if $f_{n-1}({\mathcal{N}})=0$, then $f_d({\mathcal{N}}) < {{n} \choose {d+1}}$ or, with the $f(\mathcal{F})$ notation, $f_{n-1}(\mathcal{F})=0$ implies $f_d(\mathcal{F}) < {{n} \choose {d+1}}$

A far-reaching extension of Helly’s theorem was conjectured by Katchalski and Perles and proved by Kalai Kal84b and Eckhoff Eck85.

Theorem 2.1 (Upper bound theorem).

Let $\mathcal{F}$ be a family of $n$ convex sets in $\mathbb{R}^d$, and suppose that every $d+r+1$ members of $\mathcal{F}$ have an empty intersection. Then, for $k=d$, …, $d+r-1$,

$$\begin{equation*} f_k({\mathcal{N}}(\mathcal{F})) \leq \sum _{j=k}^{d+r-1}\binom{j-d}{k-d}\binom{n-j+d-1}{d}. \end{equation*}$$

The theorem provides best upper bounds for $f_d(\mathcal{F}),\ldots ,f_{d+r-1}(\mathcal{F})$ in terms of $f_0(\mathcal{F})$ provided $f_{d+r}(\mathcal{F})=0$. The proofs rely on $d$-collapsibility. There is a simple case of equality: the family consists of $r$ copies of $\mathbb{R}^d$ and $n-r$ hyperplanes in general position. Theorem 2.1 is closely related to the upper bound theorem for convex polytopes of Peter McMullen McM70. In fact, a common proof was given by Alon and Kalai in AK95.

Problem 2.2.

Study cases of equality for the upper bound theorem.

A place to start would be to understand $2$-representable complexes $\mathcal{K}$ with $f_3(\mathcal{K})=0$ and $f_2(\mathcal{K})={{n-1} \choose {2}}$.

Theorem 2.1 implies the sharp version of the fractional Helly theorem of Katchalski and Liu KL79. The sharp version is due to Kalai Kal84b.

Theorem 2.2.

Let $\mathcal{K}$ be a $d$-representable complex. If $f_d(\mathcal{K}) \ge \alpha {{n \choose {d+1}}}$, then $\dim (\mathcal{K}) \ge \beta n$, where $\beta = \beta (d,\alpha )=1- (1-\alpha )^{1/d+1}$.

In other words, if $\mathcal{F}=\{K_1,\ldots ,K_n\}$ is a family of convex sets in $\mathbb{R}^d$ ($n\ge d+1$) and at least $\alpha {n \choose d+1}$ of the $d+1$ tuples in $\mathcal{F}$ intersect, then $\mathcal{F}$ contains an intersecting subfamily of size $\beta n$. This is a result of central importance around Helly’s theorem. The existence of $\beta (\alpha )$ is referred to as the fractional Helly property, and if $\beta \to 1$ when $\alpha \to 1$ this is referred to as the strong fractional Helly property.

We note that a complete characterization of $f$-vectors of $d$-representable complexes was conjectured by Eckhoff and proved by Kalai Kal84aKal86.

2.3. Helly numbers and Helly orders

It is useful to consider the following abstract notions of Helly numbers and Helly orders. Let ${\mathcal{F}}$ be a family of sets. The Helly number $\nobreakspace {\mathrm{h}} ({\mathcal{F}})$ of ${\mathcal{F}}$ is the minimal positive integer $h$ such that if a finite subfamily ${\mathcal{K}} \subset {\mathcal{F}}$ satisfies $\bigcap {\mathcal{K}}' \neq \emptyset$ for all ${\mathcal{K}}' \subset {\mathcal{K}}$ of cardinality $\leq h$, then $\bigcap {\mathcal{K}} \neq \emptyset$. The Helly order $\nobreakspace {\mathrm{h_o}} ({\mathcal{F}})$ of ${\mathcal{F}}$ is the minimal positive integer $h$ such that if a finite subfamily ${\mathcal{K}} \subset {\mathcal{F}}$ satisfies

(1)

every finite intersection of sets in ${\mathcal{K}}$ belongs to ${\mathcal{F}}$, and

(2)

$\bigcap {\mathcal{K}}' \neq \emptyset$ for all ${\mathcal{K}}' \subset {\mathcal{K}}$ of cardinality $\leq h$,

then $\bigcap {\mathcal{K}} \neq \emptyset$. Of course, when we consider families of sets closed under intersection, the Helly number and the Helly order coincide. So, for example, the topological Helly theorem (discussed in Section 2.4) asserts that the Helly order of topologically trivial sets in $\mathbb{R}^d$ is $d+1$, and Amenta’s theorem (see Section 3.3) asserts that the family of unions of $k$ pairwise disjoint convex sets in $\mathbb{R}^d$ has the Helly order $k(d+1)$.

Let ${\mathcal{F}}$ be a family of sets. The fractional Helly number $\nobreakspace {\mathrm{g}} ({\mathcal{F}})$ of ${\mathcal{F}}$ is the minimal positive integer $g$ such that there is a function $f(\alpha )>0$, defined for $\alpha >0$, with the following property: for every family ${\mathcal{K}} \subset {\mathcal{F}}$ of cardinality $n$, if at least $\alpha {n \choose g}$ of the $g$-tuples in $\mathcal{F}$ intersect, then $\mathcal{F}$ contains an intersecting subfamily of size $f(\alpha ) n$.

2.4. Topological Helly theorem and Leray complexes

Helly himself proved a topological version of his theorem Hel30. A good cover is a family of compact subsets of $\mathbb{R}^d$ such that every intersection of sets in the family is either empty or topologically trivial. (By topologically trivial we mean contractible, but it is sufficient to assume that all homology groups vanish.)

Theorem 2.3 (Topological Helly).

If in a good cover of $n$ subsets of $\mathbb{R}^d$, $n \ge d+1$, every intersection of $d+1$ sets is nonempty, then the intersection of all the sets in the family is nonempty.

A simplicial complex $\mathcal{K}$ is $d$-Leray if $H_i(\mathcal{K}')=0$ for every induced subcomplex $\mathcal{K}'$ of $\mathcal{K}$ and for every $i \ge d$. The well-known nerve theorem from algebraic topology asserts that if $\mathcal{K}$ is a finite family of sets that form a good cover, then the nerve of $K$ is topologically equivalent to $\bigcup {\mathcal{K}}$. (The notion of topologically equivalent corresponds to the notion of topologically trivial in the definition of good covers.) It follows from the homological version of the nerve theorem that $d$-representable complexes are $d$-Leray. It is also easy to see that $d$-collapsible complexes are $d$-Leray.

Remark.

The nerve theorem played an important role in algebraic topology in the 1940s and 1950s, e.g., in showing that de Rham homology coincides with other notions of homology. Helly’s topological theorem is remarkable since it came earlier than these developments. In Section 4.2 we will mention that Radon’s theorem can be seen as an early incarnation of the Borsuk–Ulam theorem in topology. Topological extensions of Helly-type theorems are an important part of the theory. Often, such extensions are considerably more difficult to prove, but in a few cases the topological proofs are the only known ones even for the geometric results. There are also a few cases where natural topological extensions turned out to be incorrect. The survey paper DLGMM19 of De Loera, Goaoc, Meunier, and Mustafa emphasizes connections with combinatorial theorems closely related to the Brouwer fixed-point theorem, starting with the Sperner lemma and the Knaster–Kuratowski–Mazurkiewicz theorem.

A general problem is the following.

Problem 2.3.

(i)

Find finer and finer topological and combinatorial properties of $d$-representable complexes.

(ii)

Extend Helly-type theorems to good covers, Leray complexes, and beyond.

(iii)

Find weaker topological conditions that suffice for the topological Helly theorem to hold.

There is much to say about part (ii) of Problem 2.3. In several cases the way to go about it is to extend properties of $d$-representable complexes to $d$-Leray complexes. We will come back to such extensions later, but we note that the upper bound theorem (Theorem 2.1) as well as the full characterization of their $f$-vectors, extends to $d$-Leray complexes; see Kal02. This is also closely related to Stanley’s characterization Sta75 of $f$-vectors of Cohen–Macaulay complexes.

Regarding part (i) of Problem 2.3, we first note a very easy connection with embeddability: If $G$ is a graph we denote by $TG$ the graph where for every edge $e$, we add a new vertex $v_e$ that is adjacent to the endpoints of $e$, and remove $e$ itself; see Figure 1. If $G$ is not planar, e.g., when $G=T_5$, then $TG$ is not 2-representable. (Note however that $K_n$ itself is 2-representable for every $n$.)

White Whi21 defined the class of $d$-Matoušek simplicial complexes that are related to topological invariants for embeddability as follows. Let $\mathcal{K}$ be an abstract simplicial complex with vertices $V(\mathcal{K})=[n]=\{1,2,\ldots ,n\}$. We define the dual simplicial complex $K'$, with vertices $V(\mathcal{K}')=\{J\in \mathcal{K}\ :\ J\text{ is inclusion maximal}\}$ and faces $\mathcal{K}'=\{\alpha \subseteq V(\mathcal{K}')\ :\ \bigcap _{J\in \alpha }J\neq \emptyset \}$.

We say that $\mathcal{K}$ is $d$-Matoušek, if the $\mathbb{Z}_2$-index of the space

$$\begin{equation*} \hat{\mathcal{K}}=\{(x,y)\in \, |\! | \, \mathcal{K}'\, |\! | \, ^2\ :\ \left(\bigcap \text{supp}(x)\right)\cap \left(\bigcap \text{supp}(y)\right)\notin \mathcal{K}\} \end{equation*}$$

is less than $d$. Here $\text{supp}(x)$ denotes the support of $x$ in $\mathcal{K}'$, which is the inclusion-minimal face of $\mathcal{K}'$ containing $x$.

It is straightforward to verify that $\mathcal{K}$ is $d$-representable iff there exists a linear map $f:\mathcal{K}'\to \mathbb{R}^d$, such that for every set $I\subseteq V(\mathcal{K})$ not in $\mathcal{K}$, we have $\bigcap _{i\in I}f(\alpha _i)=\emptyset$, where $\alpha _i=\{J\in V(\mathcal{K}')\ :\ i\in J\}$. This implies the existence of a $\mathbb{Z}_2$-map from $\hat{\mathcal{K}}$ to $S^{d-1}$; thus any $d$-representable complex is also $d$-Matoušek. White proved that nerves of good covers in $\mathbb{R}^d$ are $d$-Matoušek, and he also showed that being $1$-Matoušek is equivalent to being $1$-representable.

Regarding part (iii), Debrunner Deb70 showed that for the statement of the topological Helly property it suffices to assume that the (reduced) homology of intersections of $k$ sets in the family $1 \le k \le d+1$ vanishes at and below dimension $d-k$. Even more general conditions were found by Montejano Mon14.

2.5. Conditions for the fractional Helly property

Problem 2.4.

(i)

Find geometric, topological, and combinatorial conditions that imply the fractional Helly property.

(ii)

Find geometric, topological, and combinatorial conditions that imply the strong fractional Helly property.

We will mention here two conjectures regarding the fractional Helly property and two related theorems. A class of simplicial complexes is hereditary if it is closed under induced subcomplexes. Recall that for a simplicial complex $\mathcal{K}$, $f_i(\mathcal{K})$ is the number of $i$-faces of $\mathcal{K}$ and $b(\mathcal{K})$ is the sum of (reduced) Betti numbers of $\mathcal{K}$. In connection with the fractional Helly theorem, Kalai and Meshulam Kal10 formulated the following conjecture.

Conjecture 2.5 (Kalai and Meshulam).

Let $C>0$ be a positive number. Let $\mathcal{F}$ be the hereditary family of simplicial complexes defined by the property that for every simplicial complex $\mathcal{K} \in {\mathcal{F}}$ with n vertices,

$$\begin{equation*} b(\mathcal{K}) \le C n^d. \end{equation*}$$

Then for every $\alpha >0$ there is $\beta = \beta (d,C) >0$ such that $\mathcal{K} \in {\mathcal{F}}$ and $f_d(\mathcal{K}) \ge \alpha {{n \choose {d+1}}}$ imply $\dim (\mathcal{K}) \ge \beta n$.

The conclusion of the conjecture is referred to as the fractional Helly property of degree $d$. Kalai and Meshulam further conjectured that the conclusion holds even if one replaces $b(\mathcal{K})$ with $|\chi (\mathcal{K})|$, where $\chi (\mathcal{K})$ is the Euler characteristic of $\mathcal{K}$. When $d=0$, this conjecture is about graphs and it was proved (in its strong version) in CSSS20; see also SS20.

Conjecture 2.6 (Kalai and Meshulam).

Let $\mathcal{U}$ be a family of sets in $\mathbb{R} ^d$. Suppose that for every intersection $L$ of $m$ members of $\mathcal{U}$, $b(L) \le \gamma m^{d+1}$. Then $\mathcal{U}$ satisfies the fractional Helly property of order $d$.

In some special cases the fractional Helly property has been established. For instance, Matoušek Mat04 showed that families of sets with a bounded VC dimension in $\mathbb{R}^d$ satisfy the fractional Helly property of order $d$. Another case includes the so-called convex lattice sets. These are sets of the form $\mathbb{Z}^d \cap C$ where $\mathbb{Z}^d$ is the lattice of integer points in $\mathbb{R}^d$ and $C$ is a convex set in $\mathbb{R}^d$. A result of Bárány and Matoušek BM03 asserts that families of convex lattice sets in $\mathbb{R}^d$ satisfy the fractional Helly property of order $d+1$. In both of these theorems the fractional Helly number is considerably smaller than the Helly number. For example, let $\mathcal{F}$ be the family of all convex lattice sets in $\mathbb{R}^d$. The Helly number of $\mathcal{F}$, ${\mathrm{h}}(\mathcal{F})$, is equal to $2^d$, as shown by Doignon Doi73, while the fractional Helly number is $d+1$; see BM03.

Problem 2.7.

Does the assertion of the Radon theorem imply the fractional Helly property?

An affirmative solution to one interpretation of this question was recently given by Holmsen and Lee HL21, who showed that for abstract convexity spaces, the finite Radon number $r$ implies that the fractional Helly number is bounded by some function $m(r)$ of $r$.

Problem 2.8.

Estimate $m(r)$.

Convex sets are sets of solutions of systems of linear inequalities, and we can consider systems of polynomial inequalities of higher degrees.

Conjecture 2.9.

The family ${\mathcal{B}}^d_k$ of sets of solutions in $\mathbb{R}^d$ of polynomial inequalities of degree $\le k$ has the fractional Helly property.

It is known Mot55 (and is an easy consequence of Helly’s theorem itself) that the class ${\mathcal{A}}^d_k$ of sets in $\mathbb{R}^d$ of common zeroes of systems of polynomial inequalities of degree $\le k$ has the Helly number ${{d+k} \choose {k}}$. And we can even ask if this formula gives the precise fractional Helly number for the class ${\mathcal{B}}^d_k$.

We conclude this section by mentioning an interesting recent abstract notion of convexity described by Moran and Yehudayoff MY20, which seems relevant to various problems raised in this paper and, in particular, to Problem 2.7. In this notion of abstract convexity, which we call MY-convexity, we assume that every convex set is the intersection of half-spaces. We assume further that the VC dimension of the class of half-spaces is at most $D$. The class ${\mathcal{B}}_k^d$ is an example of an MY-convexity space where the half-spaces are the sets of solutions of a single polynomial inequality of degree $k$.

Problem 2.10.

Consider an MY-convexity space $X$ where the VC dimension of the class of half-spaces is at most $D$.

(i)

Does $X$ have the fractional Helly number $f(D)$ for some function $f$ of $D$?

(ii)

Does $X$ have the fractional Helly number $D$?

2.6. The $(p,q)$-property

The conclusion of Helly’s theorem is that the family is intersecting; i.e., there is a point $\mathbb{R}^d$ that is included in all sets in the family.

Problem 2.11.

What conditions guarantee that the family is $t$-pierceable, meaning that there are $t$ points such that every set in the family contains at least one?

In the language of nerves, what conditions guarantee that the set of vertices of the nerve can be expressed as the union of $t$ faces?

A family of sets has the $(p,q)$-property if for every $p$ members of the family some $q$ have a nonempty intersection. Note that here we assume $p\ge q > d$. (For nerves this says that every set of $p$ vertices spans a face with $q$ vertices, and this is closely related to Turán’s problem for hypergraphs.)

Hadwiger and Debrunner HD57 introduced the $(p,q)$-property and proved

Theorem 2.4.

If a finite family of convex sets in $\mathbb{R}^d$ has the $(p,q)$-property and $(d-1)p < (q-1)d$, then it is $p-q+1$-pierceable.

A family of sets has the $(p,q)_r$-property if in its nerve every $p$ vertices span at least $r$ faces with $q$ vertices. This was introduced by Montejano and Soberón MS11 and further studied by Keller and Smorodinsky KS18. Montejano and Soberón proved (among other results)

Theorem 2.5.

A family of convex sets in $\mathbb{R}^d$ with the $(d+2,d+1)_d$-property is $2$-pierceable.

Hadwiger and Debrunner HD57 conjectured in 1957 and Alon and Kleitman AK92bAK92a proved the following important theorem.

Theorem 2.6 ($(p,q)$-theorem).

For all $p\ge q >d$ there exists $f(d,p,q)$ such that if a family of convex sets in $\mathbb{R}^d$ has the $(p,q)$-property, then it is $f(d,p,q)$-pierceable.

The bound on $f(d,p,q)$ given in AK92b is enormous. The first open case is $d=2$ and $p=4$, $q=3$. It is known that $f(2,4,3)$ is between $3$ and $9$, the lower bound is from KGT01, and the upper bound is a recent result of McGinnis McG20 who brought down the upper bound of $13$ of KGT01 to $9$. Substantial improvements for the general case were given by Keller, Smorodinsky, and Tardos KST18 and by Keller and Smorodinsky KS20.

Problem 2.12.

Improve further the bounds on $f(2,4,3)$ and, more generally, on $f(d,p,q)$.

Alon, Kalai, Matoušek, and Meshulam AKMM02 proved the following result that implies that the Alon–Kleitman theorem extends to good covers and Leray complexes (but with worse bounds).

Theorem 2.7.

For every $q > d+1$ there exists $C(d,q)$ with the following property. Let $\mathcal{F}$ be a hereditary class of simplicial complexes satisfying the fractional Helly property of degree $d$. If a simplicial complex $\mathcal{K} \in \mathcal{F}$ has the property that every $q$ vertices span a $d$-dimensional face, then the vertices of $\mathcal{K}$ can be covered by $C(d,q)$-faces.

See Eckhoff Eck03 for a survey on $(p,q)$-theorems.

2.7. A Ramsey type question

Conjecture 2.13.

For integers $d \ge 1$ and $r > 1+\lceil d/2\rceil$, there is $\alpha =\alpha (d,r)>0$ such that the following holds. Let $\mathcal{F}$ be a family of $n$ convex sets in $\mathbb{R}^d$. Then $\mathcal{F}$ contains $n^{\alpha (d,r)}$-sets such that either every $r$ has a point in common or no $r$ has a point in common.

There is a large literature on this and related questions starting with a theorem of Larman, Matoušek, Pach, and Törőcsik LMPT94 that proves the case $d=2$ and $r=2$. Subsequent works are APP$^{+}$05 and FPT11. When $r=d+1$, this conjecture holds with $\alpha =1/(d+1)$. This was observed by Keller and Smorodinsky (private communication) and follows from their improved $(p,q)$-theorems. The general phenomenon here (with several interesting manifestations) is that graphs and hypergraphs arising in geometry satisfy much stronger forms of Ramsey’s theorem than arbitrary graphs and hypergraphs.

2.8. Colorful, fractional colorful, and matroidal Helly theorems

The colorful Helly theorem of Lovász (see Bár82) asserts the following. Assume that $\mathcal{C}_1$, …, $\mathcal{C}_{d+1}$ are finite families of convex sets in $\mathbb{R}^d$ with the property that if every transversal $K_1$, …, $K_{d+1}$ is intersecting, then $\bigcap \mathcal{C}_i \ne \emptyset$ for some $i \in [d+1]$. Here “transversal” means that $K_i \in \mathcal{C}_i$ for every $i \in [d+1]$. The colorful version implies the original one when $\mathcal{C}_1=\cdots =C_{d+1}$.

The analogous colorful version of the fractional Helly theorem says that if an $\alpha$ fraction of all transversals of the system $\mathcal{C}_1$, …, $\mathcal{C}_{d+1}$ is intersecting, then one of the families, say $\mathcal{C}_i$, contains an intersecting subfamily of size $\beta |\mathcal{C}_i|$. Here $\alpha >0$, of course, and $\beta =\beta (d,\alpha )$ has to be positive. Such a theorem (with $\beta =\alpha /(d+1)$) was proved and used first in ABB$^{+}$09. The dependence of $\beta$ was improved by Kim Kim17, who showed in particular that $\beta \to 1$ as $\alpha \to 1$. The optimal dependence of $\beta$ on $\alpha$ and $d$ is a recent result of Bulavka, Goodarzi, and Tancer BGT20. They use Kalai’s algebraic shifting technique Kal84b and raise the following interesting conjecture.

Conjecture 2.14.

Let $\mathcal{K}$ be a $d$-Leray simplicial complex whose vertex set $V$ is partitioned into sets $V_1$, …, $V_{d+1}$, called colors, and $|V_i|=n_i$ for $i \in [d+1]$. Assume that $\mathcal{K}$ contains at least $\alpha \prod _1^{d+1}n_i$ colorful $d$-faces for some $\alpha >0$. Then there is $i \in [d+1]$ such that the dimension of the restriction of $\mathcal{K}$ to $V_i$ is at least $(1-(1-\alpha )^{1/(d+1)})n_i-1$.

Kalai and Meshulam KM05 extended the assertion of the colorful Helly theorem to the topological setting and also considered a matroidal version. A matroidal complex is the complex consisting of the independent sets of a matroid. Equivalently, $M$ is a matroidal complex if and only if every induced subcomplex is pure, i.e., if all its maximal faces have the same cardinality.

Theorem 2.8.

Let $X$ be a $d$-Leray complex on the vertex set $V$. Suppose that $M$ is a matroidal complex on the same vertex set $V$ with rank function $\rho$. If $M \subset X$, then there exists $\tau \in X$ with $\rho (V \backslash \tau ) \le d$.

This theorem gives the colorful Helly property when $M$ is a transversal matroid and it suggests a general way to extend results about colorings. We will encounter this idea again in Section 4.3, where we try to move from colorful versions of Tverberg’s theorem to matroidal versions. Theorem 2.8 has interesting connections with advances in topological combinatorics related to Hall’s marriage theorem and rainbow matchings; see AB06 and AB09.

3. More around Helly’s theorem

3.1. Dimensions of intersections: Katchalski’s theorems

Let $g(d,k)$ be the smallest integer with the following property: for every family of $n$ convex sets in $\mathbb{R}^d$, $n \ge g(d,k)$, such that the dimension of intersection of every $g(d,k)$ set in the family is at least $k$, the dimension of intersection of all members of the family is at least $k$. Helly’s theorem asserts that $g(d,0)=d+1$. In 1971 Katchalski Kat71 proved the following interesting result.

Theorem 3.1.

$g(d,0)=d+1, g(d,k)=\max \{d+1, 2(d-k+1)\}$ if $1 \le k \le d$.

Given a family ${\mathcal{K}}=\{K_1,K_2,\dots , K_n\}$ of convex sets in $\mathbb{R}^d$ and $J \subset [n]$, set $K(J)=\bigcap _{j \in J}K_j$ and write $d(J)=\dim K(J)$. A further remarkable result of Katchalski Kat78 “reconstructs” the dimension of the intersection:

Theorem 3.2.

Let ${\mathcal{K}}=\{K_1,K_2,\dots , K_n\}$ and ${\mathcal{K}'}=\{K'_1,K'_2,\dots , K'_n\}$ be two families of compact convex sets in $R^d$. If $d_{\mathcal{K}}(J)=d_{\mathcal{K}'}(J)$ for every $J$, $|J| \le d+1$, then $d_{\mathcal{K}}(J)=d_{\mathcal{K}'}(J)$ for every $J$.

Katchalski actually proved a stronger statement, namely, that the condition $d_{\mathcal{K}}(J)=d_{\mathcal{K}'}(J)$ for every $J$ with $(d+1)-\lfloor d/2 \rfloor \le |J| \le d+1$ suffices for the conclusion of Theorem 3.2. More generally he proved that for every $r \ge 1$ if $d_{\mathcal{K}}(J)=d_{\mathcal{K}'}(J)$ for every $J$ with $(d+r)-\lfloor d/(r+1) \rfloor \le |J| \le d+r$, then $d_{\mathcal{K}}(J)=d_{\mathcal{K}'}(J)$ for every $J$.

Define the $D$-nerve of a finite set of convex sets as its nerve $K$ where every face $S \in K$ is labeled by the dimension of $\bigcap _{i \in S}K_i$. We can regard the $D$-nerve as a nested collection of simplicial complexes that correspond to intersections of dimension $\ge j$.

Problem 3.1.

Explore combinatorial and topological properties of $D$-nerves of families of compact convex sets in $\mathbb{R}^d$.

3.2. Helly with volume

Theorems about volumes of intersections are closely related to theorems about dimensions of intersections. The natural question is, given a finite family $\mathcal{F}$ of convex sets in $\mathbb{R}^d$, what condition guarantees that the intersection $\bigcap \mathcal{F}$ not only is nonempty but also has volume at least one, say. The first result in this direction is in BKP82 of Bárány, Katchalski, and Pach.

Theorem 3.3 (Helly with volume).

Assume that $\mathcal{F}$ is a finite family of convex sets in $\mathbb{R}^d$, $|\mathcal{F}|\ge 2d$, such that the intersection of any $2d$ sets from $\mathcal{F}$ has volume at least one. Then $\operatorname {vol} (\bigcap \mathcal{F}) \ge d^{-2d^2}$.

The example of the $2d$ half-spaces in $\mathbb{R}^d$ whose intersection is the unit cube shows that the number $2d$ is the best possible in this theorem. In other words, $2d$ is the Helly number for volumes. However, the bound $d^{-2d^2}$ is not sharp and was improved first by Naszódi Nas16 to $(cd)^{-2d}$ and later by Brazitikos Bra17 to $(cd)^{-1.5d}$. In both estimates, $c>0$ is a universal constant. The following question is still open.

Problem 3.2.

Show that under the conditions of Theorem 3.3 $\operatorname {vol} (\bigcap \mathcal{F}) \ge (cd)^{-d/2}$ where $c>0$ is a constant.

A similar result was established in BKP82 for the diameter of the intersection. The Helly number is again $2d$. So if the intersection of any $2d$ sets from the family $\mathcal{F}$ has diameter at least one, then $\operatorname {diam} \mathcal{F} \ge cd^{-d/2}$. The lower bound was improved in a series of recent papers: first by Brazitikos Bra17 to $cd^{-11/2}$, then by Ivanov and Naszódi IN21 to $(2d)^{-3}$, and more recently by Almendra-Hernández, Ambrus, and Kendall AHAK21 to $(2d)^{-2}$. This leads to the next problem.

Problem 3.3.

Assume that $\mathcal{F}$ is a finite family of convex sets in $\mathbb{R}^d$, $|\mathcal{F}|\ge 2d$, such that the intersection of any $2d$ sets from $\mathcal{F}$ has diameter at least one. Then $\operatorname {diam} \bigcap \mathcal{F} \ge \sqrt {2/d}$.

Recently, several further quantitative Helly-type results have appeared; see for instance DFN21 and DS21.

3.3. Unions of convex sets: around the Grünbaum–Motzkin conjecture

Nina Amenta Ame94 proved a Helly-type result on unions of disjoint convex sets.

Theorem 3.4.

Let $\mathcal{F}$ be a family of sets in $\mathbb{R}^d$ such that every member in ${\mathcal{F}}$ is the union of $k$ disjoint compact convex sets. Suppose further that every intersection of members of ${\mathcal{F}}$ is also a union of $k$ disjoint convex sets. If every $k(d+1)$ sets in ${\mathcal{F}}$ has a point in common, then $\bigcap {\mathcal{F}} \ne \emptyset$.

In the language of Section 2.3, Theorem 3.4 asserts that the Helly order of the family of disjoint unions of $k$ compact convex sets in $\mathbb{R}^d$ is $(d+1)k$. This was conjectured by Grünbaum and Motzkin GM61 who proved the case $k=2$, by Larman Lar68 who proved their conjecture for $k=3$, and by Amenta in its full generality. It is easy to see that this family has no finite Helly number.

Kalai and Meshulam KM08 proved that Amenta’s theorem extends topologically. They consider the following setting. Let $K$ and $L$ be simplicial complexes with a map from $V(K)$ to $V(L)$ such that the inverse image of every $i$ face in $L$ is the union of at most $k$ $i$-faces of $L$. If $K$ is $d$-Leray, then the Leray number of $L$ is at most $dk+k-1$.

Eckhoff and Nischke EN09 showed that Amenta’s theorem extends combinatorially. In the setting of the previous paragraph they proved that if $K$ has no missing face of size $d+1$ or larger, then $L$ has no missing face of size $k(d+1)$ or larger.

3.4. More on families of unions of convex sets

We may consider sets in $\mathbb{R}^d$ that can be represented as unions of $k$ convex sets but delete the disjointness assumption. In this case Alon and Kalai AK95 and Matoušek Mat97 proved the following result.

Theorem 3.5.

Assume that $\mathcal{F}$ is a finite family of sets in $\mathbb{R}^d$ such that every member in $\mathcal{F}$ is the union of $k$ compact convex sets. Then $\mathcal{F}$ has a finite Helly order.

Let us mention a recent topological Helly-type theorem by Goaoc, Paták, Patáková, Tancer, and Wagner GPP$^{+}$17 that strengthens Theorem 3.5.

Theorem 3.6.

For every $\gamma >0$ there is $h(\gamma ,d)$ with the following property. Let $\mathcal{U}$ be a family of sets in $\mathbb{R} ^d$. Suppose that for every intersection $L$ of some members of $\mathcal{U}$ and every $i \le \lceil d/2 \rceil -1$, we have $b_i(L) \le \gamma$. Then, if every $h(\gamma ,d)$ members of $\mathcal{U}$ have a point in common, then all sets in $\mathcal{U}$ have a point in common.

We note that Theorem 3.6 implies Theorem 3.5. In fact, its proof relies on the method developed by Matoušek in Mat97. His method, connecting topological obstructions for embeddability to Helly-type theorems, is the basis of White’s notion Whi21 of $d$-Matoušek complexes.

In connection with this we mention the following curious question.

Conjecture 3.4.

The Helly order of families of unions of two disjoint nonempty sets in $\mathbb{R}^d$ is $d+1$.

This is known to be false if “two” is replaced by a large integer even when $d=2$.

We say that two compact sets intersect nicely if the long Meyer–Vietoris exact sequence splits into short exact sequences dimensionwise.

Problem 3.5.

Let ${\mathcal{K}} =\{K_1,K_2,\dots , K_n\}$ be a finite family of compact sets such that for every set of indices $I\subset [n]$, ${\mathcal{K}}(I)$ is topologically equivalent to a fixed topological space $Z$, and for every two sets of indices $I,J \subset [n]$, ${\mathcal{K}}(I)$ and ${\mathcal{K}}(J)$ intersect nicely. Then $\bigcup {\mathcal{K}}$ is topologically equivalent to a fiber bundle over ${\mathcal{N}}({\mathcal{K}})$ with fibers topologically equivalent to $Z$.

A positive answer to Problem 3.5 would imply Conjecture 3.4 because a pair of disjoint unions of nonempty convex sets whose intersection is also a disjoint union of nonempty convex sets always intersects nicely.

3.5. A conjecture by Gao, Landberg, and Schulman

Here is an interesting Helly-type conjecture by Gao, Langberg, and Schulman GLS08. For a convex set $K$ in $\mathbb{R} ^d$ an $\epsilon$ enlargement of $K$ is $K+\epsilon (K-K)$ (where $K-K=\{x-y: x, y \in K\}$).

Conjecture 3.6.

For every $d$, $k$, and $\epsilon$ there is some $h=h(d,k, \epsilon )$ with the following property. Let $\mathcal{F}$ be a family of unions of $k$ convex sets. Let $\mathcal{F}^\epsilon$ be the family obtained by enlarging all the involved convex sets by $\epsilon$. If every $h$ members of $\mathcal{F}$ have a point in common, then all members of ${\mathcal{F}}^\epsilon$ have a point in common.

Of course, for $k=1$ we can take $\epsilon =0$ by Helly’s theorem.

3.6. Boxes and products

Problem 3.7.

Let $d_1$, $d_2$, …, $d_r$ be a partition of $d$. Study Helly-type theorems for families of Cartesian products $K_1 \times K_2 \times \cdots \times K_r$ of convex sets where $\dim K_i=d_i$.

The case of standard boxes, namely when $d_1=d_2=\cdots =d_{d}=1$ is of special interest. Standard boxes have Helly number 2, and therefore their nerves are determined by their graphs. Eckhoff proved an upper bound theorem for standard boxes in Eck88 and studied the extremal families in Eck91. It is easiest to describe the families where the upper bound is attained. If $f_{d+r}=0$ (that is, the largest nonempty intersection is for $d+r$ sets), then the family consists of $r$ copies of $\mathbb{R}^d$ and roughly the same number of parallel copies of each of the $d$ coordinate’s hyperplanes.

Let $\mathcal{K}$ be the nerve of a family of standard boxes in $\mathbb{R}^d$. Then $\mathcal{K}$ is a $d$-Leray complex and has the further property that if $S$ is a set of vertices such that every pair of vertices in $S$ form an edge, then $S$ is a face of $\mathcal{K}$. This property of the nerve corresponds to Helly number 2 for the original family, and we refer to it as Helly number 2.

Problem 3.8.

Extend Eckhoff’s upper bound theorem to the class of $d$-Leray complexes with no missing faces of size greater than 3 (namely, those corresponding to Helly number 2).

3.7. Mutual position of convex sets

The study of nerves of convex sets is the study of intersection patterns of families of convex sets. When we start with a family of convex sets in $\mathbb{R}^d$, we can go further and consider intersection patterns of the convex hulls of all subfamilies. (We can go even further by alternating between taking convex hulls and intersections and by considering statements regarding $k$-flat transversals rather than plain intersections.)

Figure 2 shows various possible positions of three convex sets in the plane:

(a)

the convex hull of every two sets intersects the third set;

(b)

the convex hull of any two sets is disjoint from the third set, but all pairwise convex hulls have a point in common;

(c)

the three convex hulls of pairs of sets have no point in common;

(d)

the convex hull of two sets intersects the third set.

Statements in this wider language can be regarded as the study of mutual positions of convex sets and they are, of course, of interest even for configurations of points, which we discuss in the next sections.

Problem 3.9.

Are there interesting things to say about the mutual position of convex sets?

3.8. Order types for points and sets

To conclude this section and prepare for the next, we briefly mention the notion of order types (a.k.a. oriented matroids). These objects arise from configurations of points (or of hyperplanes) in real vector spaces, and can also be associated with directed graphs. Consider a sequence $Y=(y_1,y_2,\dots ,y_n)$ of $n$ points in $\mathbb{R}^d$ that affinely span $\mathbb{R}^d$. The order type described by $Y$ can be seen as the set of all minimal Radon partitions. There is a more general axiomatic definition of order types that roughly requires that the restriction to every $d+3$ points be an order type of $d+3$ points in a real space. For general order types there is a topological representation that replaces the linear description of order types that correspond to point configurations. Another equivalent way to describe the order type is as follows: for every set $J$ of subscripts $i_1$, …, $i_{d+1}$ with $1\le i_1 < \cdots < i_{d+1} \le n$, let $\operatorname {sg}(J,Y)$ be the sign of the determinant of the $(d+1)\times (d+1)$ matrix

$$\begin{equation} \begin{pmatrix} y_{i_1} & y_{i_2}& \cdots & y_{i_{d+1}}\\ 1 & 1 & \cdots & 1 \end{pmatrix}. \tag{1} \end{equation}$$

Two sequences $Y=(y_1,y_2,\dots ,y_n)$ and $Z=(z_1,z_2,\dots ,z_n)$ of $n$ points in $\mathbb{R}^d$ are equivalent (or have the same order type) if $\operatorname {sg}(J,Y)=\operatorname {sg}(J,Z)$ for all $J\subset [n]$ of size $d+1$.

For more on oriented matroids see BLVS$^{+}$93. Returning to families of convex sets, we note that one way to record the mutual position of $n$ convex sets $K_1$, $K_2$, …, $K_n$ in $\mathbb{R}^d$ is by listing all order types of sequences $y_1 \in K_1$, $y_2 \in K_2$, …, $y_n \in K_n$.

Goodman and Pollack’s notion of allowable sequences for configurations GP85 is a very useful way to study order types of planar configurations. The more general notion of interval sequences by Dhandapani, Goodman, Holmsen, and Pollack gives a way to record mutual positions of $n$ convex planar sets DGHP05.

4. Around Tverberg’s theorem

4.1. Sierksma’s conjecture

Conjecture 4.1 (Sierksma’s conjecture).

The number of Tverberg $r$-partitions of a set of $(r-1)(d+1)+1$ points in $\mathbb{R} ^d$ is at least $((r-1)!)^d$.

This question was raised by Sierksma Sie79 in 1979 and not much progress has been achieved since. The best lower bound is about the square root of the conjectured one; this is a result of VŽ93 and Hel07. The conjecture, if true, is sharp, as shown by the example in Figure 3 for $d=2,r=4$: the vertices of the three triangles plus the point in the center is a set with ten points and $3!^2$ Tverberg partitions.

Figure 3.

Ten points with $3!^2$ Tverberg partitions.

In $\mathbb{R}^d$ take analogously $r-1$ $d$-dimensional simplices with their center at the origin; their vertices together with the origin form a set of $(r-1)(d+1)+1$ points with $(r-1)!^d$ Tverberg partitions. There are further cases where equality holds, such as the one connected to the following problem raised by Perles. We need a definition: a Tverberg partition $S_1$, …, $S_r$ of an $m$-element set $X\subset \mathbb{R}^d$ is of type $(a_1,a_2,\ldots , a_r)$ if the multisets $\{a_1,a_2,\ldots , a_r\}$ and $\{|S_1|,|S_2|,\ldots , |S_r|\}$ coincide.

Problem 4.2.

Suppose that $a_1$, $a_2$, …, $a_r$ is a partition of $m=(r-1)(d+1)+1$ such that $1\le a_i\le d+1$ for every $i$. Is there a configuration of $m$ points in $\mathbb{R} ^d$ for which all of Tverberg partitions are of type $(a_1,a_2,\ldots , a_r)$?

This problem was raised by Perles many years ago and a positive answer was given by White Whi17. White’s examples provide a rich family of examples for cases of equality in Sierksma’s conjecture. An even more general family of constructions for the equality cases, based on staircase convexity, is in the paper of Bukh, Loh, and Nivasch BLN17. A similar construction was given by Pór Pór18 in connection with the so-called universal Tverberg partitions.

Problem 4.3.

Explore further examples of equality cases in Sierksma’s conjecture.

4.2. Topological Tverberg

Conjecture 4.4 (Topological Tverberg conjecture).

Let $f$ be a continuous function from the $m$-dimensional simplex $\sigma ^m$ to $\mathbb{R} ^d$. If $m \ge (d+1)(r-1)$, then there are $r$ pairwise disjoint faces of $\sigma ^m$ whose images have a point in common.

If $f$ is a linear function, this conjecture reduces to Tverberg’s theorem. The case $r=2$ was proved by Bajmóczy and Bárány BB79 using the Borsuk–Ulam theorem. Moreover, for $r=2$, one can replace the simplex by any other polytope of the same dimension. The case where $r$ is a prime number was proved in an important paper of Bárány, Shlosman, and Szűcs BSS81. The prime power case was settled by Özaydin, in an unpublished (yet available) paper Öza87. For the prime power case, the proofs are quite difficult and are based on computations of certain characteristic classes.

In 2015 the topological Tverberg conjecture was disproved in a short note by Frick Fri15. This involves some early result on vanishing of topological obstructions by Özaydin, a theory developed by Mabillard and Wagner MW14 extending Whitney’s trick to $k$-fold intersections, and a fruitful reduction by Gromov Gro10, rediscovered and extended by Blagojević, Frick, and Ziegler BFZ19.

Conjecture 4.5.

Let $f$ be a linear function from an $m$-dimensional polytope $P$ to $\mathbb{R} ^d$. If $m \ge (d+1)(r-1)$, then there are $r$ pairwise disjoint faces of $P$ whose images have a point in common.

Problem 4.6.

Does the conclusion of the topological Tverberg conjecture hold if the images of the faces under $f$ form a good cover (that is if all those images and all their nonempty intersections are contractible)?

4.3. Colorful Tverberg

Let $C_1$, …, $C_{d+1}$ be disjoint subsets of $\mathbb{R} ^d$, called colors, each of cardinality at least $t$. A $(d+1)$-subset $S$ of $\mathbb{R}^d$ is said to be multicolored (or rainbow) if $|S\cap C_i|=1$ for $i=1$, …, $d+1$. Let $r$ be an integer, and let $T(r,d)$ denote the smallest value $t$ such that for every collection of colors $C_1$, …, $C_{d+1}$ of size at least $t$ each there exist $r$ disjoint multicolored sets $S_1$, …, $S_r$ such that $\bigcap ^r_{i=1}\operatorname {conv} S_i\not =\emptyset$. The question of finiteness of $T(r,d)$ was raised in BFL90 and proved there for the case $d=2$.

The general case was solved by an important theorem of Živaljević and Vrećica ŽV92. It asserts that $T(r,d)\leq 2r-1$ if $r$ is a prime, which implies that $T(r,d)\leq 4r-1$ for all $r$ and $d$. This theorem is one of the highlights of discrete geometry and topological combinatorics. The only known proofs of this theorem rely on topological arguments although the statement is about convex hulls, partitions, and linear algebra. The following question is a challenge for convex geometers.

Problem 4.7.

Find a nontopological proof of the finiteness of $T(r,d)$.

Bárány and Larman BL92 showed that $T(r,2)=r$ and asked the following.

Conjecture 4.8 (Colorful Tverberg conjecture).

$T(r,d)= r$.

The case where $r+1$ is a prime was proved by Blagojević, Matschke, and Ziegler BMZ15. It is a neat result by Lovász from BL92 that $T(2,d)=2$ for all $d$. Soberón gives an equally neat (and very different) proof of the same result in Sob15.

The colorful Tverberg theorem is related to a well-known problem in discrete geometry, that of halving lines and hyperplanes. Given $2n$ points in general position in $\mathbb{R}^d$, a halving hyperplane is a hyperplane with $n$ points on each side.

Problem 4.9.

What is the maximum number $H(2n,d)$ of partitions of a set of $2n$ points in $\mathbb{R}^d$ into equal parts via halving hyperplanes? Equivalently, what is the minimum number of non-Radon partitions with parts of equal size?

A well-known conjecture, which is open even for $d=2$, is that for a fixed $d$, $H(n,d)=n^{d-1+o(1)}$. With the help of the colorful Tverberg theorem it was shown that $H(n,d)=n^{d-\epsilon _d}$, where $\epsilon _d$ is a positive constant depending on $d$. For $d=2$ it is known that

$$\begin{equation*} n e^{C \sqrt n} H(2,n) \le O(n^{4/3}). \end{equation*}$$

A matroid version of Tverberg’s theorem is the topic of BKM17, which states the following. Assume that $M$ is a matroid of rank $d+1$. Let $b(M)$ denote the maximal number of disjoint bases in $M$. If $f$ is a continuous map from the matroidal complex of $M$ to $\mathbb{R}^d$, then there exist $t\ge \frac{1}{4} \sqrt {b(M)}$ independent sets $\sigma _1$, …, $\sigma _t \in M$ such that $\bigcap _1^t f(\sigma _i)\ne \emptyset$. It is not clear how good this lower estimate on $t$ is.

Conjecture 4.10.

In the above theorem, $\sqrt {b(M)}$ could be replaced by $c b(M)$ for some absolute positive constant $c$.

5. The cascade conjecture and more

When we have $r<d+2$ points in $\mathbb{R}^d$, they have a Radon partition iff they are affinely dependent. Are there conditions that guarantee that the existence of Tverberg partitions below the Tverberg number? In this section we will discuss the dimension of Tverberg points and the quest for conditions guaranteeing the existence of Tverberg partitions for configurations of points below the Tverberg number.

5.1. The cascade conjecture

For a set $A$, denote by $T_r(A)$ the set of points in $\mathbb{R} ^d$ that belong to the convex hull of $r$ pairwise disjoint subsets of $A$. We call these points Tverberg points of order $r$.

Let $\bar{t}_r(A)= 1+ \dim T_r(A)$. (Note that $\dim \emptyset = -1$.) Radon’s theorem can be stated as follows: if $\bar{t}_1(A) < |A|$, then $T_2(A) \ne \emptyset$. There is a similar statement which is still open: if $\bar{t}_1(A)+\bar{t}_2(A) < |A|$, then $T_3(A) \ne \emptyset$. We can go one step further: if $\bar{t}_1(A)+\bar{t}_2(A) +\bar{t}_3(A)< |A|$, then $T_4(A) \ne \emptyset$. These statements are special cases of the following.

Conjecture 5.1 (Cascade conjecture).

For every $A \subset \mathbb{R} ^d$,

$$\begin{equation*} \sum _{r \ge 1} \bar{t}_r(A) \ge |A|. \end{equation*}$$

This is a question of Kalai from 1974 Kal95; see also Kal00. The conjecture was proved for $d \le 2$ by Akiva Kadari (unpublished MSc thesis in Hebrew). While this conjecture is wide open, we can ask for topological extensions of various kinds and for more general topological conditions for configurations of cardinality below the Tverberg number $(r-1)(d+1)+1$, that imply the existence of a Tverberg partition into $r$ parts; see Problem 5.4.

5.2. Reay’s dimension conjecture

The following is a 1979 question from Reay Rea79 where general position means weak general position; that is, no $d+1$ points lie in a hyperplane.

Conjecture 5.2 (Reay’s conjecture).

If $A$ is a set of $(d+1)(r-1)+1+k$ points in general position in $\mathbb{R} ^d$, then

$$\begin{equation*} \operatorname {dim} T_r(A) \ge k. \end{equation*}$$

In particular, Reay’s conjecture asserts that a set of $(d+1)r$ points in general position in $\mathbb{R} ^d$ can be partitioned into $r$ sets of size $d+1$ such that the simplices described by these sets have an interior point in common. This is easy when the points are in very general position, for instance, when they are algebraically independent. The main difficulty is how to use the weak general position condition. A recent result of Frick and Soberón FS20 (see Section 7.1) is perhaps relevant here. While the conclusion of the cascade conjecture seems stronger than that of Reay’s dimension conjecture, it is not known how to derive it from the cascade conjecture.

5.3. Special cases of the cascade conjecture and expressing a directed graph as union of two trees

A special case of the cascade conjecture asserts that given $2d+2$ points in $\mathbb{R} ^d$, you can either partition them into two simplices whose interiors intersect, or you can find a Tverberg partition into three parts. We give a reformulation based on positive hulls: given $2d$ nonzero vectors in $\mathbb{R} ^d$ such that the origin is a vertex of the cone spanned by them, it is the case that either:

•

we can divide the points into two sets $A$ and $B$ so that the cones spanned by them have a $d$-dimensional intersection; or

•

we can divide them into three sets $A$, $B$, and $C$ so that the cones spanned by them have a nontrivial intersection.

Another interesting reformulation is obtained when we dualize using the Gale transform, and this has led to the problem we consider next: a very special class of configurations arising from graphs. Start from a directed graph $G$ with $n$ vertices and $2n-2$ edges and associate with each directed edge $(i,j)$ the vector $e_j-e_i$. This leads to the following problem.

Problem 5.3.

Let $G$ be a directed graph with $n$ vertices and $2n-2$ edges. When can we divide the set of edges into two trees $T_1$ and $T_2$ (we disregard the orientation of edges) so that when we reverse the directions of all edges in $T_2$ we get a strongly connected digraph?

One of us (Kalai) conjectured that if $G$ can be written as the union of two trees, the only additional obstruction is that there is a cut consisting only of two edges in reversed directions. Chudnovsky and Seymour found an additional necessary condition: there is no induced cycle $v_1$, $v_k$, …, $v_{2k}$, $v_1$ in $G$, such that each vertex $c_i$ is cubic, the edges of the cycle alternate in direction, and none of the vertices $v_1$, …, $v_{2k}$ are sources or sinks of $G$.

5.4. Tverberg partitions of order $3$ for configurations below the Tverberg number

Problem 5.4.

When $n < 2d+3$, find conditions for the set of Radon points and the set of Radon partitions of a set $X$ of $n$ points in $\mathbb{R}^d$ that guarantee the existence of a Tverberg partition into three parts.

The cascade conjecture asserts that if $n=d+2+k$ and the dimension of Radon points is smaller than $k$, then there exists a Tverberg partition into three parts. While this is wide open, it would be interesting to propose a more general topological condition that suffices for the existence of a Tverberg partition into $r$ parts.

Conjecture 5.5.

If the map from the Radon partitions of $X$ to the Radon points of $X$ is topologically degenerate (in some sense), then a Tverberg partition into three parts exists.

In Problem 5.4 and Conjecture 5.5 we can relax the conclusion and can do so in various ways. For that we need a few definitions: The $k$-core of a finite set $X$ in $\mathbb{R}^d$ is the intersection of the convex hull of all sets $A\subset X$ with $|X\setminus A|\le k$, that is,

$$\begin{equation*} \operatorname {core}_k X=\bigcap \{\operatorname {conv} A: A\subset X,\; |X\setminus A|\le k\}. \end{equation*}$$

The case $k=0$ is the usual convex hull. The $k$-Radon core of a finite set $X$ in $\mathbb{R}^d$ is the intersection of Radon points of all sets $A\subset X$ with $|X\setminus A|\le k$; this is the set of points in $\mathbb{R}^d$ that remain Radon points of $X$ even after we delete $k$ points from $X$ in all possible ways. (Clearly, the Tverberg points of order $3$ are in the first Radon core, and the points in the first Radon core are in the 2-core.)

Problem 5.6.

When $n < 2d+3$, find conditions for the set of Radon points and the set of Radon partitions of a set $X$ of $n$ points in $\mathbb{R}^d$ that guarantee the following:

(1)

the second core of $X$, $\operatorname {core}_2 X$, is nonempty;

(2)

the first Radon core of $X$ is nonempty;

(3)

$X$ admits a Reay (3,2)-partition, that is, a partition into three parts such that the convex hulls are pairwise intersecting (see Section 6.2).

5.5. Radon partitions and Radon points for configurations based on cubic graphs

Let $G$ be a cubic graph with $n$ vertices $\{v_1,v_2,\dots , v_n\}$. Associate with every edge $\{v_i,v_j\}$ in $G$ its characteristic vector in $\mathbb{R}^d$, giving a configuration $\operatorname {Conf} (G)$ of $3n/2$ points in $(n-1)$-dimensional space. In Onn01 and also in personal communication (2011), Onn observed that the existence of a Tverberg 3-partition (or even of a Reay (3,2)-partition; see Section 6.2) is equivalent to a 3-edge coloring for $G$, and he concluded that deciding if a configuration of $3(d+1)/2$ points in $\mathbb{R}^d$ ($d$ an odd integer) admits a Tverberg partition into three parts is NP-complete.

The following problem is motivated by the four-color theorem.

Problem 5.7.

(i)

Study Radon partitions and Radon points for configurations based on cubic graphs.

(ii)

Find conditions for the Radon points and Radon partitions of $\operatorname {Conf}(G)$ that guarantee a 3-edge coloring for $G$.

It would be interesting to find conditions for Problem 5.4 and Conjecture 5.5 that would imply the 3-edge colorability of bipartite cubic graphs and, much more ambitiously, conditions that would imply the four-color theorem, namely, the 3-edge colorability of planar cubic graphs.

6. More around Tverberg’s theorem

6.1. Eckhoff’s partition conjecture

Let $X$ be a set endowed with an abstract closure operation $X \to \operatorname {cl}(X)$. The only requirements of the closure operation are

(1)

$\operatorname {cl}(\operatorname {cl} (X))=\operatorname {cl}(X)$, and

(2)

$A \subset B$ implies $\operatorname {cl}(A) \subset \operatorname {cl}(B)$.

Define $t_r(X)$ to be the largest size of a (multi)set in $X$ that cannot be partitioned into $r$ parts whose closures have a point in common. The following conjecture is due to Eckhoff Eck00.

Conjecture 6.1 (Eckhoff’s partition conjecture).

For every closure operation,

$$\begin{equation*} t_r \le t_2 \cdot (r-1). \end{equation*}$$

If $X$ is the set of subsets of $\mathbb{R} ^d$ and $\operatorname {cl}(A)$ is the convex hull operation, then Radon’s theorem asserts that $t_2(X)=d+1$ and Eckhoff’s partition conjecture implies Tverberg’s theorem. In 2010 Eckhoff’s partition conjecture was refuted by Boris Bukh Buk10. Bukh’s beautiful paper contains several important ideas and further results. We will mention one ingredient. Recall the nerve construction for moving from a family $\mathcal{F}$ of $n$ convex sets to the simplicial complex that records empty and nonempty intersections for all subfamilies $\mathcal{G}$ of $\mathcal{F}$. Bukh studied simplicial complexes whose vertex sets correspond to the power set of a set of size $n$: starting with $n$ points in $\mathbb{R} ^d$ or some abstract convexity space, consider the nerve of convex hulls of all $2^n$ subsets of these points!

In Bukh’s counterexample, $t_r = t_2 \cdot (r-1)+1$, which is just one larger than the conjectured bound. Perhaps $t_r \le t_2 \cdot (r-1)+c$ for some universal constant $c\ge 1$. There is a recent and positive development about Eckhoff’s conjecture. Pálvölgyi Pál20 has proved that $t_r$ grows linearly in $r$, that is, $t_r \le c r$ where the constant $c$ depends only on $r_2$.

Problem 6.2.

Find classes of closure operations for which

$$\begin{equation*} t_r \le t_2 \cdot (r-1). \end{equation*}$$

We can ask if the inequality $t_r \le t_2 \cdot (r-1)$ holds for Moran and Yehudayoff’s convexity spaces considered in Section 2.5.

Bukh’s paper includes an interesting notion that extends the notion of nerves. Given a configuration of points in the Euclidean space or in an abstract convexity space, we consider the nerve of convex hulls of all nonempty subsets of the points. This is a simplicial complex that we refer to as the $B$-nerve of the configuration, with the additional structure that vertices are labeled by subsets, and with some additional combinatorial properties.

Problem 6.3.

Study properties of $B$-nerves of point configurations in $\mathbb{R}^d$.

6.2. A conjecture by Reay

For a set $X \subset \mathbb{R} ^d$, a Reay $(r,j)$-partition is a partition of $X$ into subsets $S_1$, $S_2$, …, $S_r$ such that $\bigcap _{i=1}^j \operatorname {conv} S_{k_i} \ne \emptyset$, for every $1 \le k_1 < k_2< \cdots < k_j \le r$. In other words, the convex hulls of any $j$ sets of the partition intersect. Define $R(d,r,j)$ as the smallest integer $m$ such that every $m$-element set $X \subset \mathbb{R}^d$ has a Reay $(r,j)$-partition. Reay Rea79 conjectured that you cannot improve the value given by Tverberg’s theorem, namely, that

Conjecture 6.4 (Reay’s conjecture).

$R(d,r,j)= (r-1)(d+1)+1$.

Micha A. Perles believes that Reay’s conjecture is false even for $j=2$ and $r=3$ for large dimensions but, with Moriah Sigron, he proved PS16 the strongest positive results in the direction of Reay’s conjecture.

6.3. Two old problems and universality

Problem 6.5 (McMullen and Larman).

How many points $v(d)$ guarantee that for every set $X$ of $v(d)$ points in $\mathbb{R}^d$ there exists a partition into two parts $X_1$ and $X_2$ such that for every $p \in X$,

$$\begin{equation*} \operatorname {conv} (X_1 \backslash p) \cap \operatorname {conv} (X_2 \backslash p )\ne \emptyset . \end{equation*}$$

This is a strong form of Radon’s theorem: the partition $X_1$, $X_2$ of $X=X_1\cup X_2$ remains a Radon partition even after we delete any point from $X$. Similar questions can be asked about Tverberg partitions. Larman Lar72 proved that $v(d) \le 2d+3$ and this bound is sharp for $d=1$, $2$, $3$, $4$. The lower bound $v(d)\ge \lceil \frac{5d}{3}\rceil +3$ is a result of Ramírez Alfonsín RA01. This problem is the dual form of the original question by McMullen: What is the largest integer $n=f(d)$ such that every set of $n$ points in general position in $\mathbb{R}^d$ is projectively equivalent to the set of vertices of a convex polytope?

A related problem is the following.

Problem 6.6.

How many points $T(d;s,t)$ in $\mathbb{R} ^d$ guarantee that they can be divided into two parts such that every union of $s$ convex sets containing the first part has a nonempty intersection with every union of $t$ convex sets containing the second part?

We explain next why $R(d; s,t)$ is finite. This is a fairly general Ramsey-type argument and it gives us an opportunity to mention a few recent important results. The argument has two parts:

(1)

Prove that $T(d;s,t)$ is finite (with good estimates) when the points are in cyclic position (to be defined shortly).

(2)

Use the fact that for every $d$ and $n$ there is $f(d,n)$ such that among every $m$ points in general position in $\mathbb{R} ^d$, $m> f(d,n)$, one can find $n$ points in cyclic position.

The finiteness of $T(d;r,s)$ follows (with horrible bounds) from these two ingredients by standard Ramsey-type results. It would be nice to understand the behavior of this function.

Statement (2) is a kind of universality theorem. In a more precise form it says that for every $d$ and $n$ there is an integer $f(d,n)$ such that the following holds. Every sequence $x_1$, …, $x_m$ in $\mathbb{R}^d$ in general position with $m\ge f(d,n)$ contains a subsequence $y_1$, …, $y_n$ such that all simplices of this subsequence are oriented the same way. The latter condition says, in more precise form, that for every set of subscripts $i_1$, …, $i_{d+1}$ with $1\le i_1 < \cdots < i_{d+1} \le n$, the sign of the determinant of the $(d+1)\times (d+1)$-matrix

$$\begin{equation} \begin{pmatrix} y_{i_1} & y_{i_2}& \cdots & y_{i_{d+1}}\\ 1 & 1 & \cdots & 1 \end{pmatrix} \tag{2} \end{equation}$$

is the same (and different from $0$). Now a point set is cyclic if its elements can be ordered so that the simplices along this ordering have the same orientation.

Statement (2) says that the property of being cyclic is universal because every long enough sequence of points in general position contains a cyclic subsequence of length $n$. Every finite sequence of points on the moment curve is cyclic. This shows that no other type of point sequence can be universal. Recently, a fairly good understanding of $f(d,n)$ has been achieved in a series of papers.

Theorem 6.1.

$f(d,n) ={\mathrm{twr}}_d(\theta (n))$.

Here, ${\mathrm{twr}}_d$ is the $d$-fold tower function. The lower bound is by Suk Suk14 (improving earlier bounds by Conlon, Fox, Pach, Sudakov, and Suk CFP$^{+}$14) and the upper bound comes from Bárány, Matoušek, and Pór BMP16.

The following, somewhat vague, question emerges here naturally.

Problem 6.7.

Determine the universal type of $n$ lines in $\mathbb{R}^3$ and in $\mathbb{R}^d$. More generally, what is the universal type of $n$ $k$-dimensional affine flats in $\mathbb{R}^d$?

Some preliminary results in this direction are the topic of a forthcoming paper by Bárány, Kalai, and Pór BKP21.

We note that the order type of a sequence of points does not determine its Tverberg partitions.

Problem 6.8.

Develop a notion of order type based on Tverberg partitions into at most $r$ parts, $r \ge 3$.

Here, Perles and Sigron’s work on strong general position PS16 and Pór’s universality theorem Pór18 could be relevant.

7. Carathéodory and weak $\epsilon$-nets

7.1. Colorful Carathéodory and the Rota basis conjecture

The following question was raised in Chow’s Polymath 12 Cho17 dedicated to Rota’s basis conjecture. Consider the $d+1$ sets (or colors if you wish) $C_1$, $C_2$, …, $C_{d+1}$ of points in $\mathbb{R} ^d$. Assume that each $|C_i|=d+1$ and that the interior of each $\operatorname {conv} C_i$ contains the origin.

Problem 7.1 (D. H. J. Polymath).

Can we find a partition of all points into $d+1$ rainbow parts such that the interior of the convex hulls of the parts have a point in common. (A rainbow set is a set containing one element from each $C_i$.)

To see the connection, first recall Rota’s basis conjecture.

Conjecture 7.2 (Rota’s basis conjecture).

If $B_1$, $B_2$, …, $B_n$ are disjoint bases in $\mathbb{R}^n$ (or even in an arbitrary matroid), then it is possible to find $n$ new disjoint bases $C_1$, $C_2$, …, $C_n$ such that each $C_i$ contains one element from every $B_j$.

Note that Rota’s basis conjecture can be stated (over $\mathbb{R}$) as follows. Consider $d+1$ sets (or colors) $C_1$, $C_2$, …, $C_{d+1}$ of points in $\mathbb{R} ^d$. Assume that each $|C_i|=d+1$ and that the interior of each $\operatorname {conv} C_i$ is nonempty. Then there exists a partition of all points into $d+1$ rainbow parts such that the interior of the convex hulls of each part is nonempty.

Returning to Problem 7.1, we note here that according to the colorful Carathéodory theorem there is a rainbow set whose convex hull contains the origin. Without the words “the interiors of”, Problem 7.1 would be a special case of the colorful Tverberg conjecture (Section 4.3). A positive answer would be a strong variant of Reay’s conjecture (Section 5.2) on the dimension of Tverberg points, and, as explained before, also a strong form of Rota’s basis conjecture over the reals.

A recent result of Frick and Soberón FS20 is that a set of $r(d+1)$ points in $\mathbb{R}^d$ can always be partitioned into $r$ sets, each of size $d+1$, such that the convex hulls of the parts have a point in common. This theorem is related to the uncolored case of Problem 7.1 but without the word “interior”.

7.2. The complexity of the colorful Carathéodory theorem and of Tverberg partitions

Problem 7.3.

Consider $d+1$ sets $C_1$, $C_2$, …, $C_{d+1}$ of points in $\mathbb{R} ^d$. Assume that each $|C_i|=d+1$ and that each $\operatorname {conv} C_i$ contains the origin. Is there a polynomial-time algorithm to find a rainbow simplex containing the origin?

An interesting result in this direction is due to Meunier et al. MMSS17. They show that the problem lies in the intersection of complexity classes PPAD and PLS. The same applies to the analogous question about Tverberg partitions: Is there a polynomial-time algorithm to find a Tverberg partition of an $(r-1)(d+1)+1$-element point set in $\mathbb{R}^d$? There are very few geometric problems in both classes PPAD and PLS that are not known to be solvable in polynomial time. The results in MMSS17 are the first upper bound on the complexity of these problems.

7.3. Carathéodory-type theorem for cores

Recall the definition of the $k$-core of a finite set $X$ in $\mathbb{R}^d$ from Section 5.4. The Carathéodory number for the $k$-core is the smallest integer $f(d,k)$ with the property that $a \in \operatorname {core}_k X$ (where $X \subset \mathbb{R}^d$) implies the existence of $Y \subset X$ such that $a \in \operatorname {core}_k Y$ and $|Y| \le f(d,k)$. So $f(d,0)=d+1$ is just the Carathéodory theorem. Bárány and Perles BP90 established the finiteness of $f(d,k)$ together with some other properties of this function, for instance, that $f(d,1)=\max \{2(d+1),1+d+\lfloor d^2/4 \rfloor \}$, and that $f(2,k)=3(k+1)$. Several questions remain open; we mention only two of them.

Problem 7.4.

Determine $f(d,2)$ and $f(3,k)$.

7.4. The covering number theorem

Assume that $X \subset \mathbb{R}^d$ is finite and $|X|\ge d+1$. A simplex of $X$ is just $\operatorname {conv} Y$ where $Y \subset X$ and $|Y|=d+1$. According to Carathéodory’s theorem every point in $\operatorname {conv} X$ is contained in a simplex of $X$; that is, $\operatorname {conv} X$ is covered by the simplices of $X$. Which point is covered maximally, and how many times is it covered? A famous result of Boros and Füredi BF84 says that in the planar case there is a point covered by $\frac{2}{9} {n \choose 3}+O(n^2)$ simplices (that is, triangles) of $X$, where $n=|X|$. This is a positive fraction of all triangles of $X$ and the constant $\frac{2}{9}$ is the best possible. In higher dimensions Tverberg’s theorem and the colorful Carathéodory theorem imply (see Bár82) the following result.

Theorem 7.1 (Covering number).

Assume $X$ is a set of $n\ge d+1$ points in $\mathbb{R}^d$. Then there is a point covered by $\frac{1}{(d+1)^d}{n \choose d+1}$ simplices of $X$.

This is again a positive fraction of all simplices of $X$. Define $b_d$ as the supremum of all $\beta >0$ such for that every set $X$ of $n\ge d+1$ points in $\mathbb{R}^d$ there is a point covered by $\beta {n \choose d+1}$ simplices of $X$. So $b_d \ge (d+1)^{-d}$. In a remarkable paper, Gromov Gro10 showed that $b_d\ge \frac{2d}{(d+1)!(d+1)}$. Gromov’s theorem applies to continuous maps from the boundary of an $(n-1)$-dimensional simplex to $\mathbb{R}^d$. His estimate is an exponential improvement on the previous bounds. Both Gromov’s theorem and Pach’s theorem below play an important role in the emerging theory of high-dimensional expanders FGL$^{+}$12.

From the other direction Bukh, Matoušek, and Nivasch BMN11 give an example, based on the stretched grid, that shows $b_d \le \frac{(d+1)!}{(d+1)^{d+1}}$. They conjecture that this is the right value of $b_d$.

Conjecture 7.5.

Show that $b_d = \frac{(d+1)!}{(d+1)^{d+1}}$. More modestly, prove that $b_d$ is exponential in $d$.

An interesting extension of the covering number theorem is the following result of Pach Pac98.

Theorem 7.2 (Pach’s theorem).

Assume that $C_1$, …, $C_{d+1}$ are sets (colors, if you like) in $\mathbb{R}^d$, each of size $n$. Then there is a point $p\in \mathbb{R}^d$ and there are subsets $D_i \subset C_i$ (for all $i\in [d+1]$), each of size at least $c(d)n$ such that the convex hull of every transversal of the system $D_1$, …, $D_{d+1}$ contains $p$. Here $c(d)>0$ is a constant that depends only on $d$.

This is a homogeneous version of the covering number theorem. It was conjectured in BFL90, where case $d=2$ was proved more generally even if the sets $C_1,C_2,C_3$ need not have the same size. This raises the following question.

Problem 7.6.

Does Pach’s theorem remain true if the sets $C_1$, …, $C_{d+1}$ have arbitrary sizes?

We mention that Pach’s theorem does not have a topological extension, as shown in BMNT18 and in BH20 in a stonger form.

7.5. Weak $\epsilon$-nets

An important application of the covering number theorem is about weak $\epsilon$-nets. Let $\epsilon >0$ be fixed. Given a finite set $X$ of $n\ge d+1$ points, let $\mathcal{C}$ be the (finite) family of sets $\operatorname {conv} Y$ for all $Y \subset X$ with $|Y|\ge \epsilon n$. A set $F \subset \mathbb{R}^d$ is called a weak $\epsilon$-net for $X$ if $F\cap C\ne \emptyset$ for every $C \in \mathcal{C}$.

Theorem 7.3 (Weak $\epsilon$-net theorem).

Under the above conditions there is a weak $\epsilon$-net $F$ for $X$ such that

$$\begin{equation*} |F| \le \frac{c_d}{\epsilon ^{d+1}}, \end{equation*}$$

where $c_d>0$ is a constant.

The upper bound on the size of $F$ is from AK92b and ABFK92 and has been improved to $O(\epsilon ^{-d})$, disregarding some logarithmic terms. The trivial lower bound on the size of $F$ is $\frac{1}{\epsilon }$. Bukh, Matoušek, and Nivasch BMN11 give an example (based on the stretched grid or staircase convexity) where the size of the weak $\epsilon$-net is at least of order $\frac{1}{\epsilon }(\log \frac{1}{\epsilon })^{d-1}$. So the bounds on the size of a weak $\epsilon$-net are far from each other, and the general belief is that the true behavior should be slightly superlinear in $\frac{1}{\epsilon }$.

Problem 7.7.

Find a better upper bound for the size of a weak $\epsilon$-net.

One remarkable improvement in this direction is a result of Rubin Rub18 who showed that in the planar case there is always a weak $\epsilon$-net of size of order $\frac{1}{\epsilon ^{1.5+\delta }}$ for any $\delta >0$. A more recent result of Rubin Rub21 applies in any dimension $d\ge 2$ and gives a weak $\epsilon$-net of size of order $\frac{1}{\epsilon ^{d-1/2+\delta }}$ for any $\delta >0$.

Weak $\epsilon$-nets can be defined not only for points but for $k$-dimensional affine flats in $\mathbb{R}^d$. We only state the question for lines in $\mathbb{R}^3$ and leave the rest of the cases to our imaginary reader. Let $\mathcal{L}$ be a set of $n$ lines, and let $\mathcal{C}$ be a finite family of convex sets in $\mathbb{R}^3$. Assume that every $C \in \mathcal{C}$ intersects an $\epsilon$-fraction of the lines in $\mathcal{L}$, that is,

$$\begin{equation*} |\{L \in \mathcal{L}: C\cap L\ne \emptyset \}| \ge \epsilon n \text{ for every } C \in \mathcal{C}. \end{equation*}$$

Conjecture 7.8 ($\epsilon$-net of lines).

Under these conditions, there is a set of lines $\mathcal{L}^*$ whose size depends only on $\epsilon$ such that every $C\in \mathcal{C}$ intersects some line in $\mathcal{L}^*$.

The set $\mathcal{L}^*$ can be thought of as a weak $\epsilon$-net of lines for $\mathcal{C}$. We will encounter this question again soon in connection with Problem 8.1.

8. A glance at common transversals

8.1. Transversals for intersecting families

A $k$-transversal of a family of convex sets in $\mathbb{R}^d$ is a $k$-dimensional affine space that intersects every set in the family. Transversal theory deals with conditions that guarantee the existence of $k$-transversals. The case $k=0$ is connected to Helly-type theorems, and there are some general results for hyperplane transversals, namely, $k=d-1$, and very few general results for $0<k<d-1$ and, in particular, for line transversals in $\mathbb{R}^3$. The fascinating theory geometric transversals goes beyond the scope of this paper; for surveys see Goodman, Pollack, and Wenger GPW93, Wenger Wen99, and Holmsen Hol13. We will mention only a few problems where the conditions are in terms of the intersection pattern of the sets in the family.

Problem 8.1.

Assume that a family $\mathcal{C}$ of $n$ convex sets in $\mathbb{R}^3$ satisfies the property that any two sets in $\mathcal{C}$ intersect. Show that there is a line intersecting $cn$ elements in $\mathcal{C}$, where $c>0$ is a universal constant.

Partial results in this direction are given in Bár21. Problem 8.1 is the first, and so far most interesting, unsolved case of a series of problems of the same type. Namely, for what numbers $k,r,d$ is it true that, given a family $\mathcal{C}$ of convex sets in $\mathbb{R}^d$ where every $k$ tuple is intersecting, there is an $r$-flat intersecting a positive fraction of the sets in $\mathcal{C}$? Of course, the positive fraction should depend only on $k$, $r$, and $d$.

An interesting example satisfying the conditions is when $\mathcal{C}$ consists of $n$ lines in a two-dimensional plane in $\mathbb{R}^3$. Then, of course, every set in $\mathcal{C}$ is a line transversal for all sets in $\mathcal{C}$. This example shows that degenerate cases are going to make the problem difficult. Figure 4 is an example of five pairwise intersecting convex sets in $\mathbb{R}^3$ without a common line transversal. The five sets comprise three rectangles and two triangles, all of whose vertices belong to two parallel planes $H_0$ and $H_1$.

The question comes from a paper by Martínez, Roldán, and Rubin MSRPR20 and is connected to the colorful Helly theorem. They also ask the slightly more general bipartite version of the question.

Problem 8.2.

Assume $\mathcal{F}$ and $\mathcal{G}$ are finite families of convex sets in $\mathbb{R}^3$ with the property that $A \cap B\ne \emptyset$ for any two sets $A \in \mathcal{F}$ and $B \in \mathcal{G}$. Show that there is a line intersecting $c|\mathcal{F}|$ elements of $\mathcal{F}$ or $c|\mathcal{G}|$ elements of $\mathcal{G}$ where $c>0$ is again a universal constant.

An example is two sets $\mathcal{F}$ and $\mathcal{G}$ of lines on a doubly ruled surface, which shows that degenerate cases may cause difficulties again. It is worth mentioning that both questions are invariant under nondegenerate affine transformation.

We observe here that a positive answer to Conjecture 7.8 from the last section would imply that in Problem 8.1 there is a very finite set $\mathcal{L}$ of lines intersecting every element of $\mathcal{C}$, where by “very finite” we mean that the size of $\mathcal{L}$ is bounded by 1000, say, or by some other absolute constant.

9. Conclusion

This paper introduces the fascinating area of Helly-type theorems, and describes some of its main themes and goals through a variety of open problems. Often, results from convexity give a simple and strong manifestation of theorems from topology: Helly’s theorem manifests the nerve theorem from algebraic topology, and Radon’s theorem can be regarded as an early “linear” appearance of the Borsuk–Ulam theorem. One of our main themes is to further explore these connections to topology. Helly-type theorems also offer complex and profound combinatorial connections and applications that represent the second main theme of this paper. We note that Helly-type theorems and the interplay between convex geometry, combinatorics, and topology play an important role in the emerging theory of high-dimensional expanders.

There are various related parts of this theory that we did not consider. We gave only a small taste of the theory of common transversals, we did not discuss the closely related theorems of Kirchberger and Krasnoselskiǐ, and we did not consider the rich connections to metric geometry. For example, when you consider families of translates of a fixed convex set, the theory takes interesting and surprising turns, and it has applications and connections, e.g., to the theory of Banach spaces.

Figure 1.

$TK_5$

Figure 2.

Mutual positions of three convex sets.

Figure 4.

Five sets in $\mathbb{R}^3$ that pairwise intersect and have no line transversal.