1
$\begingroup$

My goal is to prove that any simplicial subdivision (or triangulation) of a simplex generates a simplicial subdivision on the faces of the original simplex.

Formally, let $n,k$ be integers such that $n\geq\max\{k,1\}$ and $k\geq0$. Suppose that the vectors $x^1,\ldots,x^{k+1}\in\mathbb R^n$ are affinely independent, that is, for any $\alpha_1,\ldots,\alpha_{k+1}\in\mathbb R$, one has $$\sum_{i=1}^{k+1}\alpha_ix^i=\underbrace{(0,\ldots,0)}_{\text{$n$-vector}}\,\,\text{ and }\,\,\sum_{i=1}^{k+1}\alpha_i=0\quad\text{if and only if}\quad\alpha_1=\cdots=\alpha_{k+1}=0,$$ and let $$\bigtriangleup(x^1,\ldots,x^{k+1})\equiv\left\{\sum_{i=1}^{k+1}\lambda_ix^i\,\Bigg|\,\lambda_1,\ldots\lambda_{k+1}\geq0\text{ and }\sum_{i=1}^{k+1}\lambda_i=1\right\}$$ be the $k$-simplex generated by them.

Consider a simplicial subdivision $\mathscr T$, where

  • $\mathscr T$ is a non-empty finite set consisting of $k$-simplices;

  • $\bigcup_{T\in\mathscr T}T=\bigtriangleup(x^1,\ldots,x^{k+1})$; and

  • if $T,T'\in\mathscr T$ and $T\cap T'\neq\varnothing$, then $T\cap T'$ is a face of both $T$ and $T'$; that is, $T\cap T'$ is a simplex all of whose vertices are also vertices of both $T$ and $T'$.

Now consider “projecting” the elements of $\mathscr T$ onto a face of the original simplex. Formally, consider the face $\bigtriangleup(x^1,\ldots,x^{k})$ of $\bigtriangleup(x^1,\ldots,x^k,x^{k+1})$, and define $$\mathscr E\equiv\bigcup_{T\in\mathscr T}\left\{E\,|\,\text{$E$ is a face of $T$ with $k$ vertices and }E\subseteq\bigtriangleup(x^1,\ldots,x^{k})\right\}.$$

I wish to show that $\mathscr E$ is a simplicial subdivision of the face $\bigtriangleup(x^1,\ldots,x^{k})$.

(In particular, that $\mathscr E\neq\varnothing$).

The idea is intuitively obvious geometrically: take the vertices of members of $\mathscr T$ that lie in the face $\bigtriangleup(x^1,\ldots,x^{k})$, then omit the vertex from each such $T\in\mathscr T$ that is not on this face. Yet, I’m struggling with formalizing this algebraically. Any suggestion would be greatly appreciated.


While the geometric intuition is pretty obvious, I’m struggling with coming up with a rigorous algebraic formalization. The key issue is that while every element in the face $\bigtriangleup(x^1,\ldots,x^k)$ is clearly contained in some $T\in\mathscr T$, it is all too well possible that this $T$ merely touches $\bigtriangleup(x^1,\ldots,x^k)$ at one point/segment/low-dimensional face, as opposed to having a $k-1$-dimensional face that is fully included in $\bigtriangleup(x^1,\ldots,x^k)$!

$\endgroup$
  • $\begingroup$ (i) I think the choice of the $x_i$ is irrelevant, and you may as well take the standard simplex in $\Bbb R^{k+1}$. (ii) it's usual to regard the faces of simplices in the triangulation as elements of the triangulation, and if you do this then the simplices in the triangulation contained in say $\Delta(x_1,\ldots,x_n)$ form a triangulation of $\Delta(x_1,\ldots,x_n)$. $\endgroup$ – Lord Shark the Unknown Sep 17 '18 at 17:48
  • $\begingroup$ @LordSharktheUnknown How do I know that there are faces of the subsimplices in the triangulation contained in the face $\bigtriangleup(x^1,\ldots,x^k)$? While the geometric intuition is obvious, I’m struggling with coming up with a rigorous algebraic formalization. The key issue is that while every element in the face $\bigtriangleup(x^1,\ldots,x^k)$ is clearly contained in some $T\in\mathscr T$, it is possible that this $T$ merely touches $\bigtriangleup(x^1,\ldots,x^k)$, as opposed to being fully included in it! $\endgroup$ – triple_sec Sep 17 '18 at 20:28
  • $\begingroup$ How can "$E$ be a subset of $T$ with $k$ vertices" and not equal $\Delta(x^1, \dots, x^k)$? $\endgroup$ – BananaCats Category Theory App Sep 17 '18 at 20:49
  • 1
    $\begingroup$ I'm going to open my Munkres' book and see if I can follow along with you. This is exciting! $\endgroup$ – BananaCats Category Theory App Sep 17 '18 at 20:52
  • $\begingroup$ @EnjoysMath It is weaker than linear independence—I added the definition. As for your other comment: for example, let $n=k=2$, so that $k+1=3$. If you cut a triangle in the plane into, say, four congruent triangles, then there may exist a side of each of the small triangles that is included in, but does not coincide with, a side of the big triangle. $\endgroup$ – triple_sec Sep 17 '18 at 20:53
0
$\begingroup$

I now have an answer, which I am going to outline as follows. The most challenging part is showing that $\bigtriangleup(x^1,\ldots,x^k)\subseteq\bigcup_{E\in\mathscr E}E$ (in particular, $\mathscr E\neq\varnothing$), so I am going to focus on this.

In other words: I need to find for every point in $\bigtriangleup(x^1,\ldots,x^k)$ a face of some member of the subdivision $\mathscr T$ that has $k$ vertices and fully lies in $\bigtriangleup(x^1,\ldots,x^k)$.

For example, if $k=3$, we want the triangle on the base $\bigtriangleup(x^1,x^2,x^3)$ to be intersected by a tetrahedron from the subdivision of the “big” tetrahedron $\bigtriangleup(x^1,x^2,x^3,x^4)$ not just at a single point, not just at a line segment, but actually a smaller triangle!

The case $k=1$ is rather trivial, so assume from now on that $k\geq 2$. In what follows, if $T\in\mathscr T$, then denote the vertices of the simplex $T$ by $y^1(T),\ldots,y^{k+1}(T)$, so that $$T=\bigtriangleup(y^1(T),\ldots,y^{k+1}(T)).$$


Step 1$\quad$ Define, for each $\ell\in\{1,\ldots,k-1\}$, $$\mathcal I_{\ell}=\{I\,|\,I\subseteq\{1,\ldots,k+1\}\text{ and }\#I=\ell\}.$$ That is, $\mathcal I_{\ell}$ is simply the family of all the $\ell$-element subsets of the index set $\{1,\ldots,k+1\}$. For each $I\in\mathcal I_{\ell}$, define $$\mathscr T_{I}\equiv\{T\in\mathscr T\,|\,y^i(T)\in\bigtriangleup(x^1,\ldots,x^k)\text{ for each $i\in I$}\}.$$Furthermore, let $$W_T\equiv\bigtriangleup(\{y^i(T)\}_{i\in I})$$ for each $\ell\in\{1,\ldots,k-1\}$, $I\in\mathcal I_{\ell}$, and $T\in\mathscr T_I$. Finally, define $$W\equiv\bigcup_{\ell=1}^{k-1}\bigcup_{I\in\mathcal I_{\ell}}\bigcup_{T\in\mathscr T_I}W_T.$$ Intuitively, $W$ is the set of all points that can be expressed as a linear combination of at most $k-1$ vertices of some member of the subdivision $\mathscr T$. (Remark: I am pretty sure that the set $\mathscr T_I$ is never empty, but I didn’t bother checking that in detail because it is not really important for the purposes of the proof—you’ll see soon why not.)


Step 2$\quad$ Fix, for a moment, $\ell\in\{1,\ldots,k-1\}$, $I\in\mathcal I_{\ell}$, and $T\in\mathscr T_I$. It is not difficult to check that $W_T\subseteq\bigtriangleup(x^1,\ldots,x^k)$ and that $W_T$ is closed in $\bigtriangleup(x^1,\ldots,x^k)$. The next step is to show that $W_T$ has empty interior in $\bigtriangleup(x^1,\ldots,x^k)$ (with respect to the relative Euclidean topology). Indeed, if one had for some $w\in W_T$ a small ball around $w$ contained in $W_T$, then one could define, for any $\varepsilon\in(0,1]$, $$a^i\equiv(1-\varepsilon)w+\varepsilon x^i$$ for each $i\in\{1,\ldots,k\}$. (Geometrically, think about “shrinking” the face $\bigtriangleup(x^1,\ldots,x^k)$ around $w$.) It is easily seen that the affine independence of $x^1,\ldots,x^k$ implies that of $a^1,\ldots,a^k$. But for small enough $\varepsilon$, $\{a^1,\ldots,a^k\}$ would be fully contained in $W_T$, which is a simplex with $\ell<k$ vertices—this would contradict affine independence. It follows that $W_T$ has empty (relative) interior and it is nowhere dense in $\bigtriangleup(x^1,\ldots,x^k)$.


Step 3$\quad$ Since the union defining $W$ is finite, it follows that $W$ is also closed and nowhere dense in $\bigtriangleup(x^1,\ldots,x^k)$.


Step 4$\quad$ Fix any $w\in\bigtriangleup(x^1,\ldots,x^k)$. The goal is to show that $w\in E$ for some $E\in\mathscr E$. Since $W$ is nowhere dense in $\bigtriangleup(x^1,\ldots,x^k)$, one can find for any $m\in\mathbb N$ some $w^{(m)}\in\bigtriangleup(x^1,\ldots,x^k)\setminus W$ such that $$\lVert w^{(m)}-w\rVert<\frac{1}{m},$$ where $\lVert\cdot\rVert$ is the $n$-dimensional Euclidean norm. Clearly, the sequence $(w^{(m)})_{m\in\mathbb N}$ converges to $w$. Since the union of the members of $\mathscr T$ yields $\bigtriangleup(x^1,\ldots,x^k,x^{k+1})$, there exists some $T^{(m)}\in\mathscr T$ such that $w^{(m)}\in T^{(m)}$, so that $$w^{(m)}=\sum_{i=1}^{k+1}\mu_i^{(m)}y^i(T^{(m)})$$ for some weight vector $(\mu_i^{(m)})_{i=1}^{k+1}$ whose elements are non-negative and sum up to $1$. Let $$I^{(m)}\equiv\{i\in\{1,\ldots,k+1\}\,|\,\mu_i^{(m)}>0\}.$$ Now, since $w^{(m)}$ takes zero weight from $x^{k+1}$ in the “big” simplex $\bigtriangleup(x^1,\ldots,x^k,x^{k+1})$, it follows that $y^i(T^{(m)})\in\bigtriangleup(x^1,\ldots,x^k)$ for every $i\in I^{(m)}$. This implies two things:

  1. $\#I^{(m)}>k-1$, which follows from the fact that $w^{(m)}\notin W$; and
  2. $\#I^{(m)}<k+1$, because not all of the affinely independent vertices $y^1(T^{(m)}),\ldots,y^{k+1}(T^{(m)})$ can lie in the proper face $\bigtriangleup(x^1,\ldots,x^k)$.

Thus, $\#I^{(m)}=k$. Showdown time: since $\mathscr T$ is finite, there exists a subsequence $(T^{(m_r)})_{r\in\mathbb N}$ whose terms are all the same; let me denote it by $T^0$. By the foregoing, $T^0$ has precisely $k$ vertices lying in $\bigtriangleup(x^1,\ldots,x^k)$; let the simplex spanned by these $k$ vertices be denoted as $E^0$. Clearly, $E^0\in\mathscr E$. Also, $E^0$ is closed in $\bigtriangleup(x^1,\ldots,x^k)$ and the subsequence $(w^{(m_r)})_{r\in\mathbb N}$ in $E^0$ converges to $w$. Therefore, $w\in E^0$, and the proof is complete. Any comments on it are greatly appreciated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.