{'fraction_non_alphanumeric': 0.04886656440180066, 'fraction_numerical': 0.005955424549583421, 'mean_word_length': 3.3885075677578316, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 71, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The lemmas of Alexander and Sperner

Alexander's lemma is a version of Sperner's lemma published by Alexander two years earlier than Sperner's paper. The present paper is devoted to a modern but elementary exposition of lemmas of Alexander and Sperner and their main topological applications: Brouwer's theorems about the topological invariance of dimension and of domains (here we follow Lebesgue ideas in the form given to them by Sperner), Brouwer's fixed-point theorem, and Alexander's theorem about the topological invariance of homology groups. Along the way we relate the Knaster-Kuratowski-Mazurkiewich argument with the notion of simplicial approximations, provide a cohomological interpretation of Sperner's lemma and of its combinatorial proof, and explain how classical proofs of Sperner's and Alexander's lemma lead to path-following algorithms. The exposition does not assume any knowledge of algebraic topology.

Apparently, initially it was well understood how the lemmas of Alexander and Sperner are related. The book [AH] by P. Alexandroff and H. Hopf, referred to by J. Dieudonné, was comissioned in 1928 by R. Courant for his book series Die Grundlehren der Mathematischen Wissenschaften, published by Springer-Verlag. It was published in 1935. For quite a while it was a definitive monograph in topology. Sperner's lemma appears in [AH] in an Appendix to Chapter IX devoted to "elementary" proofs of Brouwer's fixed point theorem and related results. The proofs given in [AH] are not quite elementary: they are based on a version of Alexander's lemma, proved earlier in the book by using chains and Alexander's methods. Sperner's paper [S] is referred to only in a footnote, while Alexander's papers [A1], [A2] are listed at the end of the book among the main references for this Chapter.
In 1932 P. Alexandroff published a short book [A-f2], a sort of popular introduction to the basic notions of topology, which at the same time looks like a blueprint for parts of [AH]. It was originally intended to be an appendix to Hilbert's Anschauliche Geometrie [HC], and the preface to [A-f2] was written by Hilbert himself. The book culminates in an outline of proofs of the topological invariance of dimension and of homology groups based on methods of Brouwer, Lebesgue, and Alexander. As in [AH], Alexander's lemma appears in the form of the last two out of three conservation theorems. Sperner's lemma is not even mentioned.
Later on the fates of Alexander's and Sperner's lemmas diverged. Alexander's lemma disappeared in the sky of more and more abstract and powerful machinery of algebraic topology. It became customary to prove Brouwer's fixed-point theorem as an illustration of the power of this machinery. For example, Spanier [Sp] proves it only on p. 194, and Hatcher [H] states Brouwer's fixed-point theorem on p. 114 and completes the proof on p. 124. Sperner's lemma became a tool of choice in more set-theoretic branches of topology such as the dimension theory, although algebraic topology triumphantly returned to the dimension theory in the works of A.N. Dranishnikov [Dr1], [Dr2]. Sperner's lemma became a tool of choice also in combinatorics, game theory, and mathematical economics.
The rest of the paper is devoted to the mathematical details of this story. No familiarity with algebraic topology is assumed, and, perhaps, the paper can serve as an invitation to it. We start with the basic notions of simplices, simplicial complexes, and chains, and then prove Alexander's lemma. As the first applications we prove Brouwer's invariance of dimension and invariance of domains theorems following Lebesgue ideas in the form given to them by Sperner. But we refer to Alexander's lemma instead of Sperner's one. Next, we introduce simplicial approximations and use them to prove Brouwer's fixed-point theorem. Our main application of simplicial approximations is to the beautiful Alexander's proof of the topological invariance of homology groups. A technical part of this proof is relegated to Appendix 2. Brouwer's fixed-point theorem is also proved by Knaster-Kuratowski-Mazurkiewich argument, which after a closer examination turns out to be a version of the proof based on simplicial approximations. Section 7 is devoted to Sperner's lemma and its combinatorial proof, and Sections 8 and 10 to their cohomological interpretation. In Section 9 we explain how classical proofs of Sperner's lemma lead to so-called path-following algorithms.

Simplicial complexes and chains
Geometric simplices. Recall that the convex hull of points x 0 , x 1 , . . . , x n ∈ R d in a Euclidean space R d is the set of all linear combinations (1) n i = 0 a i x i such that the coefficients a i are real and non-negative and n i = 0 a i = 1.
The points x 0 , x 1 , . . . , x n are said to be affinely independent if the two relations n + 1 i = 1 a i x i = 0 and n + 1 i = 1 a i = 0 together imply that all coefficients a i = 0. If this is the case, then the presentation of a point of the convex hull of x 0 , x 1 , . . . , x n in the form (1) is unique. In this case the numbers a 0 , a 1 , . . . , a n are called the barycentric coordinates of the point (1). A trivial verification shows that the points x 0 , x 1 , . . . , x n are affinely independent if and only if the vectors are linearly independent in R d . A geometric n-simplex, or a geometric simplex of dimension n in R d is defined as the convex hull of n + 1 affinely independent points in R d , called its vertices. A geometric simplex is defined as a geometric n-simplex for some n . The convex hulls of subsets of the set of vertices of a geometric simplex σ are called its faces. A face of σ is said to be proper if it is not equal to σ. Each face is also a geometric simplex. A face is said to be an n-face if it is a geometric n-simplex. The union bd σ of all proper faces of σ is called the geometric boundary of σ. It is the boundary of σ in the most naive sense.

Geometric simplicial complexes.
A geometric simplicial complex in R d is a finite collection S of geometric simplices in R d such that if σ ∈ S and τ is a face of σ, then τ ∈ S, and if σ, σ ∈ S then σ ∩ σ is a face of both σ and σ . The vertices of geometric simplices σ ∈ S are called vertices of S , and the set of vertices of S is denoted by v (S ). The dimension of S is the maximal n such that S contains an n-simplex. A geometric simplicial complex Q is said to be a subcomplex of S if every simplex of Q is also a simplex of S .
The union of all geometric simplices of S is denoted by S and called the polyhedron of S , and S is said to be a triangulation of S . If Q is a subcomplex of S , then Q ⊂ S . Most of interesting (finitely dimensional) topological spaces are homeomorphic to polyhedra, and such spaces are most accessible to combinatorial and algebraic methods.
Abstract simplicial complexes. A substantial part of the theory of geometric simplicial complexes is purely combinatorial. There is a combinatorial counterpart of the notion of a geometric simplicial complex, namely, the notion of an abstract simplicial complex. It is defined as a finite collection K of subsets of a finite set v (K ) such that if σ ∈ K and σ ⊂ σ, then σ ∈ K , and v (K ) is equal to the union of all subsets in K. The elements of v (K ) are called the vertices, and the elements of K the simplices of K .
A simplex σ is said to be a face of a simplex σ if σ ⊂ σ. A face of σ is said to be proper if it is not equal to σ. A simplex σ ∈ K is said to be an n-simplex or a simplex of dimension n if | σ | = n + 1, where, as usual, we denote by | σ | the number of elements of σ. The dimension of K is the maximal n such that K contains an n-simplex.
Geometric simplicial complexes and abstract ones. A geometric simplicial complex S leads to an abstract simplicial complex a (S ) having as its set of vertices the set v (S ) of vertices of S , and as its n-simplices the sets of vertices of geometric n-simplices of S . The geometric simplicial complex S can be recovered from a (S ) as the set of convex hulls of simplices of a (S ). But the fact that the vertices of a (S ) are the points of R d is better to be ignored to the extent possible. From such a point of view the complex a (S ) encodes the combinatorics of S, understood as the pattern of intersections of geometric simplices of S.
The combinatorial part of the theory deals not with geometric simplicial complexes S , but with corresponding abstract simplicial complexes a (S ). Since there is a tautological one-toone correspondence between the simplices of S and the simplices of a (S ), which respects the property of being a face, usually there is no need to distinguish between S and a (S ). Also, some definitions and arguments apply equally well to both geometric and abstract simplicial complexes. In such situations we will speak simply about simplicial complexes.
Simplicial maps. This notion is easier to introduce in the context of abstract complexes. Let K , L be abstract simplicial complexes. Simplicial maps ϕ : K −→ L are defined as maps taking simplices of K to simplices of L. When L consists of a single simplex and its faces, every subset of v (L) is a simplex and every map v (K ) −→ v (L) is a simplicial map K −→ L.
For geometric simplicial complexes S , S simplicial maps S −→ S are defined simply as simplicial maps a (S ) −→ a (S ). In other words, a simplicial map ϕ : S −→ S is a map ϕ : v (S ) −→ v (S ) such that ϕ takes the set of vertices of each simplex of S into the set of vertices of some simplex of S . Obviously, a simplicial map ϕ : S −→ S defines a map from the set of simplices of S to the set of simplices of S . The latter map is also denoted by ϕ.
While we treat simplicial maps as combinatorial objects, their raison d'être is the fact that they are combinatorial analogues of continuous maps. It is comforting to know that a sim-plicial map ϕ : S −→ S canonically extends to a continuous map ϕ : S −→ S . It is defined as follows. Let { x 0 , x 1 , . . . , x n } be the set of vertices of a simplex of S . If a 0 , a 1 , . . . , a n are non-negative numbers with the sum 1, then ϕ : It is easy to see that ϕ is correctly defined and continuous. Somewhat surprisingly, we will use not the maps ϕ , but simplicial maps ϕ themselves as models of continuous maps.

Subdivisions of geometric simplicial complexes.
In order to find a good enough simplicial model of S considered as a topological space or of a continuous map S −→ T , one usually needs to replace S by a simplicial complex having the same polyhedron, but smaller simplices. A geometric simplicial complex S is said to be a subdivision of a geometric simplicial complex S if every simplex of S is contained in a simplex of S and every σ ∈ S is equal to the union of simplices of S contained in σ. If S is a subdivision of S, then, obviously, S = S . Given S and σ ∈ S, let S (σ) be the set of simplices of S contained in σ. Then S (σ) is a geometric simplicial complex and S (σ) = σ, i.e. S (σ) is a triangulation of σ. Clearly, the polyhedron S is equal to the union of polyhedra S (σ) .

Chains and boundaries.
The key element of the combinatorial structure of simplicial complexes is the relation " τ is a face of σ" between two simplices τ, σ. The boundary of a geometric figure has dimension less by 1 than the dimension of the geometric figure itself, and the geometric intuition suggests to concentrate on the case when the dimension of τ is 1 less than the dimension of σ. In this case algebraic topology suggests to encode this relation by a map assigning to an n-simplex the formal sum of all its (n − 1)-faces. Such formal sums with coefficients in a fixed abelian group are known as chains. For the purposes of this paper it is sufficient to consider only the chains with coefficients in F 2 = Z/2Z. Such chains can be identified with sets of simplices of the same dimensions, namely, with sets of simplices appearing with non-zero coefficients in the formal sum, and can be thought of as geometric figures, say, as complexes consisting of all faces of simplices with non-zero coefficients.
Let us turn to formal definitions and consider a simplicial complex X , either geometric or abstract. For an integer m 0 let C m (X ) be the vector space over F 2 having the set of all m-simplices of X as its basis. The elements of C m (X ) are called the m-chains of X . The boundary ∂σ of an m-simplex σ of K is defined as the sum of all (m − 1)-faces of σ. Extending the map σ −→ ∂σ by linearity we get the boundary operator If X is a geometric simplicial complex, then for every m there is a canonical isomorphism between the spaces of m-chains of X and of a (X ). These isomorphisms respect the boundary operators, and we will use them to identify chains of X with chains of a (X ).
Induced maps. Let X, Y be two simplicial complexes (either geometric or abstract) and let ϕ : X −→ Y be a simplicial map. For an integer m 0 and an m-simplex σ of X let Informally, if the dimension of ϕ(σ) is < m , then ϕ(σ) is equal to zero as an m-simplex. Let us define the induced map as the extension of the map σ −→ ϕ * (σ) by linearity. The basic property of induced maps is the fact that they commute with the boundary operators in the sense of the following theorem.
for all simplices σ of X .

Proof.
Let σ be an m-simplex of X . Then ϕ(σ) is a simplex of Y of dimension m .

A lemma of Alexander
Subdivisions of a geometric simplex. Let I = { 0, 1, 2, . . . , n }. Let δ be the geometric nsimplex in R d with the vertices v 0 , v 1 , . . . , v n . For each i ∈ I let δ i be the (n − 1)-face of ∆ having as its vertices all points v 0 , . . . , v n except v i . Every proper face of δ is contained in δ i for some i ∈ I. The geometric boundary bd δ is equal to the union of all faces δ i . Let ∆ be the geometric simplicial complex consisting of the simplex δ and all its faces, and let bd ∆ be the complex consisting of all proper faces of δ. Then δ is an n-simplex of ∆ and Let T be a subdivision of ∆, or, what is the same, a triangulation of the simplex δ.
Clearly, the dimension of T is n . Since simplices are convex, every simplex of T contained in bd δ is contained in δ i for some i ∈ I. Let bd T be the subcomplex of T consisting of simplices contained in bd δ, and for each i ∈ I let T i be the subcomplex of T consisting of simplices contained in δ i . Then bd T is a triangulation of bd δ and T i is a triangulation of δ i for each i ∈ I. Obviously, bd T is equal to the union of the complexes T i .
For the rest of the paper we will keep the above notations I, δ, δ i , ∆, T , etc.
Proof. By the definition, C n (∆) is a one-dimensional vector space over F 2 with δ forming a basis. Therefore ϕ * (α) = c δ for some coefficient c (of course, c = 0 or 1, but the proof does not depend on this). It follows that ∂(ϕ * (α)) = c (∂δ). But Theorem 1 implies that ∂(ϕ * (α)) = ϕ * (∂α) = ∂δ. Hence c = 1 and ϕ * (α) = δ. ■ Subdivision of chains. Let S be a geometric simplicial complex and let S be a subdivision of a S . Given a geometric m-simplex σ of S , let The non-branching property. If τ is an (n − 1)-simplex of T, then either τ ⊂ bd δ and then τ ⊂ δ i for some i , or τ ⊂ bd δ. In the first case τ is a face of exactly one geometric n-simplex of T, and in the second case τ is a face of exactly two geometric n-simplices of T.
We will accept this property as geometrically obvious and call it the non-branching property. Let us consider the subdivisions of chains of ∆ with respect to T . The non-branching property means that an (n − 1)-simplex of T enters the boundary ∂ [[δ]] with the coefficient 1 if it is contained in bd δ, and with the coefficient 2 otherwise. It follows that Proof. Since the subdivision map is linear by the definition, It remains to combine this equality with (3). ■

Corollary. If S is a subdivision of S as above, then
Proof. Lemma implies that this is true when α consists of only one simplex of S. The general case follows by linearity. ■ Pseudo-identical maps. If S is a subdivision of a geometric simplicial complex S as above, then S = S , but there is no natural simplicial map S −→ S . The subdivision of chains α −→ [[α]] serves as a substitute of such map. There is no natural simplicial map S −→ S either, but there are some distinguished maps S −→ S , namely, the simplicial approximations of the identity map id : S −→ S . In the situation at hand the notion of simplicial approximation reduces to the following.
Let S be a geometric simplicial complex and let x ∈ S . Then x belongs to at least one simplex of S , and since the intersection of simplices is also a simplex, there is unique minimal (with respect to the inclusion) simplex of S containing x , called the carrier of x in S .
Suppose now that S is a subdivision of S . Following Alexander [A2], we will say that a simplicial map ϕ : is a vertex of σ for every vertex v of S and every simplex σ of S containing v .
Pseudo-identical maps always exist. Indeed, let ϕ : v (S ) −→ v (S ) be an arbitrary map such that ϕ( v ) is a vertex of the carrier of v for every vertex v of S . Then ϕ is a pseudo-identical simplicial map. It is sufficient to check that ϕ is a simplicial map. Let τ be a simplex of S . Since S is a subdivision of S , the simplex τ is contained in a simplex σ of S . Every vertex of τ belongs to σ and hence its carrier is either σ or a proper face of σ. It follows that ϕ maps all vertices of τ to vertices of σ. It follows that ϕ is a simplicial map.
Alexander's lemma. Let S be a subdivision of S as above.
Proof. The theorem is trivially true for 0-chains. Arguing by induction, we may assume that it is true for m-chains with m n − 1. Let σ be an n-simplex of S considered as an nchain. Then ∂σ is an (n − 1)-chain and by the inductive assumption On the other hand, by applying the above lemma to δ = σ, we see that and hence We are almost ready to apply Theorem 2. Recall that the collection S (σ) of all simplices of S contained in σ is a triangulation of σ. The subdivisions [[∂σ]] of ∂σ with respect to S and with respect to S (σ) are obviously the same. Since the simplicial map ϕ is pseudoidentical, it induces a simplicial map S (σ) −→ σ, which is also pseudo-identical. The corresponding induced map is simply the restriction of ϕ * . By applying Theorem 2 to this simplicial map and the chain [[σ]] in the roles of ϕ and α respectively, we conclude that This proves the theorem for n-chains consisting of one simplex. By linearity this implies that the theorem is true for all n-chains. An application of induction completes the proof. ■

Remarks.
Alexander's lemma is the last and crucial lemma in the paper [A2] by Alexander, devoted to his second (and the first completely satisfactory) proof of the topological invariance of Betti numbers (essentially, of the homology groups) of polyhedra. Theorem 2 together with its proof is a part of Alexander's proof of this lemma. Apparently, it was Alexandroff [A-f2] who elevated this part of Alexander's proof to a theorem.
Alexandroff [A-f2] and Alexandroff-Hopf [AH] viewed Theorem 1 as "Theorem of conservation of boundaries by simplicial maps" (see [AH], Chapter IV, Section 3.7), Theorem 2 as its counterpart, and Alexander's lemma as a natural extension of Theorem 2. Alexandroff and Hopf gave all of them the name of conservation theorems ("Erhaltungsatzes" in German).

Brouwer's invariance of dimension theorem
Systems of sets and coverings. Let X ⊂ R d . A covering of X is a finite system (5) F 0 , F 1 , F 2 , . . . , F s of subsets R d such that X is contained in their union. The covering (5) is said to be closed if all F i are closed. Let ε > 0. The covering (5) is said to be an ε-covering if the diameter of every F i is < ε. The order of a system of sets (say, a covering) is the maximal number m such that there are m different sets in the system having non-empty intersection.

Lemma.
Suppose that m is the order of a closed ε-covering of δ. If ε is sufficiently small, then there is a closed covering of δ having the order m and consisting of n + 1 sets Proof. Let ε > 0 be so small that no set of diameter < ε can intersect all (n − 1)-faces δ i of δ. Then, in particular, no set of diameter < ε can simultaneously contain a vertex v i and a point of the (n − 1)-face δ i opposite to it. Suppose that (5) is an ε-covering of δ. By the choice of ε the n + 1 vertices of δ belong to n + 1 different sets F i . After renumbering the sets F i , if necessary, we may assume that v i ∈ F i for all i ∈ I. Then F i is disjoint from δ i , again by the choice of ε.
Suppose that the number s of sets (5) is > n + 1, and consider some set F k with k > n . By the choice of ε the set F k is disjoint from some (n − 1)-face δ i . Let us consider the union On the other hand, both F k and F i are disjoint from δ i and hence the union F k ∪ F i is also disjoint from δ i . Let us replace the sets F k , F i by their union F k ∪ F i and rename this union as F i . This results in a new covering of δ, which, as we just saw, satisfies the last condition of the lemma. Clearly, this operation cannot increase the order of the covering. By repeating this process we will eventually arrive at a covering consisting of n + 1 sets and satisfying the two other conditions of the lemma also. ■ Lebesgue lemma for closed sets. Suppose that (5) is a system of closed subsets of a compact set X . Then there is a number ε > 0 with the following property: if there is a point of X whose distance from several sets of the system (5) is < ε, then these sets have non-empty intersection. Every such number ε > 0 is called a Lebesgue number of the system (5).
Proof. Arguing by contradiction, suppose that for every natural number m there is a point x m ∈ X and a subsystem F m of the system of sets (5) such that the distance of x m from every set of the system F m is < 1/m , but the intersection of sets from F m is empty. Since (5) has only a finite number of subsystems, we may assume, after passing to a subsequence if necessary, that all subsystems F m are the same and hence are equal to F 1 . Since X is compact, we can also assume that the points x m converge to a point x ∈ X . Then the distance of x from each of the sets of the subsystem F 1 is equal to 0. Since these sets are closed, x belongs to all of them, and hence the intersection of sets from F 1 is non-empty, contrary to the assumption. The theorem follows. ■ Subdivisions into small simplices. We will need the following elementary result: for every ε > 0 there exist triangulations of δ consisting of simplices of diameter < ε. It is not hard to believe that such triangulations exist, and this fact is often accepted without even explicitly stating it. In fact, even more is true. For every geometric simplicial complex S there is a subdivision S of S consisting of simplices of diameter < ε. In order not to interrupt the flow of ideas, the proof is deferred till Appendix 1. (6) is a closed covering of δ such that v i ∈ F i and F i is disjoint from δ i for all i ∈ I. Then the order of the covering (6) is n + 1.

Lebesgue-Sperner theorem. Suppose that
Proof. Let ε > 0 be a Lebesgue number of the covering (6), and let T be a triangulation of δ such that the maximal diameter of a simplex of T is < ε. Suppose that some simplex σ of T intersects all sets (6). Then every point of σ has the distance < ε from each of the sets (6) and hence Lebesgue lemma implies that these n + 1 sets have non-empty intersection. It remains to prove that such a simplex σ exists.
Recall that ∆ is the simplicial complex consisting of the simplex δ and all its faces, and that T is a subdivision of ∆. Let us choose for every vertex v of T a set F i containing v and set ϕ( v ) = v i . Then ϕ is a map from the set of vertices of T to the set of vertices of ∆. Since every set of vertices of ∆ is the set of vertices of a simplex of ∆, the map ϕ is a simplicial map T −→ ∆. Moreover, as we will see in a moment, ϕ is a pseudo-identical map. Indeed, suppose that v be a vertex of T and σ is a simplex of ∆ such that v ∈ σ. It is sufficient to show that in this case ϕ( v ) is a vertex of σ. If not, then v ∈ F i for some i ∈ I such that v i is not a vertex of σ. In this case σ ⊂ δ i and hence v ∈ δ i , contrary to F i being disjoint from δ i . It follows that ϕ is pseudo-identical. Now Alexander's lemma implies that ϕ * ([[δ]]) = δ and hence ϕ(σ) = δ for some nsimplex σ of T . By the construction of ϕ this means for every i ∈ I some vertex of σ belongs to F i and hence σ intersects all sets (6). This completes the proof. ■ Lebesgue tiling (covering) theorem. If ε is sufficiently small, then every ε-covering of δ has order n + 1.

Proof.
It is sufficient to combine Lebesgue-Sperner theorem with the first lemma. ■

Remarks.
After presenting this proof of the Lebesgue tiling theorem, Alexandroff credits it to Sperner and Hopf (see [A-f2], footnote 40): The above proof of the tiling theorem is due in essence to Sperner; the arrangement given here was communicated to me by Herr Hopf.
In fact, the outline and most of the details of this proof are the same as in Sperner's paper [S]. Alexandroff-Hopf proof differs from Sperner's one only in using Alexander's lemma instead of Sperner's combinatorial arguments. This wouldn't be possible without assigning to a vertex v of T a vertex v i of ∆ and treating the resulting map ϕ as a simplicial map T −→ ∆.
In contrast, Sperner assigns to a vertex v of T a number i ∈ I (in both versions the assignment is subject to the same condition v ∈ F i ).
Nowadays it is only natural to turn the set I = { 0, 1, 2, . . . , n } of subscripts enumerating the sets F i into an abstract simplex and then identify it with the set of the vertices of ∆. This was hardly the case around 1930, when Alexandroff wrote his book [A-f2]. But the discovery of this idea was certainly facilitated by the notion of the nerve of a system of sets, introduced by Alexandroff [A-f1] only a little earlier. One may speculate that Alexandroff's contribution to the above proof is more significant than writing down Hopf's version of Sperner's proof.
The beautiful idea of turning various sets and maps into simplicial complexes and maps is well established by now, at least in some quarters. In skilled hands it is very powerful.
Canonical coverings of simplicial complexes by closed barycentric stars. Now we need a converse of Lebesgue tiling theorem (see Theorem 3 below). To begin with, for every geometric m-simplex σ we will construct a canonical closed covering of σ by m + 1 sets. Let x 0 , x 1 , . . . , x m be the vertices of σ, and let a 0 , a 1 , . . . , a m be the barycentric coordinates of points in σ (see Section 1). Recall that a i are non-negative real numbers with the sum 1. For every k = 0, 1, 2, . . . , m let B k be the set of points x of σ such that a k is maximal among the barycentric coordinates a i of x . Clearly, the sets B k form a closed covering of σ. The intersection of all these sets consists of one point, the barycenter of σ, which is the only point for which all barycentric coordinates are equal.
Obviously, x k ∈ B k and x i ∈ B k if i = k . Moreover, B k is disjoint from the (m − 1)face of σ opposite of x k , i.e. from the face having as its vertices the points x i with i = k . The sets B k naturally correspond to the vertices of σ, and it is convenient to reflect this in the notations. Given a vertex v of σ, let B v Now, let S be a geometric simplicial complex and let V be the set of its vertices. The (closed) barycentric star of a vertex is the union B v of the sets B v (σ) over all simplices σ of S having v as a vertex. Clearly, the sets B v form a closed covering of S .
We claim that if some point of the set B v belongs to a simplex τ of S , then v is a vertex of τ. Suppose that x ∈ B v . Then x ∈ B v (σ) for some simplex σ having v as a vertex. If x belongs to τ, then x ∈ τ ∩ σ. The intersection τ ∩ σ is a simplex and hence is a face of σ. Since B v (σ) is disjoint from the face of σ opposite to v , it follows that v is a vertex of τ ∩ σ and hence is a vertex of τ. This proves our claim.
Suppose now that X is a subset of V such that the intersection v ∈ X B v is non-empty. Let x be a point in this intersection and let τ be some simplex of S containing x . By the above claim every v ∈ X is a vertex of τ. It follows that X is the set of vertices of some face of τ and hence of a simplex of S . Conversely, if X is the set of vertices of a simplex σ, then, as we saw, this intersection contains the barycenter of σ.
Therefore the order of the covering of S by the sets B v is equal to the maximal number of vertices of a simplex of S , i.e. is equal to n + 1, where n is the dimension of S . Clearly, the diameter of each B v is less than twice the maximal diameter of a simplex of T .
Theorem 3. For every ε > 0 there exists a closed ε-covering of δ of the order n + 1.
Proof. Let us apply the above construction to a triangulation T of δ in the role of S . If the diameter of simplices of T is < ε/2, then the covering by the sets B v is an ε-covering. ■ Brouwer's invariance of dimension theorem. If m < n , then no subset of R n with nonempty interior is homeomorphic to a subset of R m . In particular, R n is not homeomorphic to R m if n = m .
Proof. Any subset of R n with non-empty interior contains a geometric n-simplex, and hence it is sufficient to prove that the n-simplex δ is not homeomorphic to a subset of R m if m < n . If h is a homeomorphism between δ and X ⊂ R m , then X is compact together with δ and hence is contained in a geometric m-simplex. By Theorem 3 the latter admits closed ε-coverings of order m + 1 for every ε > 0. Since δ is compact and hence h is uniformly continuous, transplanting these coverings by h to δ leads to closed ε-coverings of δ of order m + 1 for every ε > 0, contrary to Lebesgue-Sperner theorem. ■ Invariance of dimension for polyhedra. Let S , Q be geometric simplicial complexes of dimensions n , m respectively. If n = m , then S and Q are not homeomorphic.
Proof. If S is homeomorphic to Q , then an open subset of an n-simplex of S is homeomorphic to a subset of a k-simplex of Q with k m . By the previous corollary this implies that k n and hence m n . Similarly, n m . ■

Brouwer's invariance of domain theorem
Brouwer's invariance of domain theorem. The goal of this section is to apply the tools developed in Section 3 to prove another famous theorem of Brouwer, namely, to prove that if two subsets of R n are homeomorphic and one of them is open, then the other is also open.
The proof is based only on Lebesgue-Sperner theorem, which is a version of Lebesgue tiling theorem, and elementary constructions of closed coverings (including the existence of subdivisions into small simplices). It is largely due to Lebesgue [L1], [L2].
Lebesgue endeavor to prove the invariance of domain theorem using only properties of coverings by closed sets was quite audacious, and it is not very surprising that his arguments contained a gap. The gap was filled by Sperner [S], but not without a price: the resulting proof is dominated by the technical details. In our presentation the arguments filling that gap are separated from the rest of the proof as the technical lemma below. Its proof is based on Sperner [S], but differs in details, in particular, in the way the compactness is used. The rest is based on a modernized version of Lebesgue ideas [L1], [L2].
Systems of sets differing in a subset. Let (5) be a system of sets in R d , and let Z be a subset of R d . A system of sets differs from (5) only in Z if it consists of subsets of Z and sets Technical lemma. Suppose that (5) is a covering of the order n of a compact set X ⊂ R d and that S is a geometric simplicial complex of dimension n − 1. Then there is a covering of the union X ∪ S which has order n and differs from (5) only in S .

Proof.
For every i = 1, 2, . . . , s let D i = F i ∩ S . Some of the sets D i may be empty, but they form a closed covering of X ∩ S with the order n . Let e > 0 be smaller than a Lebesgue number of this covering, and let D i (e ) be the closed e-neighborhood of D i in S , i.e. the set of all points of S with the distance e from D i . If D i is empty, then D i (e ) is also empty. The sets D i (e ) form a closed covering of X ∩ S . If x ∈ X and x belongs to the intersection of several sets D i (e ), then the distance of x from each of the corresponding sets D i is e . By Lebesgue lemma these sets D i have non-empty intersection. It follows the order of the covering by the sets D i (e ) is n .
There exists a subdivision S of S consisting of simplices of diameter < e/2 (see Section 3). By applying the construction of coverings from Section 3 to S in the role of S , we get a closed e-covering of S = S . Let A 0 , A 1 , . . . , A p be the sets of this covering intersecting X ∩ S and let B 0 , B 1 , . . . , B q be the sets disjoint from X ∩ S .
Every A k intersects X ∩ S , and hence intersects at least one of the sets D i . Let D i (k ) be one of these sets intersecting A k , and let form a closed covering of X ∪ S which differs from (5) only in S . It remains to prove that the order of this covering is n , i.e. that every point x ∈ X ∪ S belongs to n sets (7). There are several cases to consider.
If x ∈ X , then none of the sets D i contains x . At the same time x belongs to no more than n sets A k , B l . In (7) some sets A k are merged together into one set D i , but are never split. Therefore in this case x also belongs to no more than n sets (7).
Since the order of (5) is n , in this case x belongs to n sets (7).
Since the order of the covering by the sets D i (e ) is n , in this case x belongs to n sets D i (e ), and hence to n sets (7). ■ Theorem 4. Let X be a compact subset of R n . Suppose that (8) F 0 , F 1 , F 2 , . . . , F s is closed covering of X such that its order is equal to n + 1 and only one point y belongs to n + 1 sets (8). If y belongs to the boundary of X , then for every open set U ⊂ R n containing y there exists a covering of X of order n which differs from (8) only in U .
Proof. Let σ be a geometric n-simplex contained in U and containing y in its interior int σ = σ bd σ. Since y is a boundary point of X , there exist a point y contained in int σ but not contained in X . Let X = X int σ and let r : X −→ X ∪ bd σ be the map equal to the identity on X and to the radial projection from y to bd σ on X ∩ σ. It is well defined because y ∈ X . In more details, if x ∈ X ∩ σ, then r ( x ) is the point of the intersection with bd σ of the ray starting at y and passing through x .
The sets E i form a closed covering of X with the order n (since the only point belonging to n + 1 sets is removed). By the technical lemma, there exists a closed covering G of the union X ∪ bd σ with the order n which differs from the system of sets E i only in bd σ. The collection of preimages r − 1 (G) of the sets G ∈ G is a closed covering of X . Clearly, its order is n .
It remains to check that this collection of preimages differs from (8) only in U. Actually, it differs from (8) All other sets G from the covering G are contained in bd σ, and hence their preimages r − 1 (G) are contained in σ. It follows that the collection of preimages indeed differs from (8) only in σ. ■ Brouwer's invariance of domains theorem. Suppose that Y , X ⊂ R n and h : Y −→ X is a homeomorphism. If z belongs to the interior of Y , then h ( z ) belongs to the interior of X.

In particular, if Y is an open subset of R n , then X is also an open subset.
Proof. Suppose that y = h ( z ) belongs to the boundary of X. Let us choose a geometric n-simplex τ in R n such that τ is contained in the interior of Y and the point z is the barycenter (see Section 3) of τ. In Section 3 we constructed a canonical closed covering F of τ by n + 1 sets. The covering F has order n + 1 and there is only one point, namely, the barycenter z of τ, which belongs to n + 1 sets of F . In addition, the covering F obviously satisfies the assumptions of Lebesgue-Sperner theorem. The image of F under h is a closed covering F of h (τ) of order n + 1 and y = h ( z ) is the only point belonging to n + 1 sets of F . Since the point y belongs to the boundary of X, it belongs to the boundary of h (τ) also. Let U be an open neighborhood of h ( z ) such that the preimage h − 1 (U ) is contained in the interior int τ = τ bd τ. Since bd τ = S for an (n − 1)dimensional complex S , Theorem 4 implies that there is a closed covering of h (τ) with the order n which differs from F only in U . The preimage G of this covering under h is a closed covering of τ. Clearly, its order is n and it differs from F only in h − 1 (U ).
Let G be an element of G containing some vertex of τ. Let us replace G by the union of G and all elements of G contained in h − 1 (U ), remove from G the latter elements, and denote by G the resulting covering of τ. Since h − 1 (U ) ⊂ int τ and F satisfies the assumptions of Lebesgue-Sperner theorem, G also satisfies these assumptions and hence its order is n + 1. But the previous paragraph implies that the order of G is n . ■

Remark.
Lebesgue overlook the need to modify and expand the covering of X ∩ S by the sets D i in the situation of Theorem 4, i.e. when S = bd τ and (5) is the image of F .

Brouwer's fixed-point theorem
Open stars. Let σ be a geometric m-simplex and let v be a vertex of σ. The (m − 1)-face of σ having as its vertices all vertices of σ except v is called the face opposite to v . We already informally used this notion and called δ i the face of δ opposite to v i . If σ has dimension 0, i.e. consists of the point v , then v has no opposite face (alternatively, one can consider the empty set as the face opposite to v ). Proof. Since σ is the carrier of x , no proper face of σ contains x . It follows that x be- S ), then x belongs to some simplex τ having v as a vertex, but not to its face opposite to v . Since σ is the minimal simplex containing x , it is contained in τ, and since x ∈ σ, it cannot be contained in the face opposite to v . It follows that v is a vertex of σ. Proof. If x belongs to this intersection and σ is the carrier of x , then all w i are vertices of σ. Conversely, if σ is a simplex with the set of vertices { w 0 , w 1 , . . . , w m }, then σ is the carrier of every x ∈ σ bd σ and hence σ bd σ is contained in this intersection. ■

Simplicial approximations. Let S , Q be simplicial complexes and
for every vertex v of S. Usually f admits no simplicial approximations. But if we allow to replace S by its subdivisions, the simplicial approximations always exist. The proof is based on a version of Lebesgue lemma from Section 3.

Lebesgue lemma for open coverings. Suppose that
is an open covering of a compact set X . Then there is a number ε > 0 with the following property: if the diameter of a subset Y of X is < ε, then Y is contained in U i for some i ∈ I . Every such number ε > 0 is called a Lebesgue number of the covering U .
Proof. Let F i = X U i for every i ∈ I . The sets F i are closed. Arguing by contradiction, suppose that for every natural number m there is a set Y m ⊂ X of diameter 1/m not contained in any U i . Then Y m intersects every F i . Let us choose some points y m ∈ Y m . Then the distance of y m from every F i is 1/m . Since X is compact, we can assume that the points y m converge to a point y ∈ X . Then the distance of y from each set F i is equal to 0. Since these sets are closed, y belongs to every F i , and hence does not belong to any U i . But this contradicts to the assumption that U is a covering. ■

Lemma. Suppose that S is a subdivision of S and S
−→ S is the identity map. Every simplicial approximation ϕ : S −→ S of this identity map is a pseudo-identical map.
Proof. By the definition, ϕ is a simplicial approximation of the identity if and only if for every vertex v of S . Clearly, (9) implies that v ∈ st (ϕ( v ), S ). This means that there is a simplex σ of S having ϕ( v ) as a vertex and such that v belongs to σ but not to the face of σ opposite to ϕ( v ). It follows that the carrier of v in S has ϕ( v ) as a vertex. Since v is an arbitrary vertex of S , this means that ϕ is a pseudo-identical map. ■

Remark.
The converse is also true, but is less useful and we do not need it.
The no-retraction theorem. There exists no retraction δ −→ bd δ, i.e. no continuous map r : δ −→ bd δ which is equal to the identity on bd δ.
Proof. Suppose that r : δ −→ bd δ is a continuous map equal to the identity on bd δ. The sets δ and bd δ are equal to polyhedra ∆ and bd ∆ respectively. By the simplicial approximation theorem there exists a subdivision T of the complex ∆ such that the continuous map r admits simplicial approximation ϕ : T −→ bd ∆.
The restriction bd ϕ : bd T −→ bd ∆ of ϕ is a simplicial approximation of the restriction of r to the boundary bd δ, i.e. a simplicial approximation of the identity map of bd δ. By the last lemma the restriction bd ϕ is a pseudo-identical map.
We claim that ϕ considered as a simplicial map T −→ ∆ is a pseudo-identical map. Let v be a vertex of T . If v ∈ bd δ, then ϕ(v ) is a vertex of carrier of v because bd ϕ is a pseudo-identical map. If v ∈ δ bd δ, then the carrier of v is δ and ϕ(v ) is tautologically a vertex of δ. This proves our claim. Then v ∈ σ and hence there exists i ∈ I such that v ∈ F i and v i is a vertex of σ. Let us choose an arbitrary such i and set ϕ( v ) = v i . By the construction, ϕ is a pseudoidentical simplicial map. The rest of the proof is the same as before. ■

Notations.
Let us fix a continuous map f : δ −→ δ. For a point a ∈ δ we will denote by ( a 0 , a 1 , . . . , a n ) and be the barycentric coordinates of a and b = f ( a ) respectively.

A proof of Brouwer's fixed-point theorem by KKM argument.
For i ∈ I let F i be the set of points a ∈ δ such that b i a i . Clearly, the sets F i are closed.
Suppose that J ⊂ I and a belongs to the face of δ having { v i | i ∈ J } as its set of vertices. Then the barycentric coordinate a i can be non-zero only for i ∈ J and hence i ∈ J a i = 1 .
If a does not belong to any F i with i ∈ J, then b i > a i for every i ∈ J and hence The contradiction shows that a ∈ F i for some i ∈ J. It follows that the sets F i satisfy the assumptions of KKM theorem and hence the intersection of all these sets is non-empty. If a belongs to this intersection, then b i a i for all i ∈ I. Since the sum of barycentric coordinates of every point is equal to 1, this implies that a = b = f ( a ), i.e. that a is a fixed point of the map f . ■ Remarks. This proof is due to Knaster-Kuratowski-Mazurkiewich [KKM]. Thanks to this proof a minor strengthening of Lebesgue-Sperner theorem became known as Knaster-Kuratowski-Mazurkiewich or KKM theorem. There is no doubt that Sperner would easily prove this theorem, would a need arise. But he was interested in the invariance of dimension and domain theorems, and his version of Lebesgue ideas, which we called Lebesgue-Sperner theorem, is precisely tailored for his goals.
The Knaster-Kuratowski-Mazurkiewich argument, used to deduce Brouwer's fixed-point theorem from KKM theorem, is striking. The dependence on KKM theorem could be easily eliminated (see another proof below), but KKM argument strongly contrasts with conventional proofs, invariably reducing the fixed-point theorem to the no-retraction theorem.
It turns out the standard construction of a retraction from a map without fixed points is still present in KKM argument, but in a veiled form. Moreover, KKM argument turns out to be similar to the proof of the no-retraction theorem based on the simplicial approximation theorem. In order to unveil the retraction and explain this similarity, we need to rewrite KKM argument as a proof by contradiction starting with assuming that f has no fixed points. As a byproduct, this will eliminate the dependence on KKM theorem.

A version of the KKM proof.
Arguing by contradiction, suppose that f has no fixed points. Then b = a for every a ∈ δ. For i ∈ I let U i be the set of points a ∈ δ such that b i < a i . The sets U i are open, but this is irrelevant for the proof. Since b = a and there exists i ∈ I such that b i < a i . Therefore the sets U i form a covering of δ. For every i the (n − 1)-face δ i of δ is defined by the equation a i = 0. Since the barycentric coordinates are 0, if a ∈ δ i , then a ∈ U i . In other words, U i is disjoint from δ i . Let T be a triangulation of δ. For every vertex v of T there is at least one vertex v i of δ such that v ∈ U i (because the sets U i form a covering). Let ϕ( v ) be one of them.
If v belongs to a face σ of δ and v k is not a vertex of σ, then σ ⊂ δ k and hence σ is disjoint from U k . Therefore v ∈ U k and hence ϕ( v ) = v k . It follows that ϕ is a pseudoidentical map. By Alexander's lemma there exists a simplex τ of T such that ϕ(τ) = δ. By the construction of ϕ, the simplex τ intersects every set U i .
Let ε > 0. By taking as T a triangulation of δ consisting of simplices of diameter < ε we conclude that there exists a set of diameter < ε intersecting every set U i . Such a set tautologically intersects also the closures of these sets. By applying to these closures Lebesgue lemma for closed sets we see that these closures have a common point. Clearly, if a is such a common point, then b i a i for all i ∈ I. Since the sum of the barycentric coordinates of a point is always 1, it follows that a = b = f ( a ), i.e. a is a fixed point of f , contrary to the assumption that f has no fixed points. The contradiction completes the proof. ■ Adjusting the map f . Assuming that f has no fixed points, we would like to construct a retraction r : δ −→ bd δ. For every x ∈ δ there is a unique ray starting at f ( x ) and passing through x , and we would like to define r ( x ) as the point of intersection of this ray with bd δ. But the point of intersection is not well defined when x and f ( x ) belong to the same proper face of δ. This difficulty is easy to deal with. If f (δ) is contained in the interiour int δ = δ bd δ, then r is well defined. Since there are maps arbitrarily close to f with the image contained in int δ, and every map sufficiently close to f has no fixed points, one can assume that f (δ) ⊂ int δ and hence r is well defined.
Bringing forward the retraction r . The central element of the proof is the choice of a simplicial map ϕ : T −→ ∆. The key and the most original feature of the KKM argument is the condition imposed on this choice: given a vertex v of T , one can take as ϕ( v ) any vertex v i such that v ∈ F i , or v ∈ U i in the second version of the proof.
These conditions can be easily restated in terms of r . We limit ourselves by v ∈ U i . Let Λ i ( a ) be the set of points z ∈ bd δ such that z i > a i , where ( z 0 , z 1 , . . . , z n ) are the barycentric coordinates of z . Then a ∈ U i if and only if r ( a ) ∈ Λ i ( a ). Therefore, in the (second version of the) KKM argument one can take as ϕ( v ) any vertex v i such that The set Λ i has the advantage of being independent of a , and one may try to allow as ϕ( v ) any vertex v i such that This condition turns out to be too weak to complete the proof along the lines of the KKM argument. Namely, by Lebesgue lemma for closed sets there is a point a ∈ δ such that r ( a ) belongs to the closure of Λ i for every i ∈ I. But the closures of the sets Λ i have nonempty intersection (equal to the union of all bd δ i ), and we fail to reach a contradiction. One can deal with this problem by requiring that not only r ( v ) ∈ Λ i , but also If the diameters of the simplices of T are less than the Lebesgue number of the open covering of δ by the preimages r − 1 (Λ i ), then such i ∈ I always exists. In this case Alexander's lemma implies that ϕ(σ) = δ for some simplex σ of T . Since int σ is contained in the open star of every vertex of σ, the image r ( int σ ) is contained in Λ i for every i ∈ I. But the intersection of the sets Λ i is obviously empty. We reached the desired contradiction.
The sets Λ i are the open stars st (v i , bd ∆), and hence the condition (12) is equivalent to ϕ being a simplicial approximation of r . We are back to the proof from Section 5. So, the only essential difference of the KKM argument from that proof is the choice of the condition (10) instead of (12) as the strengthening of the naive condition (11).

Homology groups and their topological invariance
∂∂-theorem. ∂ • ∂ = 0. In more details, the composition of the boundary operators is equal to 0 for every simplicial complex S and every m .
Proof. Clearly, the versions dealing with geometric and with abstract simplicial complexes are equivalent, and we can assume that S is an abstract simplicial complex. For an n-simplex σ and a vertex v ∈ σ let us denote by σ − v the (n − 1)-face σ { v } of σ. It is sufficient to prove that ∂( ∂σ ) = 0 for every simplex σ. Clearly, where the last sum is taken over all ordered pairs ( v , w ) of distinct vertices of σ. Every face of σ of the form σ { v , w }, where v = w , enters into this sum twice. Since we are working over F 2 , this implies that ∂( ∂σ ) = 0, completing the proof. ■ Cycles, boundaries, and homology. The identity ∂ • ∂ = 0 is the heart of algebraic topology. It is an algebraic form of a simple geometric idea: the boundary of a geometric figure, considered as a geometric figure in its own right, has no boundary. Informally, "cycles" are geometric figures with no boundary. The boundaries are cycles by a trivial reason, and one may ask if there are other cycles. This naturally leads to treating two cycles as equivalent when, taken together, they form a boundary. These vague ideas can be made precise only if we specify the class of "geometric figures" considered. In our context an appropriate class of "geometric figures" is formed by chains of a simplicial complex (compare Section 1). ]. The first step toward the proof of the topological invariance of homology groups is to prove that this map is an isomorphism when S is the so-called barycentric subdivision.

Let S be a simplicial complex and
Barycentric subdivisions. For every geometric simplicial complex S there is a canonical subdivision bS of S, called the barycentric subdivision. See Appendix 1. Here we only review the main properties of bS. Passing from S to bS decreases the maximal diameter of simplices by the factor n/(n + 1), where n is the dimension of S. Therefore, by iterating the construction of the barycentric subdivision one can construct for every ε > 0 a subdivision S of S such that the diameter of every simplex of S is < ε. See Appendix 1. Alexander [A2] observed that bS itself can be constructed by iterating a simpler operation of taking a stellar subdivision and proved that for stellar subdivisions the homology subdivision map is an isomorphism. This implies that the homology subdivision maps are isomorphisms for simple and iterated barycentric subdivisions. Alexander's proof is purely combinatorial, but fairly technical. It is presented in Appendix 2. where the dashed vertical arrows s , s , q are the homology subdivision homomorphisms.
By Section 5 the composition ϕ • ϑ is a simplicial approximation of the composition f • g , i.e. of the identity map of Q . Similarly, ϑ • ψ is a simplicial approximation of g • f , i.e. of the identity map of S . Now the second lemma from Section 5 implies that ϕ • ϑ and ϑ • ψ are pseudo-identical maps.
Clearly, ϕ * • ϑ * = (ϕ • ϑ) * and hence Alexander's lemma implies that for every chain α of Q. It follows that if α is a cycle and h is its homology class, then ], this means that ϕ * * • ϑ * * • q is the identity homomorphism of H m (Q ).
Since q is an isomorphisms, this implies, in particular, that ϑ * * is injective.
A completely similar argument shows that ϑ * * • ψ * * • s is the identity homomorphism of H m (S ). Since s is an isomorphisms, this implies, in particular, that ϑ * * is surjective.
It follows that ϑ * * is bijective and hence is an isomorphism H m (S ) −→ H m (Q ). This already implies that the homology groups H m (S ) and H m (Q ) are isomorphic. Since the composition ϕ * * • ϑ * * • q is the identity homomorphism and q is an isomorphism, this implies that ϕ * * is also isomorphism. ■ The isomorphism of homology groups induced by a homeomorphism. The proof of the topological invariance theorem for homology groups proves more than the isomorphism of the groups H m (S ) and H m (Q ). It shows that a homeomorphism f : S −→ Q leads to an isomorphism H m (S ) −→ H m (Q ), namely, to the isomorphism ϕ * * • s . Moreover, this isomorphisms depends only on f . It is called the isomorphism induced by f .
The proof is based on the same ideas and to a big extent is contained in the proof of the topological invariance theorem itself. We need the following two lemmas. The first one is almost contained in the proof of the topological invariance theorem. The second one is a basic fact about the existence of simplicial approximations.

Lemma. Under the assumptions of the topological invariance theorem for homology groups, the map ϕ * * does not depend on the choice of the simplicial approximation ϕ.
Proof. It is a continuation of the proof of the theorem. Since ϕ * * • ϑ * * • q is the identity map of H m (Q ) and q is an isomorphism, q • ϕ * * • ϑ * * is the identity map of H m (Q ). Therefore q • ϕ * * is the inverse of ϑ * * . But ϑ * * is independent on the choice of ϕ and ϕ * * is independent on the choice of ϑ. Therefore both maps ϑ * * and ϕ * * are independent on the choice of simplicial approximations ϑ, ϕ. ■

Lemma. If S is a geometric simplicial complex and S is a subdivision of S, then the identity map S −→ S admits simplicial approximation S −→ S.
Proof. Let w be a vertex of S and let σ be the carrier of w in S. We claim that for every vertex v of σ. Let us consider some simplex τ of S having w as a vertex. Since S is a subdivision of S, the simplex τ is contained in some simplex ρ of S. The simplex ρ contains w and hence has the carrier σ of w as a face. It follows that σ has v as a vertex.
The intersection of τ with the face of ρ opposite to v is a face of τ (perhaps, empty) not containing w . Therefore this intersection is contained in the face of τ opposite to w . The inclusion (13)

Remarks.
The same construction applies if f is only a continuous map and leads to a homomorphism H m (S ) −→ H m (Q ), called the homomorphism induced by f and usually denoted by f * . It is also independent on the choices involved in its construction, but the proof is more technical than the above one and involves other ideas. The above proof is an apparently unintended application of Alexander's methods [A2].

Sperner's lemma and its combinatorial proof
Sperner colorings. We continue to use the notations introduced at the beginning of Section 2. Let V = v (T ) be the set of vertices of the triangulation T , and let V i = v (T i ) be the set of vertices of T i . In other words,

Theorem (Sperner's lemma). If ϕ : v (T ) −→ I is a Sperner coloring, then the number of n-simplices σ of a (T ) such that ϕ(σ) = I is odd. In particular, it is non-zero.
A combinatorial proof. It is due to Sperner and is based on a celebrated double counting argument. Let us fix an element i ∈ I and let N be the number of pairs (τ, σ) such that τ is an (n − 1)-simplex of a (T ) and ϕ(τ) = I − i , and σ is an n-simplex of a (T ) having τ as a face. Let us count such pairs in two ways.
The first way is based on the non-branching property. Since the map ϕ is a Sperner coloring, if τ ⊂ V k for some k and ϕ(τ) = I − i , then k = i and τ ⊂ V i . Let h be the number of (n − 1)-simplices τ ⊂ V i such that ϕ(τ) = I − i and let g be the number of the other (n − 1)-simplices τ such that ϕ(τ) = I − i . By the non-branching property The second way is independent of the non-branching property. If an n-simplex σ has a face τ such that ϕ(τ) = I − i , then either ϕ(σ) = I, or ϕ(σ) = I − i . Let e be the number of n-simplices σ such that ϕ(σ) = I and let f be the number of n-simplices σ such that ϕ(σ) = I − i . If ϕ(σ) = I, then ϕ(τ) = I − i for exactly one face τ if σ. Suppose now that ϕ(σ) = I − i . Since | σ | = n + 1 and | I − i | = n , there is a unique pair a , b ∈ σ such that ϕ( a ) = ϕ(b ) and a = b . Clearly, Hence σ has exactly two (n − 1)-faces such that ϕ(τ) = I − i . It follows that N = e + 2 f . By comparing the two expressions for N, we see that (14) h + 2 g = e + 2 f .
Let us now use an induction by n . Sperner's lemma is trivially true for n = 0. Suppose that n > 0. The simplices of a (T i ) are nothing else but the simplices of a (T ) contained in V i . The map ϕ induces a map ϕ i : V i −→ I − i . Renumbering the elements of the set I − i by 0, 1, . . . , n − 1 turns ϕ i into a Sperner coloring. Hence the inductive assumption implies that the number of (n − 1)-simplices τ of a (T i ) such that ϕ i (τ) = I − i is odd. But this number is equal to h . Therefore the equality (14) implies that e is odd. This completes the induction step and hence the proof. ■

Remark.
Strictly speaking, there is no such statement in Sperner's paper [S], but there is the same proof, up to the language and notations. Sperner starts with a closed covering of δ by n + 1 sets satisfying the assumptions of Lebesgue-Sperner theorem (see Section 3) and chooses ϕ in the same way as in its proof. "Sperner's lemma" appeared for the first time in Knaster-Kuratowski-Mazurkiewicz paper [KKM] as the "combinatorial core of Sperner's new proof of the invariance of dimension". The authors of [KKM] also modified the proof. They considered only the numbers e and h and worked modulo 2, in contrast with Sperner.
Remark. The second method of counting is parallel to the proof of Theorem 1. The case ϕ(σ) = I corresponds to Case 1 of that proof, and the case ϕ(σ) = I − i corresponds to Case 3. The case when the dimension of ϕ(σ) is n − 2 would correspond to Case 2, but such simplices σ do not occur in pairs (τ, σ) such that ϕ(τ) = I − i .

Sperner colorings as simplicial maps.
Recall that ∆ is the simplicial complex consisting of simplex δ and all its faces. Let us identify the vertices v i of δ with their subscripts i ∈ I . This turns a Sperner colorings ϕ into a map v (T ) −→ v (∆) = I. Since every subset of v (∆) is a simplex of a (∆), this is a simplicial map T −→ ∆. A simplicial map ϕ : T −→ ∆ is a Sperner coloring if and only if for every i ∈ I it takes each vertex of T belonging to δ i into an element of I − i , i.e. into a vertex of δ i .
Since every proper face of δ is equal to the intersection of several (n − 1)-dimensional faces δ i , this condition implies that ϕ maps the set of vertices of T belonging to a face τ of δ into the set of vertices of τ. It follows that ϕ : v (T ) −→ v (∆) is a Sperner coloring if and only if ϕ is a pseudo-identical simplicial map T −→ ∆. Now Sperner's lemma takes the following form.

Cochains and Sperner's lemma
The combinatorial proof and algebraic topology. The goal of this section is to show that not only Sperner's lemma admits a natural topological interpretation, but its combinatorial proof is also a topological proof in disguise. The proof of Alexander's lemma (i.e. of Theorem 3) depends on Theorem 1 and hence indirectly contains a part of the combinatorial proof (see the second remark in Section 7). Also, the induction by n is used in both proofs in an essentially the same manner. Still, the proofs look quite different.
The induced maps ϕ * are a good tool to deal with the images of simplices under a simplicial map ϕ. But the combinatorial proof of Sperner's lemma operates not with the images but with the preimages, the sets of simplices mapped by ϕ to particular simplices in the target complex, namely, to the simplices I and I − i of a (∆).
This suggests to dualize the notions of induced maps and boundary operators in the sense of the linear algebra over the field F 2 and leads to the notion of cochains. The reader should keep in mind that this motivation is an artificial one. The cochains were introduced in 1935 by completely different reasons independently by Alexander [A3], [A4] and Kolmogoroff [Ko]. Cochains as formal sums of simplices. Since C m (S ) is a vector space over F 2 having a canonical basis consisting of m-simplices of S , the m-cochains can be identified with F 2valued functions on the set of m-simplices of S . Since all our complexes are assumed to be finite, this basis is finite and can be used to identify the vector space C m (S ) with its dual C m (S ) and interpret cochains, like chains, as formal sums of simplices.

Cochains. For a simplicial complex S and a non-negative integer m let
In what follows, we write cochains as formal sums of simplices, but keep the notation C m (S ) as an indicator showing that we treat these formal sums as cochains. The identification of cochains with formal sums of simplices turns the maps ∂ * and ϕ * into the adjoint operators of ∂ and ϕ * respectively with respect to the pairings 〈•, •〉 such that 〈σ, τ〉 = 1 if σ = τ and 〈σ, τ〉 = 0 if σ = τ .
A trivial verification shows that if τ is an (m − 1)-simplex of S, then where the sum is taken over all m-simplices σ having τ as a face. Hence the coboundary operator ∂ * , like the boundary operator ∂, encodes the relation " τ is a face of σ" between simplices τ, σ such that the dimension of τ is less by 1 than the dimension of τ.
Similarly, if ϕ : S −→ S is a simplicial map and ρ is an m-simplex of S , then where the sum is over all m-simplices τ of S such that ϕ(τ) = ρ, as another trivial verification shows. In other words, ϕ * (ρ) indeed encodes the preimage of ρ.
Proof. This immediately follows from Theorem 1 by dualizing. One can also give a direct proof based on (15) and (16). We leave this task to the interested readers as an exercise. ■

A cochains-based proof of the simplicial form of Sperner's lemma.
We are going to partially dualize the proof of Alexander's lemma. The latter is based on Theorems 1 and 2, the equality (3), and Lemma from Section 2, a compressed form of the non-branching property. The dualization of Theorem 1 is Theorem 1*. Theorem 2 and the equality (3) cannot be straightforwardly dualized, but if we fix some i ∈ I, then the obvious equality (17) ∂ * δ i = δ turns out to be a reasonable substitution for (3). By Theorem 1* and together with (17) this implies that Instead of Lemma from Section 2 we will use the non-branching property directly. Let us explicitly compute the cochains in (18) and relate them to the numbers e , f , g , h from the combinatorial proof. We need the following four sets of simplices.
Let E and F be the sets of n-simplices σ of T such that ϕ(σ) = δ and ϕ(σ) = δ i respectively. The sets E and F consist of e and f elements respectively.
Let H be the set of (n −1)-simplices τ of bd T such that ϕ(σ) = δ i . Since ϕ is a pseudoidentical simplicial map, every such simplex τ is actually a simplex of T i . In particular, H consists of h elements.
Finally, let G be the set of (n − 1)-simplices τ of T such that ϕ(τ) = δ i , but τ is not a simplex of bd T , i.e. τ ∈ H. The set G consists of g elements.
In terms of the sets E, F, G, H the cochains ϕ * (δ) and ϕ * (δ i ) can be written as follows: Therefore we can rewrite (18) as By the non-branching property, if τ ∈ H, then τ is a face of exactly one n-simplex of T , and if τ ∈ G, then τ is a face of exactly two n-simplices of T . In terms of the coboundary operator ∂ * this means that if τ ∈ H, then ∂ * τ is a simplex, and if τ ∈ G, then ∂ * τ is a sum of two simplices. Hence the right hand side of (19) is a sum of h + 2 g simplices.
If some n-simplex σ occurs in this sum at least twice, then σ has at least two (n − 1)-faces τ, τ such that ϕ(τ) = ϕ(τ ) = δ i . In this case ϕ(σ) = δ i and ϕ(τ ) = δ i for any other face τ of σ. Therefore, in this case σ ∈ F and σ occurs in the sum exactly two times. Conversely, if σ ∈ F, then σ has two such faces and hence σ occurs in this sum twice. In other words, pairs of equal simplices at the right hand side of (19) correspond to elements of F and there are f such pairs. Over F 2 such pairs cancel.
There are no other cancellations and hence the right hand side of (19) is equal to a sum of h + 2 g − 2 f distinct simplices. At the same time the left hand side of (19) is obviously a sum of e distinct simplices. Therefore (19) implies that It follows that e ≡ h modulo 2. Now one can use induction by n to complete the proof. ■ (18) is proved, one can use the non-branching property in the form of Lemma from Section 2. This leads to a proof closer to Alexander's one. By pairing both sides of (18) with [[δ]] we see that

An alternative ending. After the equality
Together with the definition of ∂ * this implies that It follows that the right hand side of (21) is equal to the taken modulo 2 number of simplices τ of bd T such that ϕ(τ) = δ i . But since ϕ is a pseudo-identical simplicial map, every such simplex τ is a simplex of T i . Hence the right hand side of (21) is equal to h modulo 2. Similarly, the left hand side of (21) is equal to e modulo 2. Now (21) implies that e ≡ h modulo 2 and one can complete the proof by using an induction by n . ■ The cochains-based proofs and the combinatorial proof. The equality (20) from the cochains-based proof is trivially equivalent to the equality (14) around which the combinatorial proof is centered. The equality (19) between cochains is a realization (or a lift to the linear algebra) of the equalities (20) and (14) between numbers, and the whole cochains-based proof is essentially the combinatorial proof rewritten in the spirit of the linear algebra methods in combinatorics. But from the point of view of a topologist both these proofs are hardly satisfactory, in contrast with Alexander's one.
On the one hand, the numbers f , g and the number of cancellations are irrelevant to the problem at hand. The alternative version of the cochains-based proof is better in this respect (at the cost of being further from Sperner's one

Graph-theoretical interpretation of the cochains-based proof.
There is a widespread opinion that the classical proofs of Sperner's lemma are pure existence proofs. In fact, an analysis of these proofs naturally leads to an algorithm leading to a simplex σ such that ϕ(σ) = δ. Let us begin with such an analysis of one step of induction in the cochains-based proof. In this analysis we will freely use the notations introduced in this proof.
The equality (20) was proved by counting the number of cancellations in the equality (19). But this counting was based on determining what simplices do actually cancel. A convenient way to record this more detailed information is to introduce an appropriate graph G i , where i ∈ I is the element fixed at the beginning of the proof. This graph has two kinds of vertices. The vertices of the first kind are (n − 1)-simplices belonging to the union G ∪ H. The vertices of the second kind are n-simplices belonging to the union E ∪ F. A vertex τ ∈ G ∪ H is connected to a vertex σ ∈ E ∪ F if τ is an (n − 1)-face of σ. There are no other edges.
The graph G i encodes all relevant information about the equality (19). Indeed, the elements of G ∪ H correspond to the summands at the right hand side of (19). The elements of E correspond to the summands at the left hand side of (19), and the elements of F correspond to the cancellations at the right hand side. Finally, a vertex τ ∈ G ∪ H is connected to a vertex σ ∈ E ∪ F if and only if σ is a summand of the coboundary ∂ * (τ).
The main properties of G i are the following. By the non-branching property, every vertex in G is an endpoint of exactly two edges, and every vertex in H is an endpoint of exactly one edge. Clearly, every n-simplex in E has exactly one face belonging to G ∪ H and hence is an endpoint of exactly one edge. Also, every n-simplex in F has exactly two faces belonging to G ∪ H and hence is an endpoint of exactly two edges. In particular, every vertex of G i is an endpoint of either one or two edges. It follows that G i consists of several disjoint paths and cycles. Clearly, every path connects two vertices in the union E ∪ H, and every vertex in this union is an endpoints of a path. Therefore the number of elements of E ∪ H, i.e. e + h , is even and hence e ≡ h modulo 2. We see that the inductive step in the cochains-based proof can be rephrased in terms of the graph G i .
The graphs G i in the combinatorial proof. In order to match the above discussion, let us switch from the abstract complex a (T ) to the geometric complex T. The combinatorial proof is based on counting pairs (τ, σ) such that τ is an (n − 1)-simplex of T and ϕ(τ) = δ i , and σ is an n-simplex of T having τ as a face. Clearly, the simplices τ occurring in such pairs are exactly the elements of G ∪ H, i.e. the vertices of the first kind of the graph G i . The simplices σ occurring in such pairs are exactly the elements of E ∪ F, i.e. the vertices of the second kind of the graph G i . The pair (τ, σ) is among the counted pairs if and only if τ and σ are connected by an edge in G i . We see that the graph G i is present in the combinatorial proof even more explicitly than in the cochains-based one.
Searching for elements of E. The graph-theoretical version of the proof is very attractive, especially because it suggests a way of finding elements of E, i.e. the n-simplices σ such that ϕ(σ) = δ. Indeed, since both sets E and H have an odd number of elements, there is at least one path starting in H and ending in E. Following a path in G i can be easily turned into an algorithm, but at the first sight such an algorithm is hardly satisfactory: it seems that in order to find in this way even one element of E one needs to know all elements of H. Still, at the very least one can replace an exhaustive search among the n-simplices of T by an exhaustive search among the (n − 1)-simplices of T i plus following several paths.
A moment of thought leads to the conclusion that one shouldn't expect that simply following paths starting in H would be a satisfactory search strategy. Indeed, this method does not fully reflect even the inductive step: the fact that elements of E not reachable in this way are pairwise connected by paths of G i is equally important. Even more importantly, the graph G i encodes only one step of the induction, and one step is not sufficient even to establish that n-simplices σ such that ϕ(σ) = δ exist. The proof of the existence implicitly involves a similar graph related to the (n −1)-face δ i of δ, a graph related to an (n −2)-face of δ i , etc. One can combine the corresponding path-following algorithms (including paths connecting one element of E with another for proper faces of δ in the role of δ ), but there is a better approach. Namely, one can concatenate all relevant graphs into a single graph.
There are no other vertices. Two vertices σ, τ as above are connected by an edge if τ is an (m − 1)-face of σ. There are no other edges. Note that if an (m − 1)-simplex τ as above is contained in δ m − 1 , then τ is connected by an edge to some (m − 2)-simplex of T m − 1 . If δ n − 1 = δ i , then, obviously, G i is a subgraph of G.
Theorem. Every vertex of G is an endpoint of one or two edges. A vertex σ is an endpoint of only one edge if and only if either σ = δ 0 , or σ is an n-simplex and ϕ(σ) = δ n = δ.
Suppose now that σ is an m-simplex of T m such that ϕ(σ) = δ m − 1 . By the definition, in this case σ is not connected by an edge with any simplex of T m + 1 not belonging to T m . The arguments used for G i with T m in the role of T show that in this case σ is connected with exactly two vertices, both of which are (m − 1)-simplices of T m .
Finally, let us consider an (m − 1)-simplex τ of T m such that ϕ(τ ) = δ m − 1 . If τ is actually a simplex of T m − 1 , then τ is connected by an edge with two vertices by the first paragraph of the proof applied to τ and m − 1 in the roles of σ and m respectively. Otherwise the arguments used for G i with T m in the role of T show that in this case τ is connected with exactly two vertices, both of which are m-simplices of T m . ■

Corollary.
The graph G consists of several disjoint paths and cycles. With exception of δ 0 , the endpoints of these paths are n-simplices σ such that ϕ(σ) = δ. ■

Corollary.
The number of n-simplices σ such that ϕ(σ) = δ is odd. ■ Path-following algorithms. Following the unique path of G starting at δ 0 leads to an nsimplex σ sich that ϕ(σ) = δ. Following this path can be easily turned into an algorithm, which turns out to be equivalent to one of Scarf's algorithms [Sc3]. Cf. [Sc3], Lemma 3.4. In the context of Brouwer's fixed-point theorem such simplices σ may be interpreted as approximate fixed points of continuous maps δ −→ δ, and the path-following algorithms were actually used for computing approximations to fixed points. Cf. [Sc2], [Sc3].
Historical remarks. A proof of Sperner's lemma based on path-following arguments was published in 1967 by D.I.A. Cohen [C]. His proof amounts to using the standard induction by n and the graph G i for the step of induction. Cohen did not relate his proof to any of the classical proofs. In 1979 A.W. Tucker [T] wrote about Sperner's lemma and Cohen's proof: This lemma, proved by a simple existential argument through induction on n , . . . Now, however, we have an algorithmic proof of Sperner's lemma, thanks to an idea of Cohen [C].
Also in 1967 H. Scarf published [Sc2] a proof of Brouwer's fixed-point theorem based on a combinatorial theorem resembling Sperner's lemma. Scarf proved this combinatorial theorem by a path-following algorithm realizing the whole inductive argument. Later on Scarf proved Sperner's lemma in a similar manner. See [Sc3]. In contrast with D.I.A. Cohen, Scarf was quite forthcoming and explained his sources of inspiration. His proof of Brouwer's fixedpoint theorem was a byproduct of his fundamental work in game theory [Sc1] and strongly influenced by linear programming and a paper by C.E. Lemke [Le]. Scarf wrote in [Sc2]: . . . , Sperner's lemma suggests no procedure for the determination of an approximate fixed point other than an exhaustive search of all subsimplices until one is found with all vertices labeled differently. . . . , the algorithm is intimately related to the procedure described by Lemke [Le] for the determination of Nash equilibrium points of two-person nonzero-sum games.
The above path-following proof shows that the classical proofs of Sperner's lemma naturally lead to a proof sharing the main features of Scarf's proof and to the same path-following algorithm. The main difference is in the ways used to piece together all steps of induction. Scarf used the so-called slack vectors, an idea coming from linear programming. This idea works in our context also, but is harder to motivate from a topological point of view.
The graphs G i and Alexander's lemma. Admittedly, one has to be more inventive in order to see these graphs in the proof of Alexander's lemma (see Section 2). Of course, the proof should be specialized to the case S = T, S = ∆. But in this case no (n − 1)-face of δ plays any special role. In fact, this proof more naturally leads to the union U of all graphs G i .
The proof of Alexander's lemma is based on a study of the action of the map ϕ on simplices of T of dimensions n and n − 1. Clearly, only the simplices σ such that the dimension of ϕ(σ) is equal to n or n − 1 matter. One may think that n-simplices σ such that ϕ(σ) is an (n − 1)-simplex are irrelevant because for them ϕ * (σ) = 0. In fact, they are highly relevant because a crucial step in the proof is the application of Theorem 1. The only nontrivial part of the proof of Theorem 1 is exactly the part dealing with such simplices.
So, the proof of Alexander's lemma suggests to consider the graph having as vertices all simplices σ of T such that the image ϕ(σ) is equal either to δ or to one of the (n − 1)-faces of δ. In order to encode the relation "τ is a face of σ" we connect two vertices by an edge when one of them is a proper face of the other. The resulting graph is the union U of graphs G i .
The above graph-theoretical arguments do not apply to the graph U by itself. While some vertices of U are connected by an edge with n + 1 vertices, they are not the source of difficulties. Indeed, they are exactly the vertices σ such that ϕ(σ) = δ. But the parity argument would be destroyed if there are paths in U connecting two (n − 1)-simplices in two different faces of δ without passing through a vertex σ such that ϕ(σ) = δ. The proof of Theorem 1 shows that this never happens. Indeed, Case 3 of this proof shows that if τ, σ are two vertices of U and τ is a face of σ, then either ϕ(σ) = δ, or the images ϕ(σ) and ϕ(τ ) are equal (to the same face δ i , i ∈ I ). Therefore a path in U starting at an (n − 1)-simplex contained in δ i actually stays in G i until it reaches σ with ϕ(σ) = δ.

Cohomology groups
Discarding coboundaries. The pairing with [[δ ]] allows to discard the coboundaries ∂ * (τ) such that τ is a simplex of T , but not of bd T , without any further analysis. It is only natural to discard these coboundaries in a systematic way by taking the quotient space of the vector space of n-cochains by a suitable subspace. In the cohomology theory all coboundaries are discarded in this way. But we need to keep the coboundaries ∂ * (τ) such that τ is a simplex of bd T . A natural way to do this is provided by the relative cohomology theory, a version based on relative cochains. The following theorem is the starting point.

Cocycles
is called the m-dimensional cohomology group of S. The term "cohomology group" is standard even when it is a vector space. The image of a cocycle α ∈ Z m (S ) in the cohomology group H m (S ) is called the cohomology class of α and is denoted by [α].
Relative cohomology. Suppose now that Q is a subcomplex of S , i.e. that every vertex of Q is a vertex of S and every simplex of Q is a simplex of S . A relative m-cochain of the pair (S , Q ) is an m-cochain of S vanishing on every m-simplex of Q if considered as a linear functional C m (S ) −→ F 2 . In the language of formal sums of simplices this means that no simplices of Q are allowed to enter the sum.
Obviously, the coboundary of a relative (m − 1)-cochain is a relative m-cochain. A relative m-cochain α is called a relative cocycle if it is a cocycle as a chain, and a relative coboundary if α = ∂ * ( β) for some relative (m − 1)-cochain β. Let Z m (S , Q ) and B m (S , Q ) be the spaces of relative m-cochains which are relative cocycles and relative coboundaries respectively. Like before, the ∂ * ∂ * -theorem implies that every relative coboundary is a relative cocycle, i.e. B m (S , Q ) ⊂ Z m (S , Q ). The quotient space is called the m-dimensional cohomology group of the pair (S , Q ). The image of a cocycle α ∈ Z m (S , Q ) in H m (S , Q ) is called the cohomology class of α and is denoted by [α].

Pseudo-manifolds.
We are especially interested in the top-dimensional cohomology groups, i.e. in the n-dimensional cohomology groups of complexes S and pairs (S , Q ) with n equal to the dimension of S. There is a class of complexes for which the top-dimensional cohomology groups are easy to determine. See Theorem 6 below. Let S be a simplicial complex of dimension n .
Guided by the non-branching property of triangulations of a simplex, we will say that S is non-branching if each (n − 1)-simplex of S is a face of either one or two n-simplices. If S is non-branching, then the boundary ∂S is defined as simplicial complex having as the simplices all faces of (n − 1)-simplices of S which are faces of exactly one n-simplex.
We will say that S is strongly connected if for every two n-simplices σ, σ of S there is a sequence σ = σ 0 , σ 1 , . . . , σ k − 1 , σ k = σ of n-simplices such that σ l and σ l + 1 have a common (n − 1)-face for every l k − 1.
Usually these two conditions are imposed together with another one. The complex S is said to be dimensionally homogenous if every its simplex is a face of an n-dimensional simplex. This condition is natural, but is hardly relevant for us. The complex S is called a pseudomanifold if it is non-branching, strongly connected, and dimensionally homogeneous.
Triangulations of a simplex. Examples of pseudo-manifolds are provided by triangulations of simplices. Every triangulation T of δ is a pseudo-manifold of dimension n . We already implicitly accepted the non-branching property as geometrically obvious. The fact that T is dimensionally homogenous is also geometrically obvious.
The fact that T is strongly connected is a little less obvious. Let σ, σ be two n-simplices of T . They can be connected by a path in δ. If this path intersects only n-simplices and (n − 1)-simplices of T , then one can read off the required sequence by following this path. If this path intersects an m-simplex with m n − 2, one can replace a segment of this path crossing this m-simplex by a segment bypassing it. We leave the details to the reader.
By the non-branching property of triangulations of δ the boundary ∂T consists of all simplices of T contained in the boundary bd δ. In other words, the boundary ∂T is nothing else but the complex which was denoted by bd T above. Recall that the complex ∆ is the tautological triangulation of δ consisting of δ itself and its faces. The discussion at the beginning of Section 2 implies that ∂T = bd T is a subdivision of ∂∆ and hence the following theorem (applied to S = ∂∆ and S = ∂T ) implies that ∂T is also a pseudo-manifold.

Theorem 5. If a complex S is a pseudo-manifold of dimension n and S is a subdivision of S, then S is also a pseudo-manifold of dimension n .
Proof. Recall that for every simplex σ of S the simplices of S contained in σ form a triangulation S (σ) of σ. As we just saw, S (σ) is a pseudo-manifold and its boundary ∂ S (σ) consists of simplices of S (σ) contained in bd σ. Let τ be an (n − 1)-simplex of S . Since S is a subdivision of S, the simplex τ is contained is some simplex of S .
If τ is contained in an (n − 1)-simplex τ of S, then the simplices σ of S having τ as a face are in 1-to-1 correspondence with simplices σ of S having τ as a face, and hence there are 1 or 2 of such simplices σ . If τ is not contained in any (n − 1)-simplex of S, then τ is contained in a unique n-simplex σ of S and does not belong to ∂ S (σ). In this case τ is a face of exactly two n-simplices of S (σ) and hence of exactly two n-simplices of S .
This proves that S is non-branching. The fact that S is strongly connected follows from the strong connectedness of S and of complexes S (σ). Similarly, S is dimensionally homogeneous because S and S (σ) are. We leave the details to the interested readers. ■ Theorem 6. Let S be a strongly connected non-branching complex of dimension n . Then H n (S , ∂S ) is a vector space of dimension 1. Every n-simplex σ of S is a cocycle and its cohomology class [σ] is non-zero and hence is a basis of H n (S , ∂S ).
Proof. Since n is the dimension of S, every n-cochain is a cocycle and hence To begin with, let us consider a cochain α ∈ C m − 1 (Q ). An extension of α is any cochain α ∈ C m − 1 (S ) resulting from adding to α several (m − 1)-simplices of S not belonging to Q. Every cochain α admits a tautological extension by zero, resulting from adding no simplices. But, as we will see in a moment, the freedom to use other extensions is essential. If α is considered as a linear functional C m − 1 (Q ) −→ F 2 , then an extension of α can be defined as an extension of α to a linear functional C m − 1 (S ) −→ F 2 .
Proof of the correctness. Any two extensions of α differ by a relative cochain of (S , Q ) and hence the coboundaries of any two extensions differ by a relative coboundary. This implies the independence on the choice of extension. Let α 1 , α 2 be two cocycles such that a = [ α 1 ] = [ α 2 ]. Then α 2 − α 1 = ∂ * (ω) for some ω ∈ C m − 2 (Q ).
Let α 1 and ω be arbitrary extensions of α 1 and ω respectively, and let Then α 2 is an extension of α 2 (note that even if α 1 and ω are extensions by zero, the extension α 2 is usually not). Therefore where at the last step we used the ∂ * ∂ * -theorem. Therefore ∂ * ( α 2 ) = ∂ * ( α 1 ) . The independence on the choice of the cocycle α follows. ■ Theorem 7. Let S be a non-branching strongly connected simplicial complex of dimension n . Suppose that ∂S is a non-branching strongly connected complex of dimension n − 1. Then the connecting homomorphism is an isomorphism.
Proof. Let τ be some (n − 1)-simplex of ∂S, and let σ be the unique n-simplex of S such that τ is a face of σ. Let τ be the extension of the cochain τ by zero, i.e. the same τ, but considered as a cochain of S. Then ∂ * ( τ ) = ∂ * (τ) = σ and hence Let Q, Q be subcomplexes of S , S respectively. Suppose that ϕ is simplicial map of pairs (S , Q ) −→ (S , Q ), i.e. that ϕ takes every simplex of Q to a simplex of Q . Then ϕ defines a simplicial map ϕ Q : Q −→ Q , and the induced map ϕ * maps relative cochains of (S , Q ) to relative cochains of (S , Q ). Hence ϕ * defines a maps ϕ * : C m (S , Q ) −→ C m (S , Q ) of relative cochains. Again, Theorem 1* implies that ϕ * maps relative cocycles to relative cocycles and relative coboundaries to relative coboundaries and hence leads to maps of relative cohomology groups. They are also called the induced maps. The maps induced by ϕ and ϕ Q s together with connecting homomorphisms form the following diagram.

Remark.
Suppose that we took as α the extension by zero. If ϕ maps to Q some simplices of S not belonging to Q, then ϕ * ( α ) usually will not be an extension by zero of ϕ * Q (α). This is another illustration of the usefulness of the freedom in the choice of extensions, and we will encounter this situation in the following cohomological proof of Sperner's lemma. The coboundaries ∂ * (τ) to be discarded are discarded here.

A cohomological proof of Sperner's lemma.
Let ϕ : T −→ ∆ be a pseudo-identical simplicial map. Since ϕ is a pseudo-identical map, ϕ leads to the map ϕ ∂T : ∂T −→ ∂∆, which we will denote now by ∂ϕ. Let us consider the following diagram.
By the above lemma it is commutative. By Theorem 6 every cohomology group in this diagram is a vector space of dimension one with the cohomology class of any top-dimensional simplex forming a basis (or, what is the same, being the only non-zero element). In particular, every cohomology group in this diagram is isomorphic to F 2 . If a vector space over F 2 is isomorphic to F 2 , then it is canonically isomorphic to F 2 . Hence we can replace all cohomology groups in our diagram by F 2 and get the following diagram.
Now the commutativity of the last diagram implies that e 1 = h 1 and hence e ≡ h modulo 2. As usual, an induction by n completes the proof. ■

A.1. Barycentric subdivisions
Cones. Let X be a subset of R d and let z be a point in R d . Suppose that segments connecting z with different points of X always intersect only at z . Then the union z * X of all segments connecting z with points of X is called the cone over X with the apex z .
If X is a simplex and z is affinely independent from the vertices of X , then z * X is also a simplex. Its vertices are the vertices of X together with the point z . The faces of z * X are the vertex z , the faces Y of X and the cones z * Y over the faces Y of X .
Geometric simplices as cones over their boundaries. For a geometric simplex σ we will denote by 〈 σ〉 the simplicial complex consisting of σ and all its faces. The boundary ∂〈 σ〉 is the complex consisting of all proper faces of σ. Clearly, 〈 σ〉 = σ and ∂〈 σ〉 = bd σ.
Let σ be a geometric simplex and let z ∈ σ bd σ be a point in the interior of σ. Then segments connecting z with different points of the boundary bd σ intersect only at z and hence σ is a cone over bd σ with the apex z , i.e. σ = z * bd σ.
Let S be a subdivision of the complex ∂〈 σ〉. Then S = ∂〈 σ〉 = bd σ, and every simplex of S is contained in a proper face of σ. It follows for every simplex τ of S the point z is affinely independent from the vertices of τ and hence the cone z * τ is defined and is a geometric simplex. Let us define the cone z * S with the apex z as the collection consisting of z , the simplices of S , and the cones z * τ over the simplices τ of S . Clearly, z * S is a simplicial complex and is a subdivision of 〈 σ〉. The complex S is a subcomplex of z * S and every vertex of z * S is either z or is a vertex of S.
Centers-generated subdivisions. Let S be a geometric simplicial complex. Suppose that for every simplex σ of S a point z (σ) ∈ σ bd σ is chosen. One may think that z (σ) is a sort of a center of σ. Any choice of such centers generates a subdivision c S of S as follows.
For every integer n 0 let S n be the complex consisting of simplices of S having dimension n . Then S 0 is a finite set and S n = S for all sufficiently big n . Let us consecutively construct the subdivisions c S 0 , c S 1 , c S 2 , . . . of S 0 , S 1 , S 2 , . . . respectively. Let c S 0 = S 0 . Suppose that the subdivision c S m of S m is already constructed. Let σ be an (m + 1)-simplex σ of S. Its boundary bd σ is contained in c S m = S n , and simplices of c S m contained in bd σ form a subdivision of ∂〈 σ〉. Let us denote this subdivision by c ∂〈 σ〉. The subdivision c S m + 1 of S m + 1 is the result of adding to c S m the cone z (σ) * c ∂〈 σ〉 for each (m + 1)-simplex σ of S. Clearly, c S m + 1 is a simplicial complex and is a subdivision of S m + 1 . Finally, c S is defined as c S m for any m such that S m = S.
By the construction, every simplex ω of c S m + 1 not contained in c S m has the center z (σ) of some (m + 1)-simplex σ as a vertex, and the other vertices of ω are all contained in a face of σ. It follows that every n-simplex ω of c S has as its vertices the centers z (σ 0 ), z (σ 1 ), . . . , z (σ n ) of simplices σ 0 , σ 1 , . . . , σ n such that σ i − 1 is a face of σ i for all i = 1, 2, . . . , n and hence σ j is a face of σ i if j i . In particular, the combinatorial structure of c S does not depend on the choice of centers z (σ). But the size of simplices of c S depends on the choice of the centers. Let us turn to an efficient in this respect choice of centers. Let S be a geometric simplicial complex, and let us choose the barycenters as the centers of simplices. In other words, let z (σ) = c (σ). The corresponding subdivision c S is called the barycentric subdivision of S and is denoted by bS. As we will see now, passing from S to bS decreases the maximal diameter of simplices by a definite factor. For x ∈ R d , let us denote by | x | be the norm of the vector x . So, x − y is the distance between x , y ∈ R d .

Lemma.
Let σ be an n-simplex in R d , and let w 0 , w 1 , . . . , w n be its vertices. Then for every x ∈ R d and a ∈ σ. The diameter of σ is equal to max i , j w i − w j .
Proof. By the definition of a simplex, where a i 0 for all i and This proves the first statement of the lemma. If x ∈ σ, then the first statement implies that | w i − x | max j w i − w j for every i and hence | x − a | max i , j w i − w j . The second statement follows. ■ Lemma. Let σ be an n-simplex. Then the diameter of every simplex of the barycentric subdivision b〈 σ〉 is than n/(n + 1) times the diameter of σ.

A.2. Stellar subdivisions
Stellar subdivisions. Let S be a simplicial complex and σ be a simplex of S . Let K be the subcomplex of S consisting of simplices of S having σ as a face together with their other faces. Let L be the subcomplex of K consisting of simplices of K not having σ as a face.
Let us choose a point w in the interior σ bd σ of σ and define the cone K = w * L as the collection of simplices consisting of w , the simplices of L, and the cones w * τ with τ running over the simplices of L. Clearly, K is a simplicial complex. As we will see in a moment, K = K , i.e. K is a subdivision of K . The readers feeling that this is obvious are advised to skip the proof of the next lemma.
Let us replace in S the simplices of K by the simplices of K . Since K is a subdivision of K , the result S is a subdivision of S , called the stellar subdivision of S with the center w .
Proof. By the construction, K ⊂ K . Let us prove the opposite inclusion. Given a point x ∈ K , let us consider the ray starting at w and going in the direction of x . The intersection of this ray with K is a segment J containing x and having w as one of its endpoints. Let z be the other endpoint of J, and let τ be the smallest simplex of K containing z . Then z belongs to the interior of τ. If τ has σ as a face, then w ∈ τ and the whole segment J is contained in τ. Moreover, since z is in the interior of τ, the segment J can be extended without leaving K and hence cannot be the intersection of our ray with K . The contradiction shows that σ is not a face of τ and hence τ is a simplex of L. It follows that x ∈ w * τ ⊂ w * L. Since x ∈ K was arbitrary, this proves that K = K . ■ Stellar subdivisions and chains. Let us keep the above assumptions and choose a vertex v of σ. Let ϕ( w ) = v and ϕ( z ) = z if z is a vertex of S different from w . Then ϕ is a simplicial map S −→ S . Recall that [[α]] denotes the subdivision of a chain α of K or S with respect to K or S respectively. Since the map ϕ is obviously pseudo-identical, Alexander's lemma implies that ϕ * ( [[α]] ) = α for every chain α in S . It turns out that the map β −→ [[ ϕ * ( β)]] is fairly close to the identity. This is the key element of the proof of the invariance of homology groups under stellar subdivisions.
We need to extend the operation of taking cones to a simple situation when the geometric cone is not defined. Let τ be an n-simplex of L for some n . If v is not a vertex of τ, then v * τ is already well defined (because v is a vertex and τ is a face of some simplex of K ).
If v is a vertex of τ, then we interpret v * τ as the zero (n + 1)-chain. We extend the maps τ −→ w * τ and τ −→ v * τ from simplices to chains by linearity.
Lemma. If δ is a face and z is a vertex of a simplex, then ∂ ( z * δ ) = δ + z * ∂δ.
Proof. If z is not a vertex of δ, this is obvious. If δ is an n-simplex and z is a vertex of δ, then z is a vertex of all (n − 1)-faces of δ except of the (n − 1)-face δ z opposite to z . In this case z * δ = 0 and z * ∂δ = z * δ z = δ. Therefore in this case the identity of the lemma reduces to ∂0 = δ + δ, which is obviously true over F 2 . ■ Double cones. Given a simplex τ of L, let considered as a chain in K .
Here v * τ is interpreted as zero if v is a vertex of τ and w * ( v * τ) is interpreted as zero if w belongs to the simplex v * τ. Let us extend the map τ −→ w v * τ to a linear map from chains of L to chains of K .

Lemma. Let α be a chain in L.
Then Proof. It is sufficient to consider the case when α is equal to a simplex τ of L. Suppose first that v is not a vertex of τ and w does not belong to v * τ. Then v * τ is a simplex in L and hence [[ v * τ ]] = v * τ. In this case the previous lemma implies that Suppose now that v is not a vertex of τ, but w belongs to v * τ. In this case σ is not a face of τ but is a face of v * τ. This may happen only when τ contains the face σ v opposite to v in σ but does not contains v . Let n be the dimension of τ. An n-face of v * τ is either equal to τ, or has the form v * λ for some (n − 1)-face λ of τ. The simplex v * λ is a simplex of L if and only if λ does not contain the simplex σ v . Let Λ be the sum of such (n − 1)-faces λ of τ. Then [[ v * τ ]] = w * ( v * Λ) + w * τ. On the other hand, because if an (n − 1)-face µ of τ contains the simplex σ v , then v * µ contains w and hence w * ( v * µ) = 0 by the definition. It follows that [[ v * τ ]] + w * τ + w v * (∂τ) = w * ( v * Λ) + w * τ + w * τ + w * ( v * Λ) = 0 .
In this case also w v * τ = 0 and hence the identity of lemma holds.
It remains to consider the case when v is a vertex of τ. Then w v * τ = w * 0 = 0 and v * τ = 0. By the previous lemma τ = v * ∂τ and hence w v * (∂τ) = w * τ. Since w * τ + w * τ = 0, the lemma holds in this case also. ■ Lemma. Let α be a chain of K such that its boundary is a chain of L. Then [[ϕ * (α)]] − α is a cycle and, moreover, a boundary.
Proof. Let β be the sum of simplices of α not having w as a vertex. Then β is a chain in L and hence ϕ * ( β) = β and [[ϕ * ( β)]] = [[β]] = β. It follows that the boundary of β is a chain in L and [[ϕ * ( β)]] − β = 0. Therefore, after replacing α by α − β, if necessary, we may assume that every simplex of α has w as a vertex. In this case α = w * ρ for some chain ρ of L and hence ϕ * (α) = v * ρ. Also, ∂α is a chain in L and hence ∂α = ρ. It follows that ∂ρ = ∂∂α = 0. By the previous lemma Proof. By Alexander's lemma ϕ * ( [[α]] ) = α for every chain α in S and hence ϕ * * • s is the identity map. By the last lemma for every cycle γ in S the cycles [[ϕ * (γ)]] and γ belong to the same homology class and hence s • ϕ * * is the identity map. ■ Stellar subdivisions and centers-generated subdivisions. Let S be a simplicial complex. Suppose that, as in Appendix 1, for every simplex σ of S a point z (σ) ∈ σ bd σ, called the center of σ, is chosen. Recall that such a choice generates a subdivision c S of S . The simplices of c S are in one-to-one correspondence with sequences σ 0 , σ 1 , . . . , σ n of simplices of S such that σ j is a face of σ i if j < i , and the simplex corresponding to the sequence σ 0 , σ 1 , . . . , σ n has the centers z (σ 0 ), z (σ 1 ), . . . , z (σ n ) as its vertices. Alexander observed that such a subdivision c S can be obtained as the result of a sequence of stellar subdivisions. Let us arrange all simplices of S into a sequence of simplices σ 1 , σ 2 , . . . , σ N with non-increasing dimensions. In other words, the dimension of σ i is required to be greater or equal than the dimension of σ j if i j . The order of simplices of the same dimension does not matter. Let S (0) = S and let S (k ) be the stellar subdivision of S (k − 1) with the center z (σ k ) for every k N.

Lemma. S ( N ) is equal to the centers-generated subdivision c S .
Proof. The vertices of S ( N ) are exactly the centers of simplices of S (one should keep in mind the vertices of S are centers of the corresponding 0-simplices). Since several vertices are the vertices of a simplex if and only if they are pairwise connected by edges, the main part of the proof is to find out when two centers are connected by an edge in S ( N ).
Let k N. The center z (σ k ) is introduced as a new vertex in S (k ). Since dimensions are non-increasing, the centers z (ρ) of simplices ρ having σ k as a proper face are already present in S (k ). By the definition of stellar subdivisions, z (σ k ) is connected by an edge in S (k ) to these centers z (ρ) and to no other centers z (σ i ) with i < k . In particular, z (σ k ) is not connected in S (k ) with centers z (σ i ) of simplices σ i of the same dimension as σ.
Since every edge connecting two centers is created at one of the steps of our stellar subdivision process, we see that two centers z (σ k ) and z (σ i ) are connected by an edge in S ( N ) if and only if one of the simplices σ k , σ i is a proper face of the other. It follows that several centers are pairwise connected by edges of S ( N ) if and only if the corresponding simplices can be arranged in a sequence σ 0 , σ 1 , . . . , σ n such that σ j is a face of σ i if j < i . This means that S ( N ) has exactly the same simplices as c S .