Triangulation of a simplex generates triangulation of a face

Question

I am trying to understand the proof of Sperner’s Lemma in Francis Su’s Rental Harmony article here. Instead of giving the full formulation, let me only give definitions for the part I do not understand:

Consider the unit simplex $$ S = \{x \in \mathbb{R}^n: x_1, \ldots, x_n \geq 0, x_1 + \cdots + x_n = 1\} $$ of dimension $n-1$ in $\mathbb{R}^n$. And a triangulation (see p. 931) of $S$, i.e., a finite collection of

(T1) smaller $n-1$ dimensional simplices

(T2) whose union is $S$ and

(T3) such that the intersection of any two of them is either empty or a face of both.

In an induction step he uses, without proof, that this triangulation induces a triangulation also on the face $$ F = \{x \in S: x_n = 0\}. $$

Question: why is this the case?

This seems geometrically obvious and the proofs I found in the literature, including the original German article by Sperner himself, also seem to think so, because they all skip this step of the proof. But I don’t see why it is true.

Some preliminary work: First of all, what simplices should you pick to constitute the triangulation on that face? The definition requires simplices of the right dimension, so now $n-2$ dimensional ones. So you can’t just take the intersection of the original smaller simplices with the face $F$, since these may have the wrong dimension. This is illustrated in my figure below: although simplices $a$ and $d$ have a nonempty intersection with the face $F$, according to property (T1) in the definition in Su, they cannot be part of the triangulation of $F$, since the intersection is zero- and not one-dimensional.

So you probably need to take as the triangulation all $n-2$ dimensional intersections of simplices in the original triangulation and the face $F$.

That would, by construction, settle (T1), but I still don’t understand how to prove the properties (T2) and (T3).

Answer 1

The simplices $\sigma$ of the triangulation of $S$ that you pick to constitute the triangulation of $F$ are precisely those having the property that every vertex of $\sigma$ is contained in $F$. This is clear from the point of view of geometry/topology, because $F$ is closed and convex, and $\sigma$ is the convex hull of its vertex set, i.e. $\sigma$ is the smallest closed, convex set containing its own vertex set.

For an algebraic proof, the key thing to prove is that if the vertex set of $\sigma$ is contained in $F$ then $\sigma \subset F$. By writing the vertices of $F$ as $v_0,...,v_K$, and the vertices of $\sigma$ as $w_0,...,w_L$, and by using the assumption that $w_l \in F$ to write each $w_l$ as a convex combination $$w_l = s_{l,0} \, v_0 \, + .... + \, s_{l,K} \, v_K $$ you can then work through the algebra to rewrite an arbitrary convex combination $$w = t_0 \, w_0 \, + ... + \, t_L \, w_L \in \sigma $$ as a convex combination of $v_0,...,v_K$.

Added after comments: Once one understands the previous part, there is one big step left, namely property (T2). So, we must prove that $F$ is the union of those simplices of the triangulation such that each vertex of the simplex is in $F$.

Let $P$ be the $n-1$ dimensional plane containing $F$, let $H$ be the closed half-space of $P$ containing the simplex $S$. Note that the open half space $H-P$ is convex; this will be used below.

So, given a point $p \in F$, we must find a simplex $\sigma$ with vertices $v_0,...,v_K$ such that $p \in \sigma$ and $v_0,...,v_K \in F$.

To identify $\sigma$, we use the fact that $S$ can be written uniquely as the disjoint union of the interiors of the simplices in its triangulation (to be clear, the interior of a simplex $\sigma$ with vertices $v_0,...,v_K$ is all convex combinations $t_0 \, v_0 \, + ... + \, t_K \, v_K$ such that $t_0,...,t_K$ are all positive; as a special case, the interior of a $0$-simplex is just the $0$-simplex).

It follows that there exists a unique simplex $\sigma$ of the triangulation of $S$ such that $p$ is contained in the interior of $\sigma$. Letting $v_0,...,v_K$ be the vertices of $\sigma$, we must prove that each of the vertices $v_0,...,v_K$ is in $F$.

Arguing by contradiction, suppose that at least one of those vertices is not in $F$. Reorder the vertices as $v_0,...,v_J,v_{J+1},...,v_K$ so that $0 \le J \le K$, $v_0,...,v_J \not\in F$, and $v_{J+1},...,v_K \in F$. Let $[v_0,...,v_J]$ and $[v_{J+1},...,v_K]$ be the pair of simplices spanned by the vertices indicated, i.e. the set of convex combinations of the vertices indicated (in the special case $J=K$, the second simplex is undefined; that case will be handled separately in what follows).

Since $v_0,...,v_J \in H-P$, and since $H-P$ is convex, it follows that $[v_0,...,v_J] \subset H-P$.

Since $v_{J+1},...,v_K \in F$, and since $F$ is convex, it follows that $[v_{J+1},...,v_K] \subset F \subset P$.

In the special case that $J=K$, we conclude that $p \in \sigma = [v_0,...,v_K] \subset H-P$, contradicting that $p \in F$.

So from now on I'll assume that $J<K$. Write the point $p$ as a convex combination $$p = \underbrace{t_0 \, v_0 \, + ... + \, t_J \, v_J}_{r \, a} + \underbrace{t_{J+1} \, v_{J+1} \, + ... + \, t_K \, v_K}_{s \, b} $$ All of the coefficients $t_j$ ($0 \le j \le J$) are positive, since $p$ is in the interior of $\sigma$. By collecting terms as indicated, we may rewrite this as a convex combination $$p = r \, a + s \, b $$ where $a \in [v_0,...,v_J]$ and $b \in [v_{J+1},...,v_K]$, $r = t_0+...+t_J$ and $s=t_{J+1}+...+t_K$. Clearly $a \in H-P$ and $b \in F \subset P$.

Since $P$ is an $n-1$ dimensional plane and the line $\overline{ab}$ contains a point $a$ $P$ and a point $b$ not in $P$, it follows that the line $\overline{ab}$ intersects $P$ exactly at the point $b$. Since $p \in \overline{ab} - \{b\}$, it follows that $p \not\in P$ so $p \not\in F$, a contradiction.

Answer 2

Everything seems to be obvious intuitively, but when I started to think about your question I realized that it is not. I tried to find rigorous proofs, but this was not as trivial as I believed.

In Francis Su’s article an $n$-simplex $S$ in $\mathbb R^m$ is defined as the convex hull of a set $V = \{ p_0,\dots,p_n \}$ of $n+1$ affinely independent points $p_i \in \mathbb R^m$, for $n \le m$. In other words, $S = Conv(V) = \{ \sum_{i=0}^n t_i p_i \mid t_i \ge 0 , \sum_{i=0}^n t_i = 1 \}$. The points $p_i$ are the vertices of $S$. Since the $p_i$ are affinely independent, in the "convex sum representation" of $x \in S$ as $x = \sum_{i=0}^n t_i p_i$ the coordinates $t_i$ are uniquely determined.

A $k$-dimensional face of $S$ is any $k$-simplex in $\mathbb R^m$ which is the convex hull of a subset $V' \subset V$ having $k+1$ points.

A triangulation of an $n$-simplex $S$ is then defined as a finite collection $\mathcal{T} = \{S_i \}_{i \in C}$ of smaller $n$-simplices $S_i$ (which means $S_i \subset S$) whose union is $S$ and such that the intersection of any two of them is either empty or a face of both. More precisely, the last condition means the following: If $S_i = Conv(V_i)$, then $S_i \cap S_j = Conv(V_i \cap V_j)$.

We shall need a few simple lemmas. They are intuitively obvious, but we do not want to appeal to intuition and therefore we give formal proofs. These are not completely trivial and we do it completely elementary on the level of the article.

Lemma 1. Let $Face(\mathcal{T})$ denote the collection of all faces of all simplices in a triangulation $\mathcal{T}$. Then the intersection of any two of members of $Face(\mathcal{T})$ is either empty or a face of both members.

Proof. Consider $S'_1, S'_2 \in Face(\mathcal{T})$. Choose $S_i = Conv(V_i) \in \mathcal{T}$ such that $S'_i$ is a face of $S_i$. Then $S'_i = Conv(V'_i)$ with $V'_i \subset V_i$. We claim that $S'_1 \cap S'_2 = Conv(V'_1 \cap V'_2)$. It is obviuos that $Conv(V'_1 \cap V'_2) \subset S'_1 \cap S'_2$. Consider $x \in S'_1 \cap S'_2 \subset S_1 \cap S_2 = Conv(V_1 \cap V_2)$. We have $x = \sum_{p \in V_1 \cap V_2} t_p p$ with unique coordinates $t_p$. Define $t_p = 0$ for $p \in V_i \setminus V_1 \cap V_2$. Then $x = \sum_{p \in V_i} t_p p \in S_i$. Since $x \in S'_i$, we conclude that $t_p = 0$ for $p \in V_i \setminus V'_i$. Now let $p \in V_1 \cap V_2 \setminus V'_1 \cap V'_2$, i.e. $p \in V_1, V_2$ and $p \notin V'_i$ for $i = 1$ or $i=2$. Hence $p \in V_i \setminus V'_i$ for $i = 1$ or $i=2$ which shows that $t_p = 0$. This proves $x = \sum_{p \in V'_1 \cap V'_2} t_p p \in Conv(V'_1 \cap V'_2)$.

Lemma 2. No $n$-simplex $S = Conv(\{p_0,\dots,p_n\})$ in $\mathbb R^m$ contains an $r$-simplex $S' = Conv(\{q_0,\dots,q_r\})$ in $\mathbb R^m$ with $r > n$.

Proof. Let $S' \subset S$. W.lo.g. we may assume that $p_0 = 0$ (the translation $T(x) = x - p_0$ shifts $S, S'$ to $T(S), T(S')$ which are $n$- resp. $r$-simplices such that $T(S') \subset T(S))$. Then the vectors $p_1,\dots,p_n$ are linearly independent and the vectors $w_j = q_j - q_0$, $j = 1,\dots,r$ are linearly independent. Since $S' \subset S$, we have $q_j = \sum_{i=0}^n t^j_i p_i = \sum_{i=1}^n t^j_i p_i$. Thus the $w_j$ are contained in the span of $p_1,\dots,p_n$ which is an $n$-dimensional linear subspace of $\mathbb R^m$. Since the $w_j$ are linearly independent, we conclude $r \le n$.

Next note that each simplex $S$ is a topological space (a subspace of $\mathbb R^m$). All simplices are compact.

Lemma 3. Let $S = Conv(\{p_0,\dots,p_n\})$ be an $n$-simplex in $\mathbb R^m$. Then each non-empty open subset $U \subset S$ contains an $n$-simplex $S'$.

Proof. Let $\xi \in U$. There exists $\epsilon > 0$ such that $U^S_\epsilon(\xi) = \{ x \in S \mid \lVert x - \xi \rVert < \epsilon \} \subset U$. Write $\xi = \sum_{i=0}^n t_i p_i$. Since $\sum t_i = 1$, we may w.l.o.g. assume that $t_0 > 0$. Let $0 < r < t_0/n$. Then $\xi_r = (t_0 -nr)p_0 + \sum_{i=1}^n (t_i +r)p_i \in S$. Writing $\xi_r = \sum_{i=0}^n t^r_i p_i$, we see that all $t^r_i > 0$. Hence also all $t^r_i < 1$ and $\tau = \min(t^r_0,\dots,t^r_n, 1-t^r_0,\dots, 1-t^r_n)> 0$. We have $\xi_r - \xi = -nrp_0 + \sum_{i=1}^n rp_i = r(-np_0 + \sum_{i=1}^n p_i)$, thus we can choose $r$ such that $\lVert \xi_r - \xi \rVert < \epsilon/2$. Hence $U^S_{\epsilon/2}(\xi_r) \subset U$. Now let $0 < u < \tau$. Then all $\xi_i = \xi_r - u p_0 + u p_i = \xi_r + u(p_i - p_0) \in S$. We have $\xi_r - \xi_i = u(p_i - p_0)$, thus we can choose $u$ such that all $\xi_i \in U^S_{\epsilon/2}(\xi_r)$. The set $\Xi = \{ \xi_0, \dots, \xi_n \}$ is affinely independent, thus $S' = Conv(\Xi)$ is a $n$-simplex which is contained in the convex set $U^S_{\epsilon/2}(\xi_r)$ which is contained in $U$.

Lemma 4. Let $S_1,\dots,S_r$ be finitely many simplices of dimension $< n \le m$ in $\mathbb R^m$. Then $\bigcup_{i=1}^r S_i$ does not contain any $n$-simplex in $\mathbb R^m$.

Proof. By induction on $r$. The base case is covered by Lemma 2. Assume the assertion is true for $r \ge 1$ simplices. Now let $S_1,\dots,S_{r+1}$ be simplices of dimension $< n$. Assume $\bigcup_{i=1}^{r+1} S_i$ contains an $n$-simplex $S$. We know that $K = \bigcup_{i=1}^r S_i$ is compact and does not contain $S$. Hence $S \setminus K$ is a non-empty open subset of $S$. By Lemma 3 it contains an $n$-simplex $S'$. But then we must have $S' \subset S_{r+1}$ which is impossible by Lemma 2.

Now let us consider a triangulation $\mathcal{T} = \{S_i \}_{i \in C}$ of your unit $(n-1)$-simplex $S$ in $\mathbb R^n$. Let $p_n(x_1,\dots,x_n) = x_n$ be the projection onto the last coordinate which is a linear map. For $x \in S$ we have $0 \le p_n(x) \le 1$ and $x \in F$ iff $p_n(x) = 0$.

(1) Each $S'_i = S_i \cap F$ is either empty or a face of $S_i$.

Each $x \in S_i$ has the form $x = \sum_{i=0}^n t_i a_i$ for suitable $t_i \ge 0$ such that $\sum_{i=0}^n t_i = 1$, and therefore $x \in S'_i$ iff $p_n(x) = \sum_{i=0}^n t_i p_n(a_i) = 0$. Now assume $S'_i \ne \emptyset$. This implies $\sum_{i=0}^n t_i p_n(a_i) = 0$ for some convex combination which is possible only if at least one $p_n(a_i) = 0$. So let $a_{i_0},\dots,a_{i_k}$ be the vertices of $S_i$ with $p_n(a_{i_r}) = 0$. Their convex hull is a $k$-dimensional face $F^*$ of $S_i$ which is contained in $F$ since $p_n(x) = 0$ for $x \in F^*$. If $x = \sum_{i=0}^n t_i a_i \in S_i \setminus F^*$, then $t_j > 0$ for some $j \ne i_0,\dots,i_k$. Hence $p_n(x) \ge t_jp_n(a_j) > 0$, i.e. $x \notin F$. This proves $S'_i = F^*$.

(2) Define

$$C(F) = \{ i \in C \mid S'_i = S_i \cap F \text{ is an $(n-1)$-dimensional face of } S_i \} ,$$ $$\mathcal{T}(F) = \{ S'_i \}_{i \in C(F)} .$$

(a) The sets $S'_i \in \mathcal{T}(F)$ are $(n-1)$-simplices by definition.

(b) We have $S'_i \subset F$ by definition.

(c) The intersection of any two of them is either empty or a face of both. This follows from Lemma 1.

(d) The union of the $S'_i$ is $F$. This is the essential part of the proof.

We have $F = F \cap (\bigcup_{i \in C} S_i) = \bigcup_{i \in C} F \cap S_i = \bigcup_{i \in C} S'_i$. Now assume that $F \ne A = \bigcup_{i \in C(F)} S'_i$. $A$ is compact, thus $F \setminus A$ is a non-empty open subset of $F$. By Lemma 3, it contains an $(n-1)$-simplex $S'$. It must be covered by simplices of dimension $< n -1$. This contradicts Lemma 4.