A Sparse Colorful Polytopal KKM Theorem

Abstract

Recently Soberón (Proc. Am. Math. Soc. Ser. B 9, 404–414 (2022)) proved a far-reaching generalization of the colorful KKM Theorem due to Gale (Int. J. Game Theory 13(1), 61–64 (1984)): let $n\ge k$, and assume that a family of closed sets $(A^i_j\,|\,i\in [n],\,j\in [k])$ has the property that for every $I\in \left( {\begin{array}{c}[n]\\ n-k+1\end{array}}\right)$, the family $\bigl (\bigcup _{i\in I}A^i_1,\dots ,\bigcup _{i\in I}A^i_k\bigr )$ is a KKM cover of the $(k-1)$-dimensional simplex $\Delta ^{k-1}$; then there is an injection $\pi :[k] \rightarrow [n]$ such that $\bigcap _{j=1}^k A_j^{\pi (j)}\ne \emptyset$. We prove a polytopal generalization of this result, answering a question of Soberón in the same note. We also discuss applications of our theorem to fair division of multiple cakes, d-interval piercing, and a generalization of the colorful Carathéodory theorem.

1 Introduction

The KKM theorem due to Knaster, Kuratowski, and Mazurkiewicz [9] is a set covering version of Sperner’s lemma [17] and Brouwer’s fixed point theorem.

KKM Theorem 1.1

[9] If a family of closed subsets $(A_1,\dots ,A_k)$ of the $(k-1)$-dimensional simplex $\Delta ^{k-1} ={{\,\textrm{conv}\,}}{\{v_1,\dots ,v_k\}}$ satisfies $\sigma \subseteq \bigcup _{v_i \in \sigma } A_i$ for every face $\sigma$ of $\Delta ^{k-1}$ (including for $\sigma =\Delta ^{k-1}$), then $\bigcap _{i=1}^k A_i \ne \emptyset$.

A family of sets $(A_1,\dots ,A_k)$ satisfying the conditions of the KKM theorem is called a KKM cover of $\Delta ^{k-1}$. The KKM theorem has numerous applications in all areas of mathematics (as do its equivalents—Sperner’s lemma and Brouwer’s fixed point theorem). It has many known generalizations that are widely applied as well (see e.g., [4] and the references therein). In this paper we prove a new generalization of the KKM theorem and use it to prove results in discrete geometry and in fair division.

One important extension of the KKM theorem is the colorful KKM theorem by Gale [6]:

Colorful KKM Theorem 1.2

Given k KKM covers $(A^i_1,\dots ,A^i_k)$ for $1\le i\le k$, there exists a permutation $\pi :[k] \rightarrow [k]$ such that $\bigcap _{i=1}^k A_i^{\pi (i)}\ne \emptyset$.

We think of each KKM cover as associated with a distinct color; the theorem gives a non-empty intersection of a “colorful" selection of sets, where each set is taken from a distinct KKM cover. Gale’s theorem specializes to the KKM theorem when all the KKM covers are the same cover.

Another well-known generalization of the KKM theorem is the KKMS theorem, due to Shapley [13], which applies to more general covers of the simplex. Komiya proved a polytopal generalization of the KKMS theorem:

Theorem 1.3

[10] Let P be a $(k-1)$-dimensional polytope. Suppose that for every non-empty face $\tau$ of P we are given a closed subset $A_\tau$ of P and a point $y_\tau \in \tau$. If $\sigma \subseteq \bigcup _{\tau \subseteq \sigma }A_\tau$ for every face $\sigma$ of P (including P itself), then there exist faces $\tau _1,\dots ,\tau _k$ of P such that $p\in {{\,\textrm{conv}\,}}{\{y_{\tau _1},\dots ,y_{\tau _k}\}}$ and $\bigcap _{i=1}^k A_{\tau _i}\ne \emptyset$.

A family of sets $(A_\tau \,|\,\tau ~\text {a face of}~P)$ satisfying the condition of Theorem 1.3 is called a Komiya cover of P. If $P=\Delta ^{k-1}$, $y_p$ is a point in the interior of P, and $A_\tau =\emptyset$ for every face $\tau$ of dimension greater than 0, then we recover the KKM theorem. The KKMS theorem is the case where P is the $(k-1)$-simplex and $y_\tau$ is the barycenter of $\tau$ for every face $\tau$. A colorful generalization of Komiya’s theorem was proved by Frick and Zerbib.

Theorem 1.4

[4] Let P be a $(k-1)$-dimensional polytope with $p\in P$. Suppose for every non-empty proper face $\tau$ of P we are given k closed subsets $A^1_\tau ,\dots , A^k_\tau$ of P and k points $y^1_\tau ,\dots ,y^k_\tau \in \tau$. If for every $i\in [k]$ and every face $\sigma$ of P, we have $\sigma \subset \bigcup _{\tau \subset \sigma }A^i_\tau$, then there exist faces $\tau _1,\dots ,\tau _k$ of P such that $p\in {{\,\textrm{conv}\,}}{\{y^1_{\tau _1},\dots ,y^k_{\tau _k}\}}$ and $\bigcap _{i=1}^kA^i_{\tau _i}\ne \emptyset$.

Note that Theorem 1.4 is true also if all the sets $A_{\sigma }$ are open in P. Indeed, given an open cover $\{A_\sigma \,|\,\sigma ~ \text {a nonempty face of}~{ P}\}$ of P as in Theorem 1.4, we can find closed sets $B_\sigma \subset A_\sigma$ that have the same nerve as $A_\sigma$ (namely, any collection of sets $\{B_{\sigma _i}\,|\,i\in I\}$ intersects if and only if the corresponding collection $\{A_{\sigma _i}\,|\,i\in I\}$ intersects) and still satisfy $\sigma \subset \bigcup _{\tau \subset \sigma } B_\tau$ for every face $\sigma$ of P. This implies that the KKM theorem and all its generalization mentioned above are true also when all the sets in the given cover are open.

Recently, Soberón [16] proved a beautiful generalization of the colorful KKM theorem that we call here the sparse colorful KKM theorem. Let $n\ge k$. A family of all closed (or all open) sets $(A^i_1,\dots ,A^i_k\mid i\in [n])$ forms a k-weakly KKM cover of $\Delta ^{k-1}$ if for every $I\in \left( {\begin{array}{c}[n]\\ n-k+1\end{array}}\right)$, the sets $\bigl (\bigcup _{i\in I}A^i_1,\dots ,\bigcup _{i\in I}A^i_k\bigr )$ form a KKM cover of $\Delta ^{k-1}$. The notion of a k-weakly KKM cover was defined by Soberón [16], where he proved

Theorem 1.5

Let $n\ge k$ be positive integers. Assume the family $(A^i_1,\dots , A^i_k \mid i\in [n])$ forms a k-weakly KKM cover of $\Delta ^{k-1}$. Then there is an injection $\pi :[k] \rightarrow [n]$ such that $\bigcap _{j=1}^k A_j^{\pi (j)}\ne \emptyset$.

In the same note, Soberón asked whether Theorem 1.5 can be extended to coverings of general polytopes, in the same way that Theorem 1.4 generalizes the colorful KKM theorem. In this paper we positively answer this question. We first give a definition of k -weakly Komiya cover for a general polytope P. Given a polytope P, let F(P) denote the set of non-empty, proper faces of P.

Definition 1.6

(k-weakly Komiya cover)   Let $n\ge k$ be positive integers, and let P be a $(k-1)$-dimensional polytope. A family of closed sets $(A^i_\sigma \,|\,i\in [n],\,\sigma \in F(P))$, is called a k -weakly Komiya cover of P if for every $I\in \left( {\begin{array}{c}[n]\\ n-k+1\end{array}}\right)$, the family $\bigl (\bigcup _{i\in I}A^i_\sigma \mid \sigma \in F(P)\bigr )$ is a Komiya cover of P.

Our main theorem is the following.

Theorem 1.7

Let $n\ge k\ge 2$ be integers. Let P be a $(k-1)$-dimensional polytope with $p\in P$. Assume that for every $\tau \in F(P)$, we are given n points $y_\tau ^1,\dots ,y_\tau ^n\in \tau$. If the family $(A^i_\tau \,|\,i\in [n],\,\tau \in F(P))$ forms a k-weakly Komiya cover of P, then there exists an injection $\pi :[k]\rightarrow [n]$ and faces $\tau _{1},\dots ,\tau _{k}$ such that $p\in {{\,\textrm{conv}\,}}{\{y_{\tau _{1}}^{\pi (1)},\dots ,y_{\tau _{k}}^{\pi (k)}\}}$ and $\bigcap _{i=1}^k A^{\pi (i)}_{\tau _{i}}\ne \emptyset$.

As in the case of the previous theorems, Theorem 1.7 is true also if all the sets $A^i_\tau$ are open. Note also that when $k=1$, P is just a point, and the theorem is trivial.

Let us discuss applications of Theorem 1.7. The first is a sparse colorful piercing theorem for hypergraphs of d -intervals. A d -interval is a union of d compact intervals in $\mathbb {R}$. A separated d -interval is a d-interval consisting d disjoint interval components $h^1,\dots ,h^d$ such that $h^{i+1}\subset (i,i+1)$ for $0\le i\le d-1$. A hypergraph of (separated) d -intervals is a hypergraph H whose vertex set is $\mathbb {R}$ and whose edge set is a finite family of (separated) d-intervals.

A matching in a hypergraph H is a set of pairwise disjoint edges. The matching number of H, which we denote as $\nu (H)$, is the maximum size of a matching. A cover of H is a set of vertices that intersects each edge of H, and the covering number (or piercing number) of H, $\tau (H)$, is the minimum size of a cover.

Tardos [19] and Kaiser [8] proved the following result on the ratio between the covering and matching numbers in hypergraphs of d-intervals.

Theorem 1.8

In any hypergraph of d-intervals H we have $\tau (H)\le ({d^2-d+1})\nu (H)$. If H is a hypergraph of separated d-intervals, then $\tau (H)\le (d^2-d)\nu (H)$.

Matoušek [11] constructed examples of hypergraphs of d-intervals H such that $\tau (H)=\Omega (d^2\nu (H)/{\log d})$, showing that the bounds from Theorem 1.8 are not far from optimal. Aharoni et al. [2] gave an alternative proof of Theorem 1.8 using the KKMS theorem and Theorem 1.3. Frick and Zerbib [4] applied Theorem 1.4 in a similar way to prove a colorful generalization of Theorem 1.8. In the following, a colorful matching $\mathcal {M}$ in a collection of families of edges $(\mathcal {F}_1,\dots ,\mathcal {F}_k)$ in a hypergraph H is a matching in H in which $|\mathcal {M}\cap \mathcal {F}_i|\le 1$ for every $i\in [k]$.

Theorem 1.9

(Frick–Zerbib [4])   Let k, d be positive integers.

• For $i\in [k]$, let $\mathcal {F}_i$ be a hypergraph of d-intervals. If $\tau (\mathcal {F}_i)\ge k$ for every $i\in [k]$, then there exists a colorful matching $\mathcal {M}$ of $(\mathcal {F}_1,\dots ,\mathcal {F}_k)$ of size $|\mathcal {M}|\ge k/(d^2-d+1)$.

• Let $d\ge 2$. For $i\in [(k-1)d+1]$, let $\mathcal {F}_i$ be a hypergraph of separated d-intervals. If $\tau (\mathcal {F}_i)\ge (k-1)d+1$ for every $i\in [k]$, then there exists a colorful matching $\mathcal {M}$ of $(\mathcal {F}_1,\dots ,\mathcal {F}_{(k-1)d+1})$ of size $|\mathcal {M}|\ge k/(d-1)$.

Here we use Theorem 1.7 to obtain a “sparse colorful” generalization of Theorem 1.9.

Theorem 1.10

Let n, k, m, d be positive integers.

• Let $n\ge k$, and for every $i\in [n]$, let $\mathcal {F}_i$ be a hypergraph of d-intervals. If $\tau \bigl (\bigcup _{i\in I}\mathcal {F}_i\bigr )\ge k$ for every $I\in \left( {\begin{array}{c}[n]\\ n-k+1\end{array}}\right)$, then there exists a colorful matching $\mathcal {M}$ of $(\mathcal {F}_1,\dots ,\mathcal {F}_n)$ of size $|\mathcal {M}|\ge {k}/(d^2-d+1)$.

• Let $n\ge (m-1)d+1$, $d\ge 2$, and for every $i\in [n]$, let $\mathcal {F}_i$ be a hypergraph of separated d-intervals. Suppose $\tau \bigl (\bigcup _{i\in I} \mathcal {F}_i\bigr )\ge (m-1)d+1$ for every $I\in \left( {\begin{array}{c}[n]\\ n-(m-1)d\end{array}}\right)$. Then there exists a colorful matching $\mathcal {M}$ of $(\mathcal {F}_1,\dots ,\mathcal {F}_n)$ of size $|\mathcal {M}|\ge m/(d-1)$.

Another application of Theorem 1.7 is to fair division of multiple cakes. Suppose that there are n participants (players) at a party where d cakes (which we identify with d copies of the [0, 1] interval) are served. Given any partition of cakes into m interval pieces each, every player can choose one of their favorite d-tuple of pieces (a d-tuple of pieces contains one piece from each cake). It is possible that there are multiple d-tuples of pieces that a player will prefer as their favorite, i.e., they like these pieces equally. The goal is to find such a partition and a distribution of the resulting pieces to the players so that every member in a large subset of players receives one of their favorite d-tuple of pieces.

The only condition on the preferences of the players that we require is the following (m, d)-hungry condition. We say that the set of players are (m, d)-hungry if the following two conditions hold:

• 1. Given any partition of the d cakes into m interval pieces each, and given any set I of $n-d(m-1)$ players, there is a player in I that prefers some d-tuple of non-empty pieces as their favorite.

• 2. The preference sets of the players are closed: if a player prefers some d-tuple of pieces in a converging sequence of partitions, they prefer the same d-tuple also in the limit partition.

Soberón [16] used Theorem 1.5 to prove the following generalization of the classical fair division theorem due to Stromquist [18] and Woodall [20].

Theorem 1.11

(Soberón [16])   Let $n\ge k$, and assume that n players are (k, 1) hungry. Then there exists a partition of a single cake into k interval pieces where k players get their favorite piece.

Here we give an extension of this theorem to fair division of multiple cakes. Our theorem is also a generalization of Theorem 2.1 in [12].

Theorem 1.12

Let n, m, d be positive integers such that $n\ge d(m-1)+1$ and $d\ge 2$. Assume that n players are (m, d)-hungry. Then, there exists a partition of the d cakes into m interval pieces each, and an allocation of d-tuples of pieces to a subset P of players of size at least $m/(d-1)$, such that each player in P receives one of their favorite d-tuple of pieces.

A third application of Theorem 1.7 concerns a generalization of the colorful Carathéodory theorem [3]. The following sparse colorful version of the colorful Carathéodory theorem was proven in a stronger form in [7] and [15].

Theorem 1.13

(Holmsen [7], Soberón [15])   Let k be a positive integer and $n\ge k$. If $X_1,\dots , X_n$ are finite subsets of ${\mathbb {R}}^{k-1}$ and for each $I\in \left( {\begin{array}{c}[n]\\ n-k+1\end{array}}\right)$, $0\in {{\,\textrm{conv}\,}}\bigl (\bigcup _{i\in I}X_i\bigr )$, then there exist indices $i_1,\dots ,i_k$ and points $x_j\in X_{i_j}$ such that $0\in {{\,\textrm{conv}\,}}{\{x_1,\dots ,x_k\}}$.

In [4], Theorem 1.4 was used to give a new proof of the colorful Carathéodory theorem. Using a similar approach, Theorem 1.7 can be used to give another proof of Theorem 1.13. The proof is essentially the same as the proof in [4], so we omit it.

The paper is organized as follows. Section 2 contains some preliminaries. In Sect. 3 we prove a theorem concerning the existence of certain triangulations that are needed for the proof of Theorem 1.7, and then in Sect. 4 we prove Theorem 1.7. Finally, in Sect. 5 we prove Theorems 1.10 and 1.12.

2 Preliminaries

All the triangulations considered in this paper are convex, that is, every face is the convex hull of its vertices. In order to prove Theorem 1.7, we first need a vertex labelling version of Theorem 1.3. Let P be a polytope and T a triangulation of P. For $v\in P$ denote by ${{\,\textrm{supp}\,}}(v)$ the support of v, that is, the minimal face of P containing v. A Sperner–Shapley labelling of T is an assignment $\lambda :V(T) \rightarrow F(P)$ such that $\lambda (v)\subset {{\,\textrm{supp}\,}}(v)$ for every $v\in V(T)$.

The following was essentially proved in [4], and we give the proof here for completeness.

Theorem 2.1

Let $P\subset \mathbb {R}^d$ be a polytope with $p\in P$, and let T be a triangulation of P. Let $\lambda :V(T) \rightarrow F(P)$ be a Sperner–Shapley labeling of T. Suppose that for every $v\in V(T)$, a point $y(v)\in \lambda (v)$ is assigned. Then there is a face $\tau$ of T such that $p\in {{\,\textrm{conv}\,}}{\{y(v)\,|\,v\in V(\tau )\}}$.

Proof

By the Sperner–Shapley labeling condition we have $y(v)\in \lambda (v) \subset {{\,\textrm{supp}\,}}(v)$. Extending y linearly onto faces of T defines a continuous map $Y:P\rightarrow P$, so that $Y(\sigma )\subset \sigma$ for every face $\sigma$ of P. This implies that Y is homotopic to the identity on $\partial P$, and thus $Y|_{\partial P}$ has degree one. Then Y is surjective and we can find a point $x\in P$ such that $Y(x)=p$. Let $\tau$ be a face of T containing x. By the definition of Y, we have $p\in Y(\tau )={{\,\textrm{conv}\,}}{\{y(v)\,|\,v\in V(\tau )\}}$. $\square$

We will use the following simple lemma frequently.

Lemma 2.2

Let $n\ge k\ge 2$ be integers, and let P be a $(k-1)$-dimensional polytope. Suppose the family $(A^i_\tau \,|\,i\in [n],\,\tau \in F(P))$ is a k-weakly Komiya cover of P. Let $v\in P$ and $I\subset [n]$. If $|I|\ge n-k+1$ then there exists $i\in I$ and $\tau \subset {{\,\textrm{supp}\,}}(v)$ such that $v\in A^i_\tau$.

Proof

Let J be a subset of I of size $n-k+1$. Since the sets $A^i_\sigma$ form a k-weakly Komiya cover of P, the family $\bigl (\bigcup _{j\in J}A^j_\sigma \mid \sigma \in F(P)\bigr )$ forms a Komiya cover of P. Therefore, $v\in {{\,\textrm{supp}\,}}(v) \subset \bigcup _{\tau \subset {{\,\textrm{supp}\,}}(v)}\bigcup _{i\in J} A^i_\tau$. Hence there is some $\tau \subset {{\,\textrm{supp}\,}}(v)$ and $i\in J$ such that $v\in A^i_\tau$. $\square$

3 Refining a Triangulation

Let X be a triangulation of P. Denote by E(X) the one-dimensional faces (or edges) of X. For an edge $v_1v_2 \in E(X)$, let $b(v_1,v_2)$ denote the barycenter of $v_1v_2$. For $m\ge 2$ we define $b(v_1,\dots ,v_{m+1})$ recursively by

$$\begin{aligned} b(v_1,\dots ,v_{m+1})=b(b(v_1,\dots ,v_{m}),v_{m+1}). \end{aligned}$$

Denote by $X(v_1,v_2)$ the triangulation refining X, so that

$$\begin{aligned} V(X(v_1,v_2)) = V(X) \cup \{b(v_1,v_2)\}, \end{aligned}$$

and $X(v_1,v_2)$ is obtained by replacing every face of the form ${{\,\textrm{conv}\,}}{\{v_1,v_2,\dots ,v_j\}}$ in X that contains the edge $v_1v_2$ with two faces ${{\,\textrm{conv}\,}}{\{b(v_1,v_2),v_2,\dots ,v_j\}}$ and ${{\,\textrm{conv}\,}}{\{b(v_1,v_2),v_1,v_3,\dots ,v_j\}}$. Given a map $f:V(X)\rightarrow [n]$, an edge $uv\in E(X)$ will be called bad if $f(u)=f(v)$. Let B(X) denote the set of bad edges of X, and for a vertex $v\in V(X)$ define

$$\begin{aligned} B(X; v) = \{u\in V(X) \mid uv \in B(X)\}. \end{aligned}$$

In this section we prove that given the conditions of Theorem 1.7, and given any triangulation T of P, there exists a triangulation $T'$ refining T and satisfying certain nice properties. A question that might be of interest is to find an effective bound on the number of steps in the algorithm described in the proof of Theorem 3.1.

Theorem 3.1

Let $n\ge k\ge 2$ be integers. Let P be a $(k-1)$-dimensional polytope with $p\in P$. Assume that for every $\tau \in F(P)$, we are given n points $y_\tau ^1,\dots ,y_\tau ^n\in \tau$, and the family $(A^i_\tau \,|\,i\in [n],\, \tau \in F(P))$ is a k-weakly Komiya cover of P. Let T be a convex triangulation of P. Then there exists a refinement $T'$ of T and maps $\lambda :V(T')\rightarrow F(P)$, $f:V(T')\rightarrow [n]$, and $y:V(T') \rightarrow P$ with the following properties:

• (P1) $v\in A^{f(v)}_{\lambda (v)}$ for every $v\in V(T')$,

• (P2) $y(v) = y_{\lambda (v)}^{f(v)} \in \lambda (v) \subset {{\,\textrm{supp}\,}}(v)$ for every $v\in V(T')$, and

• (P3) for every face $\tau$ of $T'$, the indices f(v), $v\in \tau$, are pairwise distinct.

Proof

Let $v\in V(T)$. By Lemma 2.2 we may choose an index $i \in [n]$ and a face $\tau \subset {{\,\textrm{supp}\,}}(v)$ such that $v\in A^i_\tau$. Let $\lambda (v)=\tau$, $f(v)=i$, and $y(v)=y_\tau ^i$.

Let $N=|B(T)|$ be the number of bad edges in T. Note that if $N=0$, then properties P1–P3 hold for T with the defined maps $\lambda ,f,y$, and we are done. So assume $N\ge 1$ and let $v_1v_2\in B(T)$.

We will now describe an algorithm that receives $T,\lambda ,f,y$ and terminates with a refinement $T'$ of T and assignments $\lambda (v) \in F(P)$, $f(v)\in [n]$, $y(v)\in Y$ for every $v\in V(T')\setminus V(T)$, with the following properties:

• (i) properties P1 and P2 hold for $T',\lambda ,f,y$,

• (ii) $B(T') \subset B(T)$, and

• (iii) $v_1v_2 \notin E(T')$.

Note that ii and iii imply that $B(T')<B(T)$, and thus the triangulation $T'$ has at most $N-1$ bad edges. This suffices to prove the theorem.

Throughout the algorithm, $T_c$ is being updated with finer and finer triangulations. The notation $T_c=T_c(b(v_1,\dots ,v_{j+1}),v_{j+2})$ in step 3. below means that we replace the current $T_c$ with the new refined triangulation $T_c(b(v_1,\dots ,v_{j+1}),v_{j+2})$, that we now call $T_c$. In the algorithm, we will construct sequences of points $v_1,\dots ,v_{j+2}$ and sets $Q_{j+1}=B(T_c;b(v_1,\dots ,v_{j+2}))$, which record the bad edges that were introduced in the current triangulation. The goal of the algorithm is to terminate at a triangulation in which $Q_j=\emptyset$ for all j.

3.1 The Algorithm

Setup: Set $T_c=T(v_1,v_2)$. Since $|[n]\setminus \{f(v_2)\}|\ge n-k+1$ (recall we take $k\ge 2$), by Lemma 2.2 there exists $i\in [n]\setminus \{f(v_2)\}$ and $\tau \in {{\,\textrm{supp}\,}}(b(v_1,v_2))$ such that $b(v_1,v_2)\in A^i_\tau$. Set $\lambda (b(v_1,v_2))=\tau$, $f(b(v_1,v_2))=i$, and $y(b(v_1,v_2))=y_\tau ^i$. Since $y_\tau ^i\in \tau \subset {{\,\textrm{supp}\,}}(v)$, properties P1 and P2 hold for $v=b(v_1,v_2)$. Set $Q_1=B(T_c;b(v_1,v_2))$ and $Q_j=\emptyset$ for all $j\ge 2$.

Apply the following procedure:

• 1. If $Q_j=\emptyset$ for all $j\ge 1$, stop and return $T_c, \lambda , f, y$. Otherwise,

• 2. let j be the largest index for which $Q_j\ne \emptyset$, and choose a vertex $v\in Q_j$. Set $v_{j+2}=v$, $T_c=T_c(b(v_1,\dots ,v_{j+1}),v_{j+2})$. Remove $v_{j+2}$ from $Q_j$.

• 3. Choose $i\in [n]\setminus \{f(v_2),f(v_3),\dots ,f(v_{j+2})\}$ and $\tau \subset {{\,\textrm{supp}\,}}(b(v_1,\dots ,v_{j+2}))$ such that $b(v_1,\dots ,v_{j+2})\in A^i_\tau$ (we will show that such a choice exists). Set $\lambda (b(v_1,\dots ,v_{j+2}))=\tau$, $f(b(v_1,\dots ,v_{j+2}))=i$, $y({b(v_1,\dots ,v_{j+2})})=y_{\tau }^i$. Like before, properties P1 and P2 hold for $v=b(v_1,\dots ,v_{j+2})$.

• 4. Set $Q_{j+1}=B(T_c;b(v_1,\dots ,v_{j+2})).$

• 5. Return to step 2

The idea of the algorithm is as follows. We want to eliminate the bad edge $v_1v_2$ of T by subdividing it using the new vertex $b(v_1,v_2)$ and refining T to obtain $T(v_1,v_2)$. However, after assigning $f(b(v_1,v_2))$, the current triangulation $T(v_1,v_2)$ may contain bad edges that did not appear in T. Every such a bad edge must contain the vertex $b(v_1,v_2)$. So we let $Q_1$ record the vertices v for which $vb(v_1,v_2)$ is a bad edge; these are precisely the bad edges of $T(v_1,v_2)$ that are not bad in T. More generally, throughout the algorithm $Q_j$ records the vertices v of the current triangulation $T_c$ such that $vb(v_1,\dots ,v_{j+1})$ is a bad edge of $T_c$. At every iteration of the algorithm, every bad edge of $T_c$ that is not bad in T is of the form $vb(v_1,\dots ,v_{j+1})$, for some $j\ge 1$. Thus, if the algorithm terminates, i.e., $Q_j=\emptyset$ for all j, then the returning triangulation $T_c$ contains only bad edges that were already bad in T. Moreover, $T_c$ does not contain the edge $v_1v_2$, which was bad in T. Thus, $T_c$ contains at least one less bad edge than T.

The algorithm works in a depth-first manner. We find the largest index j such that $Q_j\ne \emptyset$ and we reduce the size of $Q_j$ by subdividing an edge of the form $vb(v_1,\dots ,v_{j+1})$. By doing this we may have $Q_{j+1}\ne \emptyset$ in step 5 The algorithm continues to run until $Q_{j+1}=\emptyset$ (we will show that this always happens), and then we reduce the size of $Q_j$ by subdividing another edge of the form $vb(v_1,\dots ,v_{j+1})$. Similarly, we continue until $Q_{j}=\emptyset$, and then we reduce the size of $Q_{j-1}$ by subdividing an edge of the form $vb(v_1,\dots ,v_{j})$ (see Example 3.10).

Our goal now is to show that: (a) the choice in step 4 of the algorithm is possible as long as the algorithm runs, (b) the algorithm stops after finitely many steps, and (c) the returning triangulation satisfies properties i–iii. This will imply the theorem.

Claim 3.2

For every $2\le j\le k$, each maximal simplex of $T_c$ containing the vertex $b(v_1,\dots ,v_{j})$ is of the form

$$\begin{aligned} {{\,\textrm{conv}\,}}{\{b(v_1,\dots ,v_{j}), w_2, \dots , w_{j},u_{j+1},\dots ,u_k\}}, \end{aligned}$$

where

• $w_2\in \{v_1, v_2\}$,

• $w_i \in \{v_i, b(v_1,\dots ,v_{i-1})\}$ for every $3\le i\le j$, and

• $u_{j+1},\dots ,u_k$ are some vertices in $V(T_c)$.

Proof

We proceed by induction on j. For $j=2$ the claim is true. Indeed, in the triangulation $T(v_1,v_2)$ each maximal simplex containing $b(v_1,v_2)$ contains $v_1$ or $v_2$. Since $f(b(v_1,v_2))\ne f(v_1), f(v_2)$, the edges $v_1b(v_1,v_2)$ or $v_2b(v_1,v_2)$ are never subdivided at any iteration in the algorithm, so in each triangulation obtained at any iteration of the algorithm, any maximal simplex containing $b(v_1,v_2)$ will still contain $v_1$ or $v_2$. Let $3\le j\le k$, and assume the claim is true for $j-1$.

We first claim that $v_{j}$ is not one of the vertices $v_1,\dots ,v_{j-1}$ or $b(v_1,\dots ,v_{i})$ for $2\le i\le j-1$. This is true because at some iteration in the algorithm, $v_j\in B(b(v_1,\dots ,v_{j-1}))$ and thus $v_jb(v_1,\dots ,v_{j-1})$ is a bad edge (and in particular $v_j\ne b(v_1,\dots ,v_{j-1})$), and $ub(v_1,\dots ,v_{j-1})$ is not a bad edge if u is one of the vertices $v_1,\dots ,v_{j-1}$ or $b(v_1,\dots ,v_{i})$ for $2\le i\le j-2$; indeed, we have that $f(v_1)=f(v_2)$ and $f(v_{i+1})=f(b(v_1,\dots ,v_{i}))$ for $2\le i\le j-2$, and by the choice of $f(b(v_1,\dots ,v_{i}))$ made in step  4, $f(b(v_1,\dots ,v_{i}))\in [n]\setminus \{f(v_2),f(v_3),\dots ,f(v_i)\}$.

By the inductive hypothesis, the maximal simplices of $T_c$ containing the edge $v_{j}b(v_1,\dots ,v_{j-1})$ are of the form

$$\begin{aligned} {{\,\textrm{conv}\,}}{\{b(v_1,\dots ,v_{j-1}), w_2, \dots , w_{j-1},v_{j},u_{j+1},\dots ,u_k\}}, \end{aligned}$$

where $w_2\in \{v_1, v_2\}$ and for $3\le i\le j$, $w_i$ is equal to $v_i$ or $b(v_1,\dots ,v_{i-1})$. Therefore, the maximal simplices of $T_c$ containing $b(v_1,\dots ,v_{j})$ are of the form

$$\begin{aligned} {{\,\textrm{conv}\,}}{\{b(v_1,\dots ,v_{j}),w_2,\dots , w_{j},u_{j+1},\dots ,u_k\}}, \end{aligned}$$

where $w_2\in \{v_1, v_2\}$ and for $3\le i\le j$, $w_i$ is equal to $v_i$ or $b(v_1,\dots ,v_{i-1})$. This completes the proof of the claim. $\square$

Applying the claim for $j=k$ we get

Claim 3.3

Assume that at some iteration of the algorithm, at step 3 we have $Q_{k-2}\ne \emptyset$ and $k-2$ is the largest index j for which $Q_j\ne \emptyset$. Then in the current triangulation $T_c$, the vertex $b(v_1,\dots ,v_k)$ is connected by an edge only to the vertices $v_1,\dots ,v_k$ and $b(v_1,\dots ,v_{i-1})$ for $3\le i\le k$.

Claim 3.4

At any iteration of the algorithm, $Q_{j}=\emptyset$ for every $j\ge k-1$. In other words, the index j from step 3 is always at most $k-2$.

Proof

We first prove that $Q_{k-1}=\emptyset$ at every iteration. Assume that $v_k$ has been defined in some iteration of the algorithm in step 3, and let $T_c$ be the resulting triangulation defined in the same step. By Claim , $b(v_1,\dots ,v_k)$ is connected by an edge only to the vertices $v_1,\dots ,v_k$ and $b(v_1,\dots ,v_{j})$ for $2\le j\le k-1$ in $T_c$. By the choice of $f(b(v_1,\dots ,v_k))$ from step 4, we have

$$\begin{aligned} f(b(v_1,\dots ,v_k))\in [n]\setminus \{f(v_2),f(v_3),\dots ,f(v_k)\}. \end{aligned}$$

Moreover, $f(v_1)=f(v_2)$ and by the setup in step 3, $f(b(v_1,\dots ,v_{i}))=f(v_{i+1})$ for every $2\le i \le k-1$. Therefore, $f(b(v_1,\dots ,v_k))\ne f(v)$ for every vertex v that is connected to $b(v_1,\dots ,v_k)$ by an edge in $T_c$. It follows that $Q_{k-1}=\emptyset$. Now, since $Q_{j+1}$ is being changed in step 5 only if $Q_j\ne \emptyset$ at step 3 in some iteration of the algorithm, it follows that $Q_j= \emptyset$ for every $j\ge k$ as well. $\square$

Claim 3.5

The choice of $i,\tau$ in step 4 of the algorithm is possible as long as the algorithm runs.

Proof

By Claim 3.4, at any iteration of the algorithm $j\le k-2$, and thus the set $I=[n]\setminus \{f(v_2),f(v_3),\dots ,f(v_{j+2})\}$ is of size at least $n-k+1$. Therefore, by Lemma 2.2 there exists a choice of $i\in I$ and $\tau \in {{\,\textrm{supp}\,}}(b(v_1\dots ,v_{j+2}))$ such that $b(v_1\dots ,v_{j+2})\in A^i_\tau$, as needed in step 4 $\square$

Claim 3.6

For any $j\ge 1$, at any iteration of the algorithm, either $Q_j=\emptyset$ or there is a later iteration in the algorithm for which $Q_j =\emptyset$ and the size of $Q_{i}$ for each $1\le i\le j-1$ is the same in both iterations.

Proof

We proceed by induction on $k-1-j$. If $k-1-j\le 0$, then the statement is true by Claim 3.4. Let $1\le j\le k-2$. Assume that in the $i_1$-th iteration in the algorithm, we have $Q_j\ne \emptyset$. It suffices to show that there is some later iteration for which the size of $Q_j$ is decreased by 1 and the size of $Q_i$ for $1\le i\le j-1$ remains unchanged. By the induction hypothesis, there exists $i_2\ge i_1$ such that in the $i_2$-th iteration of the algorithm, $Q_{j+1}=\emptyset$ and the size of $Q_i$ for each $1\le i\le j$ is the same as in the $i_1$-th iteration. Similarly, we may find $i_3\ge i_2$ such that in the $i_3$-th iteration of the algorithm, $Q_{j+2}=\emptyset$ and the size of $Q_i$, for every $1\le i\le j+1$, is the same as in the $i_2$-th iteration (and in particular, $Q_{j+1}=\emptyset$). Continuing in this way, we find some $i_{k-1-j}\ge i_1$ such that in the $i_{k-1-j}$-th iteration of the algorithm, $Q_i=\emptyset$ for all $j+1\le i\le k-2$ and the size of $Q_i$ for $1\le i\le j$ is the same as in the $i_1$-th iteration. It follows by Claim 3.4 that j is the largest index for which $Q_j\ne \emptyset$. Therefore, in step 3 of the $i_{k-1-j}+1$-th iteration, we choose some $v\in Q_j$ and set $Q_j=Q_j\setminus \{v\}$, so the size of $Q_j$ decreases by 1, and the size of $Q_i$ for $1\le i\le j-1$ is unchanged. $\square$

Claim 3.7

If at some iteration of the algorithm $Q_i=\emptyset$ for every $1\le i\le j$, then $Q_j=\emptyset$ in every later iteration of the algorithm.

Proof

If $Q_i=\emptyset$ for every $1\le i\le j$, then at the next iteration of the algorithm, the index chosen in step 3 is at least $j+1$. Therefore, it is still the case that $Q_i=\emptyset$ for each $1\le i\le j$ in the next iteration. $\square$

Claim 3.8

At any iteration of the algorithm, every edge of $B(T_c)\setminus B(T)$ is of the form $vb(v_1,\dots ,v_j)$, where $v\in Q_{j-1}$ and $v_j$ has been defined in some iteration of algorithm.

Proof

We proceed by induction on the number of iterations. The claim is true in the 0-iteration, when $T_c=T(v_1,v_2)$ in the setup. Let $T'$ be the triangulation $T_c$ obtained at the i-th iteration of the algorithm for some i, and assume the statement holds for $T'$. Let $T''$ be the triangulation obtained in the $(i+1)$-th iteration. Let j be the index in step 3 of the $(i+1)$-th iteration. Then every bad edge of $E(T'')\setminus E(T')$ is of the form $vb(v_1,\dots ,v_{j+2})$, for $v\in Q_{j+1}$. This, combined with the fact that the claim held for $T'$, implies that the claim holds for $T''$. $\square$

Claim 3.9

The algorithm terminates after finitely many steps. The returning triangulation $T'$ satisfies properties , ii, and iii.

Proof

Applying Claim 3.6 for $j=1$, we have that there is some iteration for which $Q_1=\emptyset$. Therefore, by Claim 3.7, we have that $Q_1=\emptyset$ at any later iteration of the algorithm. Now, by Claim 3.6, there is a later iteration in the algorithm for which $Q_1=Q_2=\emptyset$. Applying Claim 3.7 again, we have that $Q_2=\emptyset$ for every later iteration. Continuing this way, we get that there is an iteration where $Q_j=\emptyset$ for every $j\ge 1$, and therefore the algorithm terminates.

By Claim 3.8, every edge in $B(T')\setminus B(T)$ is of the form $vb(v_1,\dots ,v_{j+1})$ where $v\in Q_{j}$. When the algorithm terminates, we have that $Q_j=\emptyset$ for all $j\ge 1$, so $T'$ has no such bad edges. Since $T'$ no longer has the edge $v_1v_2$, it follows that $T'$ has at most $N-1$ bad edges. Finally, i holds by the the definition of $\lambda , f, y$ throughout the algorithm. $\square$

Claim 3.9 completes the proof of Theorem 3.1. $\square$

Example 3.10

Let P be a 2-dimensional simplex and $n=4$. Assume we have closed sets $(A^i_\sigma \,|\,i\in [4],\,\sigma \in F(P))$ satisfying the conditions of Theorem 1.7. Let T be the triangulation of P depicted in Fig. 1A. Suppose that a map $f:V(T)\rightarrow [4]$ is defined. Every vertex $v\in V(T)$ in the figure is labeled by v, f(v). Then $u_1u_2$ is a bad edge.

We now apply the algorithm with $v_1=u_1$ and $v_2=u_2$. In the setup of the algorithm we obtain $T_c=T(u_1,u_2)$, and assign $f(b(v_1,v_2))\in [4]\setminus \{1\}$. Say $f(b(v_1,v_2))=2$. We then obtain the triangulation in Fig. 1B.

Proceeding to step 2 in the algorithm, we find that $Q_1=\{u_3,u_4\}$ is non-empty, and in step 3, the largest index j such that $Q_j\ne \emptyset$ is $j=1$. We choose $v_3=u_4$, $T_c=T_c(b(v_1,v_2),v_3)$, and remove $v_3$ from $Q_1$, so now $Q_1=\{u_3\}$. Proceeding now to step 4, we find some $i\in [4]\setminus \{f(v_2)=1,f(v_3)=2\}$ and $\sigma \subset {{\,\textrm{supp}\,}}(b(v_1,v_2,v_3))$ such that $b(v_1,v_2,v_3)\in A^i_\sigma$, and set $f(b(v_1,v_2,v_3))=i$. Say $i=3$. We obtain the triangulation in Fig. 1C. In step 5 we find $Q_2=B(T_c, b(u_1,u_2,u_4)) = \emptyset$.

We go back to step 2 and begin the second iteration of the algorithm. Since $Q_1\ne \emptyset$, we move to step 3. Here $j=1$ is again the largest index for which $Q_j\ne \emptyset$. We set $v_3=u_3$, $T_c=T_c(b(v_1,v_2),v_3)$, and $Q_1=Q_1\setminus \{v_3\}=\emptyset$. In step 4, we find some $i\in [4]\setminus \{f(v_2)=1,f(v_3)=2\}$ and $\sigma \subset {{\,\textrm{supp}\,}}(b(v_1,v_2,v_3))$ such that $b(v_1,v_2,v_3)\in A^i_\sigma$. We set $f(b(v_1,v_2,v_3))=i$. Say $i=4$. We obtain the triangulation $T_c$ in Fig. 1D. In step 5, $Q_2=\emptyset$.

Now we go back to step 2. The algorithm terminates since $Q_j=\emptyset$ for all j. In the returning triangulation $T'$ every bad edge was bad already in the triangulation T we started with. Moreover, the edge $u_1u_2$ that was bad in T, is not an edge anymore in $T'$.

Fig. 1

The algorithm applied to a triangulation of a 2-simplex in Example 3.10

4 Proof of Theorem 1.7

The proof follows from Theorem 3.1 using an argument similar to the one used to prove [4, Thm. 2.1]. By Theorem 3.1, for every $\varepsilon >0$ there exists a triangulation $T_\varepsilon$ of P with diameter at most $\varepsilon$ and assignments $\lambda (v),f(v),y(v)$, such that the following properties hold:

• (i) for every $v\in V(T_\varepsilon )$ we have $v\in A_{\lambda (v)}^{f(v)}$ and $y(v)=y_{\lambda (v)}^{f(v)}$,

• (ii) $\lambda (v)\subset {{\,\textrm{supp}\,}}(v)$, and

• (iii) for every face $\tau$ of $T_\epsilon$, the indices $(f(u)\,|\,u\in V(\tau ))$ are pairwise distinct.

By Theorem 2.1 there is a face $\sigma ={{\,\textrm{conv}\,}}{\{u_1,\dots ,u_k\}}$ in $T_\varepsilon$ (of dimension $k-1$, without loss of generality) such that $p\in {{\,\textrm{conv}\,}}{\{y(u)\,|\,u\in V(\sigma )\}}$. This implies that for $\tau _i=\lambda (u_i)$ and $j_i=f(u_i)$, we have $p\in {{\,\textrm{conv}\,}}{\{y_{\tau _i}^{j_i}\,|\,1\le i\le k\}}$. Moreover, since $u_i \in A_{\tau _i}^{j_i}$ and the diameter of $\sigma$ is at most $\varepsilon$, the $\varepsilon$-neighborhoods of $A_{\tau _1}^{j_1},\dots , A_{\tau _k}^{j_k}$ intersect. Let $\pi _\varepsilon (i):[k]\rightarrow [n]$ be the function $i\mapsto j_i$. The function $\pi _\varepsilon (i)$ is indeed an injection as Theorem 1.7 ensures that the values $f(u_i)=j_i$ are pairwise distinct since the $u_i$ are the vertices of a face in $T_\epsilon$. Now, taking $\varepsilon$ to 0 and using the compactness of P and the fact that the sets $A_{\tau }^{i}$ are closed, we conclude the theorem.

5 Applications: Proofs of Theorems 1.10 and 1.12

The proof of Theorem 1.10 is very similar to the proof of Theorem 1.9, where the role of Theorem 1.4 is replaced by Theorem 1.7.

A fractional matching in a hypergraph $H=(V,E)$ is a function $f:E \rightarrow \mathbb {R}_{\ge 0}$ satisfying $\sum _{e:e\ni v} f(e)\le 1$ for all ${v\in V}$. The fractional matching number $\nu ^*(H)$ is the maximum of $\sum _{e\in E} f(e)$ over all fractional matchings f of H. A perfect fractional matching in H is a fractional matching f in which $\sum _{e:v\in e} f(e) = 1$ for every $v\in V$. The rank of a hypergraph $H=(V,E)$ is the maximal size of an edge in H. A hypergraph H is d-partite if there exists a partition $V_1,\dots , V_d$ of V such that $|e\cap V_i| =1$ for every $e\in E$ and $i\in [d]$.

For the proof of Theorem 1.10 we will use a theorem by Füredi [5].

Theorem 5.1

If H is a hypergraph of rank $d\ge 2$, then

$$\begin{aligned} \nu (H) \ge \frac{\nu ^*(H)}{d-1+{1}/{d}}. \end{aligned}$$

If H is d-partite, then $\nu (H) \ge {\nu ^*(H)}/(d-1)$.

We will also need the following simple lemma (see e.g. [4]).

Lemma 5.2

If a hypergraph $H=(V,E)$ of rank d has a perfect fractional matching, then $\nu ^*(H)\ge {|V|}/{d}$.

Proof of Theorem 1.10

Since $\mathcal {F}=\bigcup _{i=1}^n\mathcal {F}_i$ is finite, by rescaling $\mathbb {R}$ we may assume that each member of $\mathcal {F}$ is a subset of (0, 1). We will use the points of $\Delta ^{k-1}$ to represent $k-1$ points on the interval [0, 1]. Then we will define an appropriate family of subsets of $\Delta ^{k-1}$ that satisfy the hypothesis of Theorem 1.7, and the conclusion of the theorem will provide our result.

For a point $x=(x_1,\dots ,x_k)\in \Delta ^{k-1}$, let $p_x(j)=\sum _{i=1}^j x_i \in [0,1]$. Every face of $\Delta ^{k-1}$ is of the form $\Delta ^T={{\,\textrm{conv}\,}}{\{e_j\,|\,j\in T\}}$ for some $T\subset [k]$, where $e_j$ is the vertex of $\Delta ^{k-1}$ having 1 at the j-component and 0 otherwise.

For every $T\subset [k]$, let $A^i_T$ be the set consisting of all $x \in \Delta ^{k-1}$ for which there exists a d-interval $f \in \mathcal {F}_i$ satisfying

• $f\subset \bigcup _{j\in T} (p_{x}({j-1}),p_{x}({j}))$, and

• $f \cap (p_{x}({j-1}),p_{x}({j})) \ne \emptyset$ for each $j\in T$.

Note that $A^i_T =\emptyset$ whenever $|T| > d$, and that the sets $A^i_{T}$ are open.

Let $I\in {[n]\atopwithdelims ()n-k+1}$. The assumption $\tau \bigl (\bigcup _{i\in I}\mathcal {F}_i\bigr )\ge k$ implies that for every $x=(x_1,\dots ,x_{k})\in \Delta ^{k-1}$, the set $P(x)=\{p_{x}({j}):j\in [k-1]\}$ is not a cover of $\bigcup _{i\in I}\mathcal {F}_i$, meaning that there exists $i\in I$ and $f\in \mathcal {F}_i$ not containing any $p_{x}(j)$. This, in turn, means that $x\in A^i_{T}$ for some $T\subset [k]$. Thus the sets $(A^i_T\,|\,i\in I,\,T\subset [k])$ form a cover of $\Delta ^{k-1}$. We will show that $\bigl (\bigcup _{i\in I}A^i_{T}\mid T\subset [k]\bigr )$ is a Komiya cover, and since $I\in {[n]\atopwithdelims ()n-k+1}$ was chosen arbitrarily, this will imply that $(A^i_{T}\,|\,i\in [n],\,T\subset [k])$ is a k-weakly Komiya cover. Let $\Delta ^S$ be a face of $\Delta ^{k-1}$ for some $S\subset [k]$. If $x\in \Delta ^S$ then $(p_{x}({j-1}),p_{x}({j}))=\emptyset$ for $j \notin S$, and hence it is impossible to have ${f \cap (p_{x}({j-1}),p_{x}({j}))\ne \emptyset }$. Thus $x \in A^i_{T}$ for some $T \subseteq S$. This proves that $\Delta ^S \subseteq \bigcup _{T\subseteq S} \bigcup _{i\in I} A^i_{T}$, and thus $\bigl (\bigcup _{i\in I} A^i_{T} \mid T\subset [k]\bigr )$ is a Komiya cover, for every $I\in {[n] \atopwithdelims ()n-k+1}$.

By Theorem 1.7 there is an injection $\pi :[k]\rightarrow [n]$ and faces $\Delta ^{T_1},\dots ,\Delta ^{T_k}$ of $\Delta ^{k-1}$ such that

• (i) $b(\Delta ^{k-1}) \in {{\,\textrm{conv}\,}}{\{b(\Delta ^{T_1}),\dots ,b(\Delta ^{T_k})\}}$, and

• (ii) $\bigcap _{i=1}^k A^{\pi (i)}_{T_{i}}\ne \emptyset$.

(Here we are using b(P) with P a polytope to denote the barycenter of P.) Note that c1 implies that the hypergraph $H=([k],\{T_{1},\dots ,T_{k}\})$ has a perfect fractional matching, and c2 implies that $|T_i|\le d$ for all $i \in [k]$. Then by Lemma 5.2, $\nu ^*(H)\ge k/d$. Therefore, by Theorem 5.1,

$$\begin{aligned} \nu (H) \ge \frac{\nu ^*(H)}{d-1+1/d}\ge \frac{k}{d^2-d+1}. \end{aligned}$$

Let M be a matching in H of size $m \ge {k}/({d^2-d+1})$. Let $x \in \bigcap _{i=1}^{k} A^{\pi (i)}_{T_i}$. For every $i\in [k]$ let $f_i$ be the d-interval of $\mathcal {F}_{\pi (i)}$ witnessing the fact that $x \in A^{\pi (i)}_{T_i}$. Then the set $\mathcal {M}=\{f_i\,|\,T_i \in M\}$ is a colorful matching of size m in $\mathcal {F}$. This proves the first assertion of the theorem.

Now suppose that $\mathcal {F}_i$ is a hypergraph of separated d-intervals for all $i\in [n]$. For $f\in \mathcal {F}$ let $f^t \subset (t-1,t)$ be the t-th interval component of f. We can assume without loss of generality that $f^t$ is nonempty. Let $P=(\Delta ^{m-1})^d$. Then $\dim P = (m-1)d$. For a d-tuple $T=(j_i,\dots ,j_d) \in [m]^d$ (note that T corresponds to the vertex $v_T=e_{j_1}\times e_{j_2}\times \cdots \times e_{j_d}$ of P) let $A^i_T$ consist of all $x=x^1\times \cdots \times x^d \in P$ for which there exists $f\in \mathcal {F}_i$ satisfying $f^t\subset (t-1+p_{x^t}({j_t-1}),t-1+p_{x^t}({j_t}))$ for all $t\in [d]$.

Let $I\in {[n] \atopwithdelims ()n-d(m-1)}$. Since $\tau \bigl (\bigcup _{i\in I} \mathcal {F}_{i}\bigr ) \ge d(m-1)+1$, the set of points

$$\begin{aligned} \{t-1+p_{x^t}(j)\mid t\in [d], \,j\in [m-1]\} \end{aligned}$$

does not form a cover of $\bigcup _{i\in I} \mathcal {F}_{i}$. Therefore, by the same argument as before, the sets $(A^i_{T}\,|\,i\in [n], T\in [m]^d)$ are open and form a $(d(m-1)+1)$-weakly Komiya cover of P. Applying Theorem 1.7 with $k=d(m-1)+1$, we conclude that there exists an injection $\pi :[d(m-1)+1]\rightarrow [n]$ and d-tuples $T_1,\dots ,T_{d(m-1)+1}$ in $[m]^d$ such that

• (i) $b(P) = {{\,\textrm{conv}\,}}{\{v_{T_1},\dots ,v_{T_k}\}}$, and

• (ii) $\bigcap _{i\in [(m-1)d+1]} A^{\pi (i)}_{T_i} \ne \emptyset$.

Observe that w1 implies that the d-partite hypergraph

$$\begin{aligned} ([m]\times [d] ,\{T_1,\dots ,T_{d(m-1)+1} \}) \end{aligned}$$

(where an edge $T_i$ contains a vertex (i, j) if $T_i$ has i as its j-th entry) has a perfect fractional matching. Hence by Lemma 5.2 we have $\nu ^*(H) \ge md/d =m$. By Theorem 5.1, this implies $\nu (H) \ge {\nu ^*(H)}/(d-1)\ge m/(d-1)$. Now, by the same argument as before, by taking $x \in \bigcap _{i\in [(m-1)d+1]} A^{\pi (i)}_{T_i}$ we obtain a colorful matching in $\mathcal {F}$ of the same size, concluding the proof of the theorem. $\square$

Proof of Theorem 1.12

Given d cakes, the set of all possible partitions of the cakes in m interval pieces is modeled by the polytope $P=(\Delta ^{m-1})^d$ of dimension $(m-1)d$ (see e.g. [1, 12]). For a d-tuple $T=(j_i,\dots ,j_d) \in [m]^d$ define

$$\begin{aligned} A^i_T=\{x=x^1\times \cdots \times x^d \in P \mid \text {player}~ i~ \text {prefers the}~ d~\text {-tuple of pieces}~{T}\}. \end{aligned}$$

The fact that the players are (m, d) hungry implies that the sets $(A^i_T \,|\,i\in [n],\, T\in [m]^d)$ form a $(d(m-1)+1)$-weakly Komiya cover of P. Applying Theorem 1.7 with $k=d(m-1)+1$ as in the previous proof, we conclude that there exists an injection $\pi :[d(m-1)+1]\rightarrow [n]$ and d-tuples $T_1,\dots ,T_{d(m-1)+1}$ in $[m]^d$ such that

• (i) $b(P) = {{\,\textrm{conv}\,}}{\{v_{T_1},\dots ,v_{T_k}\}}$, and

• (ii) $\bigcap _{i\in [(m-1)d+1]} A^{\pi (i)}_{T_i} \ne \emptyset$.

Like before, u1 implies that the d-partite hypergraph

$$\begin{aligned} H=([m]\times [d] ,\{T_1,\dots ,T_{d(m-1)+1} \}) \end{aligned}$$

has a perfect fractional matching. Hence by Lemma 5.2 we have $\nu ^*(H) \ge md/d =m$. By Theorem 5.1, this implies $\nu (H) \ge \nu ^*(H)/(d-1)\ge m/(d-1)$.

Let M be a matching of size at least $m/(d-1)$ in H. Consider the partition $x \in \bigcap _{i\in [(m-1)d+1]} A^{\pi (i)}_{T_i}$. Then players $\{\pi (i)\,|\,T_i\in M\}$ prefer in the partition x pairwise disjoint d-tuples of pieces, as needed. $\square$