1
$\begingroup$

There are many books and articles that prove Sperner's Lemma. Almost all that I have looked up happily take the following as obvious.

If $\mathcal{S}$ is a simplicial subdivision of the standard $n$-simplex, then every $(n-1)$-simplex of $\mathcal{S}$ is a face of at most two $n$-simplices of $\mathcal{S}$.

Most of the references don't even state this explicitly. Some of them prove the lemma only under an explicit assumption that the above holds. The only one that goes into a deeper discussion is a Polish book Wstęp do topologii by Engelking and Sieklucki. (I think that "Engelking, Sieklucki Topology: a geometric approach Sigma Series in Pure Mathematics, 4. Heldermann Verlag, Berlin, 1992" might be an English translation but I'm not sure since I have no access to it.) At first, they only prove Sperner's Lemma for iterated barycentric subdivisions for which the property above can be verified directly. Later, they show (using Invariance of Domain) that this property holds for all subdivisions.

My question: is there an elementary proof of the statement above? By "elementary" I mean one that avoids things like Invariance of Domain as well as homotopical and homological arguments.

$\endgroup$
3
$\begingroup$

It depends on what you mean by a "simplicial subdivision". I can think of two different definitions, leading to two different outcomes for your question.

In one definition, a "simplicial subdivision" is obtained from the original decomposition into simplices by repeating some kind of elementary subdivision. The iterated barycentric subdivision is like this, but there are more general constructions. In that case the proof should simply be induction.

In another defnition, a "simplicial subdivsion" simply means another simplicial structure on the same space of which the original skeleta are subcomplexes. In this situation, invariance of domain is your friend where nothing else will help, it seems to me.

The theme here is that the local topology of Euclidean space is subtler than you might think. Try proving that dimension is a topological invariant without homological arguments, for example.

$\endgroup$
  • $\begingroup$ I meant subdivisions by affine simplices with arbitrary combinatorial structure (sometimes called simplicial complexes). I do realize that Euclidean topology is subtle. I just wanted to make sure that I'm not overlooking something elementary since so many authors skip this point for some reason. $\endgroup$ – Karol Szumiło Nov 18 '15 at 12:28
  • $\begingroup$ Affine simplices of codimension 1, like flat hyperplanes, are always 2-sided for elementary reasons, so invariance of domain is unnecessary (my paragraph "in one definition"); same for codimension 1 simplices which are smooth, or tame, or something similar. But subdivisions which do not assume simplices to be affine or smooth or tame or something similar, do require invariance of domain (my paragraph "in another definition"). $\endgroup$ – Lee Mosher Nov 18 '15 at 17:03
  • $\begingroup$ I think I see what you are saying, except for the part that "the proof should simply be induction". Do you mean induction over the number of simplices? Take the subdivision of $\Delta^n$ whose $n$-simplices are spanned by $\{e_0, \ldots, \hat{e_i}, \ldots, e_n, b\}$ for all $i \in [n]$ where $b$ is the barycenter of $\Delta^n$. This subdivision is not a refinement of any subdivision with fewer simplices so I don't see how such induction could work. On the other hand, if I understand your comment correctly, in the affine case induction shouldn't be necessary. $\endgroup$ – Karol Szumiło Nov 18 '15 at 17:48
  • $\begingroup$ When referring to induction, I was imagining that the subdivision process itself is defined by induction. For example, the $n^{\text{th}}$ barycentric subdivision is the $1^{\text{st}}$st barycentric subdivision of the $n-1^{\text{st}}$ barycentric subdivision. In that situation, it would be appropriate to apply induction to prove properties of all the barycentric subdivisions at one time. However, there might well be a way to subvert the induction, and prove what you want directly without resort to induction. $\endgroup$ – Lee Mosher Nov 19 '15 at 0:08
  • $\begingroup$ Yes, I was already aware of this case when I was writing the question. My concern was that not every affine subdivision is obtained by such an iterative construction. In any case, thank you for pointing out that the affine case is easy. (For some reason Engelking and Sieklucki seem to imply the opposite since they use affine subdivisions and only mention the more general ones in passing.) $\endgroup$ – Karol Szumiło Nov 19 '15 at 12:43
1
$\begingroup$

I presume this answer is untimely, but I recently faced the exact same issue. It turns out that more is true:

  1. Every $(n-1)$-dimensional subsimplex in $\mathcal S$ that lies fully in the boundary of the “big” simplex is a face of precisely one $n$-dimensional subsimplex in $\mathcal S$.

  2. Every $(n-1)$-dimensional subsimplex in $\mathcal S$ that does not lie fully in the boundary of the “big” simplex is a face of precisely two $n$-dimensional subsimplices in $\mathcal S$.

An elementary proof of these claims that does not rely on algebraic topology can be found in Section 23.1 of Maschler et al. (2013). This beautifully elegant and not overly complicated proof is based on the geometric intuition gained by connecting the barycenter of the face with the omitted edge(s), and considering a sequence of points on this segment close to, but not on, the face.

$\endgroup$
  • $\begingroup$ I do appreciate this answer very much, even if it is untimely. In fact, not long after posting my question, I realized that the upper bound that I asked about is easy and the difficult part is actually the lower bound that you state in your answer. I managed to find a proof which I think is similar to the one you cite, but still it is very good to have a reference. (Although, it is a shame on topologists that the only (apparently) source that discusses this result is not even a topology book.) $\endgroup$ – Karol Szumiło Oct 12 '18 at 12:50
  • $\begingroup$ I'm going to leave the accepted answer as is, since it answers the question that I asked, even if it is not the question that I should have asked. $\endgroup$ – Karol Szumiło Oct 12 '18 at 12:50
  • $\begingroup$ @KarolSzumiło Thank you for the feedback! For the record, I never expected to change your accept tag, especially after such a long time since Lee Mosher’s answer, so don’t worry about it. My primary goal was to simply record this finding for future reference for me and for everybody else who might be interested, including you, and your question seemed to be the perfect outlet for this. As for your disappointment in other sources—it sometimes takes a bunch of game theorists to explain results that are apparently too trivial for hardcore topologists in a student-friendly manner... :-) $\endgroup$ – triple_sec Oct 24 '18 at 18:19

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.