Topological combinatorics studies how topological ideas can be used to solve discrete problems about graphs, hypergraphs, simplicial complexes, and partitions. The course develops the central philosophy that combinatorial structure often carries hidden geometric and homological information, and that this information can be converted into strong existence theorems and lower bounds. Along the way, it introduces the basic language of simplicial complexes and combinatorial topology, then builds the homological and obstruction-theoretic tools needed to detect when certain combinatorial configurations must exist. The main themes are equivariance, index methods, and topological versions of classical discrete theorems. Early chapters establish the foundational notions of connectivity and homology, then use the Borsuk–Ulam theorem as a model for translating topology into combinatorics. From there, the course develops combinatorial analogues such as Tucker’s lemma, Ky Fan’s lemma, and Sperner’s lemma, and applies them to problems like Kneser’s conjecture, ham sandwich cuts, and Tverberg-type partition theorems. Later chapters broaden the toolkit with shellability, Cohen-Macaulay complexes, and posets, showing how these structural ideas support both deeper theory and further applications. The chapters are arranged to move from foundational definitions to powerful applications. The initial material on simplicial complexes and homology prepares the language for obstruction theory and equivariant topology, which in turn underlie the combinatorial Borsuk–Ulam results. Those results then feed into the major applications on graph coloring and partition theorems, while the final chapters connect the course to broader algebraic and combinatorial methods that continue to drive current research. # Introduction This course studies a recurring phenomenon in combinatorics: finite configurations often cannot be understood by counting alone, because the obstruction to a desired choice is topological. The organising principle is the [Borsuk-Ulam theorem](/theorems/6462) and its equivariant relatives, which turn symmetry into lower bounds, non-existence statements, and intersection theorems. The goal of this introductory chapter is to explain the kinds of questions the course answers, the objects that will carry the topological information, and the proof pattern that will reappear in graph colouring, convexity, and discrete geometry. The course assumes point-set topology, basic algebraic topology, elementary graph theory, finite group actions, simplicial complexes, and linear algebra. The notes are written for early graduate students in combinatorics, topology, discrete geometry, or theoretical computer science. Later chapters develop the required language in more detail, but this chapter fixes the map of the subject before the technical work begins. ## Why Topology Enters Combinatorics What can force a finite combinatorial problem to have no solution even when every local obstruction has been removed? The topological answer is that a hypothetical solution may define an equivariant map between spaces, and such a map may be forbidden by topology. The finite problem is then converted into a continuous problem with symmetry. [explanation: Obstruction Philosophy] A typical topological-combinatorial proof has three stages. First, encode the combinatorial data as a simplicial complex or a configuration space. Second, translate a hypothetical combinatorial object, such as a colouring or an avoided intersection, into a continuous map respecting a [group action](/page/Group%20Action). Third, use a theorem from equivariant topology to prove that no such map exists. The strength of this method is that the topological obstruction is insensitive to many local changes. It can see global incompatibility that is difficult to detect by direct enumeration. In this course, the obstruction is often measured by connectivity, homology, index theory, or a Borsuk-Ulam-type theorem. [/explanation] This viewpoint changes the role of topology in combinatorics. Topology is not decoration added after a finite argument; it is the language in which the finite impossibility statement becomes stable and computable. [example: Odd Cycle Colouring] Label the vertices of $C_{2m+1}$ in cyclic order as $v_0,v_1,\dots,v_{2m}$, with edges $v_i v_{i+1}$ for $0\leq i<2m$ and closing edge $v_{2m}v_0$. We show that no proper $2$-colouring exists. Suppose, for contradiction, that $c$ is a proper colouring with colour set $\{0,1\}$. Since adjacent vertices must have different colours, the first few colours are forced: \begin{align*} c(v_1)=1-c(v_0). \end{align*} \begin{align*} c(v_2)=1-c(v_1)=1-(1-c(v_0))=c(v_0). \end{align*} \begin{align*} c(v_3)=1-c(v_2)=1-c(v_0). \end{align*} Repeating the same step along the path gives $c(v_i)=c(v_0)$ when $i$ is even and $c(v_i)=1-c(v_0)$ when $i$ is odd. In particular, $2m$ is even, so \begin{align*} c(v_{2m})=c(v_0). \end{align*} But $v_{2m}$ is adjacent to $v_0$, so properness requires \begin{align*} c(v_{2m})\neq c(v_0), \end{align*} which contradicts the equality above. Thus $C_{2m+1}$ is not $2$-colourable. The same obstruction can be read topologically: the two colours form a symmetric pair, and an odd cycle forces an alternating assignment to return to its starting point with incompatible parity. [/example] The example is elementary, but it contains the main theme: parity, symmetry, and continuity reinforce each other. Chapters 2, 3, and 6 replace the circle-like obstruction by higher-dimensional spheres, deleted joins, and equivariant indices. ## The Borsuk-Ulam Principle Which topological statement is strong enough to produce combinatorial lower bounds? The central answer is the Borsuk-Ulam theorem. It says that antipodal symmetry on a sphere cannot be compressed into Euclidean space of one lower dimension without identifying some antipodal pair. [quotetheorem:6462] [citeproof:6462] The theorem will be used both as a result in its own right and as a model for more general obstruction statements. Many later proofs do not mention $S^n$ explicitly, but they follow the same template: assume a combinatorial construction exists, build an equivariant map, then contradict a topological index calculation. The hypotheses are doing real work. The dimension of the target is sharp: the identity map $S^n\to S^n\subset \mathbb R^{n+1}$ is continuous and separates every antipodal pair, so the obstruction is specifically about trying to map into $\mathbb R^n$ and then, after normalisation, into $S^{n-1}$. Raising the target dimension by one destroys the conclusion, because this inclusion satisfies $f(x)\neq f(-x)$ for every $x\in S^n$. Continuity is also essential: by choosing one point from each antipodal pair using the [axiom of choice](/page/Axiom%20of%20Choice), one can define a discontinuous map that assigns different values to $x$ and $-x$ everywhere. Thus Borsuk-Ulam is not a statement about arbitrary labellings of antipodal pairs; it is a statement about continuous, globally compatible labellings. It also does not say where the coincidence occurs, how many coincidences there are, or that the coincident point is unique. [example: Ham Sandwich Preview] Parametrize an oriented affine hyperplane by a point $y\in S^n$, and write its positive and negative closed half-spaces as $H_y^+$ and $H_y^-$. Reversing the orientation gives the antipodal point $-y$, so $H_{-y}^+=H_y^-$ and $H_{-y}^-=H_y^+$. For each bounded measurable set $A_i\subset \mathbb R^n$, define its signed imbalance across $H_y$ by \begin{align*} F_i(y)=\mathcal L^n(A_i\cap H_y^+)-\mathcal L^n(A_i\cap H_y^-). \end{align*} These quantities are finite because each $A_i$ is bounded and measurable. Combining the $n$ imbalances gives \begin{align*} F(y)=(F_1(y),\dots,F_n(y)). \end{align*} For each coordinate, \begin{align*} F_i(-y)=\mathcal L^n(A_i\cap H_{-y}^+)-\mathcal L^n(A_i\cap H_{-y}^-). \end{align*} Using $H_{-y}^+=H_y^-$ and $H_{-y}^-=H_y^+$, this becomes \begin{align*} F_i(-y)=\mathcal L^n(A_i\cap H_y^-)-\mathcal L^n(A_i\cap H_y^+). \end{align*} Factoring out the minus sign gives \begin{align*} F_i(-y)=-\bigl(\mathcal L^n(A_i\cap H_y^+)-\mathcal L^n(A_i\cap H_y^-)\bigr). \end{align*} Hence \begin{align*} F_i(-y)=-F_i(y), \end{align*} so $F(-y)=-F(y)$. Assuming the standard continuity check for these imbalance functions, the *Borsuk-Ulam Theorem* gives a point $y\in S^n$ such that \begin{align*} F(y)=F(-y). \end{align*} Since $F(-y)=-F(y)$, we get \begin{align*} F(y)=-F(y). \end{align*} Adding $F(y)$ to both sides gives \begin{align*} 2F(y)=0. \end{align*} Since the [vector space](/page/Vector%20Space) is over $\mathbb R$, division by $2$ gives \begin{align*} F(y)=0. \end{align*} Therefore, for every $1\le i\le n$, \begin{align*} 0=F_i(y)=\mathcal L^n(A_i\cap H_y^+)-\mathcal L^n(A_i\cap H_y^-). \end{align*} Thus \begin{align*} \mathcal L^n(A_i\cap H_y^+)=\mathcal L^n(A_i\cap H_y^-). \end{align*} The antipodal coincidence has become a single affine hyperplane whose two sides have equal $A_i$-measure for every set at once. [/example] This preview shows why geometric intersection theorems belong in the same course as graph-colouring lower bounds. Both are consequences of the same impossibility of equivariant compression. ## Spaces Built from Finite Data How does a finite set system become a [topological space](/page/Topological%20Space)? The standard device is a simplicial complex, whose faces record mutually compatible choices. The geometry of the complex then measures the global pattern of compatibility. [explanation: Simplicial Complex Preview] An abstract simplicial complex on a set $V$ is a collection $K$ of finite subsets of $V$ such that if $\sigma \in K$ and $\tau \subset \sigma$, then $\tau \in K$. The elements of $K$ are called faces. A maximal face under inclusion is called a facet. The dimension of a non-empty face $\sigma$ is $|\sigma|-1$, and the dimension of $K$ is the supremum of the dimensions of its faces. [/explanation] After this definition, the word "complex" should be read in two compatible ways. It is a finite or locally finite combinatorial object made of faces, and it also has a geometric realization obtained by gluing simplices. The course moves between these two meanings constantly. [example: Independence Complex] Let $G=(V,E)$ be a finite graph. The independence complex $\operatorname{Ind}(G)$ has vertex set $V$, and a finite subset $\sigma\subseteq V$ is a face exactly when no two distinct vertices of $\sigma$ are joined by an edge of $G$. For the path $P_3$ with vertices $1,2,3$ and edges $12,23$, the subsets of $\{1,2,3\}$ are \begin{align*} \varnothing,\quad \{1\},\quad \{2\},\quad \{3\},\quad \{1,2\},\quad \{1,3\},\quad \{2,3\},\quad \{1,2,3\}. \end{align*} The pairs $\{1,2\}$ and $\{2,3\}$ are not independent because $12,23\in E$. The triple $\{1,2,3\}$ is not independent because it contains the edge $12$ and also contains the edge $23$. The pair $\{1,3\}$ is independent because $13\notin E$. Every singleton is independent, since a one-element set contains no pair of distinct vertices, and $\varnothing$ is independent for the same reason. Thus the faces of $\operatorname{Ind}(P_3)$ are \begin{align*} \varnothing,\quad \{1\},\quad \{2\},\quad \{3\},\quad \{1,3\}. \end{align*} Geometrically, the face $\{1,3\}$ realizes as an interval with endpoints $1$ and $3$, while the vertex $2$ is not contained in any higher-dimensional face. Therefore $\operatorname{Ind}(P_3)$ is one interval together with one isolated vertex. [/example] Independence complexes demonstrate how graph structure becomes topology. A graph colouring question can often be restated as a question about maps out of, or into, complexes naturally associated to the graph. [explanation: Geometric Realization Preview] Let $K$ be an abstract simplicial complex on a finite vertex set $V=\{v_1,\dots,v_m\}$. Its geometric realization $|K|$ is the subspace of $\mathbb R^m$ consisting of all points $\sum_{i=1}^m t_i e_i$ such that $t_i \ge 0$, $\sum_{i=1}^m t_i=1$, and $\{v_i : t_i>0\}\in K$. [/explanation] The geometric realization is the bridge between combinatorics and topology. It lets us apply homotopy, homology, connectivity, and group actions to finite data without losing the original combinatorial meaning. [example: Order Complex Preview] Let $P$ be the proper part of the Boolean lattice on $\{1,2,3\}$, so \begin{align*} P=\{\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}\}, \end{align*} ordered by inclusion. The order complex $\Delta(P)$ has these six elements as vertices, and a subset of vertices is a face exactly when its elements can be arranged in a strict inclusion chain. The one-vertex faces are the six singleton chains. The two-vertex faces are precisely the strict inclusions from a one-element subset into a two-element subset: \begin{align*} \{1\}\subset \{1,2\},\qquad \{1\}\subset \{1,3\}. \end{align*} \begin{align*} \{2\}\subset \{1,2\},\qquad \{2\}\subset \{2,3\}. \end{align*} \begin{align*} \{3\}\subset \{1,3\},\qquad \{3\}\subset \{2,3\}. \end{align*} There are no three-vertex faces, because a strict chain of three subsets in the Boolean lattice on $\{1,2,3\}$ would have the form \begin{align*} \{i\}\subset \{i,j\}\subset \{1,2,3\}, \end{align*} and the top element $\{1,2,3\}$ is not in the proper part. Thus $\Delta(P)$ is a one-dimensional complex with six vertices and six edges. Reading the edges in cyclic order gives \begin{align*} \{1\},\ \{1,2\},\ \{2\},\ \{2,3\},\ \{3\},\ \{1,3\},\ \{1\}. \end{align*} Its geometric realization is therefore a hexagon. Since a hexagon is homeomorphic, and hence homotopy equivalent, to $S^1$, the order complex records a circle-shaped obstruction coming from the inclusion pattern of the proper non-empty subsets. [/example] This example previews why posets enter topological combinatorics. Their chains are combinatorial, but their order complexes often have recognizable homotopy types. ## Symmetry and Equivariant Maps Where does the group action enter the argument? Most applications compare two choices related by symmetry: opposite points of a sphere, two parts of a partition, or several labelled copies of a configuration. A group action records this symmetry so that continuous maps are required to respect it. [explanation: Group Action Preview] Let $G$ be a group and let $X$ be a set. A left action of $G$ on $X$ is a map $G\times X\to X$, written $(g,x)\mapsto g\cdot x$, such that $e\cdot x=x$ for all $x\in X$ and $(gh)\cdot x=g\cdot(h\cdot x)$ for all $g,h\in G$ and $x\in X$. [/explanation] For topological applications, $X$ will usually be a topological space and each map $x\mapsto g\cdot x$ will be continuous. A group action alone records the symmetry of each space, but the obstruction argument also needs a way to compare two spaces while preserving that symmetry. This requirement leads to the maps used in every test-map proof. [explanation: Equivariant Map Preview] Let $G$ act on topological spaces $X$ and $Y$. A map $f:X\to Y$ is $G$-equivariant if $f(g\cdot x)=g\cdot f(x)$ for every $g\in G$ and every $x\in X$. [/explanation] Equivariance is the formal condition that a map respects the symmetry in the problem. In Borsuk-Ulam arguments, the contradiction usually says that a certain equivariant map cannot exist. [example: Antipodal Equivariance] Let $G=\mathbb Z/2\mathbb Z=\{0,1\}$, where $0$ acts as the identity and $1$ acts antipodally. Thus on $S^n$ we have \begin{align*} 0\cdot x=x,\qquad 1\cdot x=-x, \end{align*} and on $S^{n-1}$ we have \begin{align*} 0\cdot y=y,\qquad 1\cdot y=-y. \end{align*} By the definition of equivariance, a map $h:S^n\to S^{n-1}$ is $G$-equivariant exactly when \begin{align*} h(g\cdot x)=g\cdot h(x) \end{align*} for every $g\in G$ and $x\in S^n$. For $g=0$, this condition reads \begin{align*} h(0\cdot x)=0\cdot h(x), \end{align*} which is \begin{align*} h(x)=h(x). \end{align*} For $g=1$, it reads \begin{align*} h(1\cdot x)=1\cdot h(x), \end{align*} which is \begin{align*} h(-x)=-h(x). \end{align*} Hence equivariance is exactly the antipodal identity $h(-x)=-h(x)$. Now suppose such an equivariant $h$ existed. Regard $S^{n-1}$ as a subset of $\mathbb R^n$, and define $f:S^n\to \mathbb R^n$ by \begin{align*} f(x)=h(x). \end{align*} By the *Borsuk-Ulam Theorem*, there is some $x\in S^n$ such that \begin{align*} f(x)=f(-x). \end{align*} Since $f=h$ and $h(-x)=-h(x)$, we also have \begin{align*} f(-x)=h(-x)=-h(x)=-f(x). \end{align*} Combining the two equalities gives \begin{align*} f(x)=-f(x). \end{align*} Adding $f(x)$ to both sides gives \begin{align*} 2f(x)=0, \end{align*} and division by $2$ in the real vector space $\mathbb R^n$ gives \begin{align*} f(x)=0. \end{align*} But $f(x)=h(x)\in S^{n-1}$, so $\|f(x)\|=1$, contradicting $f(x)=0$. Therefore no antipodal equivariant map $S^n\to S^{n-1}$ exists, which is exactly the obstruction obtained when a nowhere-zero odd map is normalised to the sphere. [/example] Chapter 6 expands this from $\mathbb Z/2\mathbb Z$ to broader equivariant index language, and Chapter 8 uses cyclic groups, elementary abelian $p$-groups, and symmetric group actions for Tverberg-type theorems. The same logic remains: symmetry creates equivariant maps, topology restricts them. ## Three Guiding Applications What combinatorial theorems justify building this machinery? The course returns to three major families of applications. Each illustrates a different way topological information forces a finite conclusion. For the first application, $KG(n,k)$ denotes the Kneser graph: its vertices are the $k$-element subsets of $[n]=\{1,\dots,n\}$, and two vertices are adjacent exactly when the corresponding subsets are disjoint. [quotetheorem:6463] [citeproof:6463] This theorem is the flagship example of the course. A graph-colouring invariant, which at first seems purely finite, is computed by an argument about antipodal maps on spheres. The hypotheses also clarify the scope of the result. The condition $n\ge 2k$ is exactly the range in which $KG(n,k)$ has vertices that can be compared by disjointness in a non-degenerate way; when $n<2k$ there are no edges, so the chromatic number is $1$ rather than $n-2k+2$. At the boundary $n=2k$, the graph is a matching on complementary $k$-subsets and the formula gives $\chi(KG(2k,k))=2$. The theorem classifies the chromatic number of this special family of highly symmetric graphs; it does not compute chromatic numbers of arbitrary graphs, nor does it say that every graph-colouring lower bound is topological. Its limitation is part of its value: the topology enters because the vertices are $k$-subsets and adjacency is disjointness, giving an antipodal geometry that a general graph need not possess. [example: Petersen Graph as a Kneser Graph] The Petersen graph is $KG(5,2)$: its vertices are the $2$-element subsets of $\{1,2,3,4,5\}$, and two vertices are adjacent exactly when the corresponding pairs are disjoint. Applying the *Kneser-Lovasz Theorem* with $n=5$ and $k=2$ gives \begin{align*} \chi(KG(5,2))=5-2\cdot 2+2. \end{align*} Since $2\cdot 2=4$, this is \begin{align*} \chi(KG(5,2))=5-4+2=3. \end{align*} The upper bound $\chi(KG(5,2))\leq 3$ can also be checked by an explicit colouring. Put all pairs containing $1$ in colour class $C_1$, put $\{2,3\},\{2,4\},\{3,4\}$ in colour class $C_2$, and put $\{2,5\},\{3,5\},\{4,5\}$ in colour class $C_3$. Any two vertices in $C_1$ intersect in $1$, any two vertices in $C_2$ share at least one element from $\{2,3,4\}$, and any two vertices in $C_3$ intersect in $5$. Since adjacency in $KG(5,2)$ means disjointness, no two vertices of the same colour are adjacent, so these three classes define a proper $3$-colouring. The equality $\chi(KG(5,2))=3$ gives the lower bound as well: if a proper $2$-colouring existed, then the chromatic number would satisfy \begin{align*} \chi(KG(5,2))\leq 2, \end{align*} contradicting $\chi(KG(5,2))=3$. Thus the Kneser description explains more than the presence of odd cycles: it places the Petersen graph inside a family whose chromatic number is controlled by an antipodal sphere-cover obstruction. [/example] The next family of applications concerns partitions of point sets and measures. Instead of colouring vertices, the task is to force intersections or common bisectors. [quotetheorem:6464] [citeproof:6464] The theorem shows the geometric side of the same method. A simultaneous balancing statement becomes the assertion that an odd map must vanish. The finite Borel measure hypotheses ensure that every half-space cut has assigned mass and that the target value "half the total mass" is finite. If one instead works with ordinary [Lebesgue measure](/page/Lebesgue%20Measure) on all of $\mathbb R^n$, both half-spaces can have infinite measure, so the phrase "half of the measure" no longer defines a finite bisection condition. The hyperplane parametrisation is also part of the theorem rather than a cosmetic choice: orientations give opposite points on $S^n$, and reversing the orientation changes the imbalance vector by a sign. The theorem guarantees existence of at least one simultaneous bisecting hyperplane, but it does not classify all such hyperplanes, give uniqueness, or assert that the hyperplane avoids atoms or boundaries. If boundary mass matters, one usually imposes absolute continuity or interprets the closed-half-space convention with care. Intersection theorems push this idea further: instead of balancing two sides of a hyperplane, they force several disjoint pieces of a simplex to have images that meet at a common point. That stronger coincidence problem requires deleted joins and equivariant obstruction theory beyond the antipodal case. [quotetheorem:6465] [citeproof:6465] This preview also marks a boundary of the theory. For non-prime-power values of $r$, the topological Tverberg statement in this form fails in sufficiently high dimensions, so the topology is not merely proving a universal convexity fact; it is detecting the exact reach of the method. The number $N=(r-1)(d+1)$ is the threshold predicted by the affine Tverberg theorem: below this dimension there are not enough vertices to force $r$ disjoint faces to meet under every map. For example, with fewer than $(r-1)(d+1)+1$ vertices, the simplex can be placed in sufficiently general position in $\mathbb R^d$ so that the required $r$-fold intersection is not forced. The prime-power condition is not a technical accident in the topological version: the known obstruction uses equivariant cohomology for $p$-groups, and counterexamples show that the unrestricted statement fails for non-prime-powers in high dimensions. The theorem also does not identify which faces intersect, does not claim uniqueness of the intersection point, and does not say that every equivariant obstruction problem reduces to [Tverberg's theorem](/theorems/6499). ## How the Course Develops What sequence of tools is needed to make these applications rigorous? The course begins with simplicial complexes and combinatorial topology, then adds homology, connectivity, and obstruction language. It then develops equivariant topology around Borsuk-Ulam theorems before applying the machinery to graphs, convexity, and Tverberg-type results. [explanation: Lecture Architecture] The first part of the course builds the objects: abstract complexes, geometric realizations, joins, links, barycentric subdivision, nerves, and standard examples from graphs and posets. The second part builds the measurements: reduced homology, Euler characteristic, connectivity, Mayer-Vietoris arguments, and long exact sequences. The third part adds symmetry through group actions, equivariant maps, indices, and test-map schemes. The final part applies the machinery. Kneser graphs show how topology proves chromatic lower bounds. The [ham sandwich theorem](/theorems/6464) and necklace-splitting problems show how antipodal and equivariant maps encode fair division. Tverberg-type theorems show how deleted products and deleted joins turn intersection problems into equivariant non-existence statements. [/explanation] This structure is cumulative. Each later theorem uses objects introduced earlier, so the reader should treat the first chapters as a toolkit rather than a collection of isolated definitions. [remark: Proof Strategy to Remember] The recurring proof strategy is: build a configuration space, remove forbidden coincidences, impose a group action, construct a test map from a hypothetical counterexample, and contradict an equivariant topological theorem. [/remark] That sentence is the course in miniature. The technical chapters explain how to build each term in the sentence and how to verify the hypotheses in concrete combinatorial problems. The opening chapter gives the course its overall pattern: turn a combinatorial problem into topology, then use a topological obstruction to rule out a hypothetical counterexample. The next chapter supplies the basic language for carrying out that translation by turning graphs, posets, hypergraphs, and set systems into simplicial complexes. # 1. Simplicial Complexes and Combinatorial Topology This opening chapter sets up the dictionary between finite combinatorial data and topological spaces. The main question is how a graph, poset, hypergraph, or family of sets can be converted into a simplicial complex whose topology records combinatorial structure. The prerequisites are basic set notation, finite graphs and posets, and the point-set topology language of open covers, compactness, homotopy, and contractibility. Later chapters use these complexes as the spaces on which equivariant topology acts, so we begin by fixing the basic constructions and the examples that recur throughout the course. ## Complexes Built from Faces How should a finite collection of combinatorial objects be organised so that it behaves like a triangulated space? The central requirement is closure under taking smaller pieces: once a face is present, all of its subfaces must also be present. This is the combinatorial shadow of the fact that a simplex contains all of its lower-dimensional faces. [definition: Abstract Simplicial Complex] Let $V$ be a set. An abstract simplicial complex on $V$ is a collection $K$ of finite subsets of $V$ such that if $\tau \in K$ and $\sigma \subset \tau$, then $\sigma \in K$. The elements of $K$ are called faces or simplices. A vertex is a face of cardinality $1$. [/definition] The closure condition is what lets us draw a face $\{v_0,v_1,v_2\}$ as a filled triangle rather than merely as three named vertices. Since $\varnothing\subset \tau$ for every face $\tau$, the empty face belongs to every nonempty abstract simplicial complex under this convention. Once a complex has been specified, the next bookkeeping problem is to distinguish its maximal pieces from its lower-dimensional boundary pieces. This motivates the following definition. [definition: Dimension and Facet] Let $K$ be an abstract simplicial complex. The dimension of a face $\sigma \in K$ is \begin{align*} \dim \sigma = |\sigma| - 1. \end{align*} The dimension of $K$ is \begin{align*} \dim K = \sup_{\sigma \in K} \dim \sigma. \end{align*} A facet of $K$ is a face maximal under inclusion. [/definition] Facets give an economical way to specify a finite complex: list the maximal faces and include all of their subsets. Dimension measures the largest simplex present, not the number of vertices in the ambient vertex set. The following small boundary example separates these two pieces of information. [example: Boundary of a Triangle] Let $V=\{1,2,3\}$, and let \begin{align*} K=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\}\}. \end{align*} The maximal faces under inclusion are exactly the two-element faces. The singleton faces are not maximal, since $\{1\}\subset\{1,2\}$, $\{2\}\subset\{1,2\}$, and $\{3\}\subset\{1,3\}$. Each two-element face is maximal: the only subset of $V$ strictly containing any of $\{1,2\}$, $\{2,3\}$, or $\{1,3\}$ is $\{1,2,3\}$, and $\{1,2,3\}\notin K$. Hence the facets are $\{1,2\}$, $\{2,3\}$, and $\{1,3\}$. Using $\dim \sigma=|\sigma|-1$, the facet dimensions are \begin{align*} \dim\{1,2\}=|\{1,2\}|-1=2-1=1. \end{align*} Similarly, $\dim\{2,3\}=1$ and $\dim\{1,3\}=1$. The remaining nonempty faces have one vertex, so they have dimension $1-1=0$, while the empty face has dimension $0-1=-1$. Therefore the largest face dimension in $K$ is $1$, so $\dim K=1$. The complex contains the three boundary edges of the triangle but not the $2$-face $\{1,2,3\}$, so it is the boundary of a $2$-simplex rather than the filled triangle. [/example] This example also shows why local structure is not captured by listing dimensions alone: near a vertex, the incident edges describe a neighbourhood. To study a complex locally near a face, we separate the faces disjoint from it that can still be attached to it. This motivates the following definition. [definition: Link and Star] Let $K$ be an abstract simplicial complex and let $\sigma \in K$. The link of $\sigma$ in $K$ is \begin{align*} \operatorname{lk}_K(\sigma)=\{\tau \in K : \tau \cap \sigma=\varnothing \text{ and } \tau \cup \sigma \in K\}. \end{align*} The star of $\sigma$ in $K$ is \begin{align*} \operatorname{st}_K(\sigma)=\{\tau \in K : \tau \cup \sigma \in K\}. \end{align*} [/definition] The link is the combinatorial normal slice to a face, while the star is a neighbourhood built from all simplices that can be joined to the face. Before using links in inductive arguments, we need the closure properties and the basic identity for taking links twice. This motivates the following theorem. [quotetheorem:6466] [citeproof:6466] The hypotheses are part of the content. The face $\sigma$ must lie in $K$: if a chosen set of vertices is not a face, the expression $\tau\cup\sigma\in K$ may still define a collection, but it no longer describes a neighbourhood of a simplex in the complex. The disjointness condition in the link is also essential; without it, linking a vertex in a filled triangle would retain that vertex and would not model the transverse edge opposite the vertex. The theorem does not say that links determine the whole complex: two nonisomorphic complexes can have isomorphic links at a chosen face, so links are local data rather than a complete invariant. These formulas are used repeatedly when inducting on a complex or analysing neighbourhoods. Links describe what remains transverse to a chosen face, but many constructions require building a larger complex from two unrelated pieces. If faces from the two pieces are meant to be chosen independently, the complex must specify exactly which mixed vertex sets are allowed and must avoid ambiguity from overlapping vertex labels. The join is the operation that encodes this independent choice of one face from each factor. [definition: Join of Simplicial Complexes] Let $K$ and $L$ be simplicial complexes on disjoint vertex sets. Their join is the simplicial complex \begin{align*} K * L = \{\sigma \cup \tau : \sigma \in K,\ \tau \in L\}. \end{align*} [/definition] Once joins are available, two basic consistency checks become necessary. First, the dimension count must reflect that a simplex in the join is assembled from simplices in both factors, with one extra direction between them. Second, local calculations should remain manageable: the link of a mixed face should separate into data from the two original complexes rather than becoming a new unrelated object. These are not automatic from the definition alone: mixed faces could in principle make dimensions and links hard to read from the two factors. We need a pair of formulas that recover the dimension and each mixed-face link from the corresponding data in the two factors, because that control is what makes joins usable in later local and inductive arguments. [quotetheorem:6467] [citeproof:6467] The disjoint-vertex-set hypothesis prevents an ambiguity in writing a face of $K*L$ as $\sigma\cup\tau$: if the same vertex were allowed to occur in both factors, the cardinality calculation would double-count it and the link formula would no longer separate into two independent conditions. The nonempty finite hypotheses keep the dimension statement in the ordinary finite-dimensional setting used in these notes; for empty complexes or infinite-dimensional complexes, conventions for $\dim$ must be fixed before the formula has a precise meaning. The theorem also does not say that joins preserve the topology of either factor: a join usually changes homotopy type substantially, and joining with a simplex produces a cone-like object. Later connectivity arguments use this change as a feature, because the join adds room while the link formula keeps local calculations factorised. The formula predicts that joining two $0$-dimensional complexes should produce a $1$-dimensional complex. A concrete four-vertex case also shows that joins can create connected topology from disconnected inputs. [example: Joining Two Discrete Two-Point Complexes] Let $K=\{\varnothing,\{a_1\},\{a_2\}\}$ and $L=\{\varnothing,\{b_1\},\{b_2\}\}$, with the vertex sets disjoint. By the definition of the join, \begin{align*} K*L=\{\sigma\cup\tau:\sigma\in K,\ \tau\in L\}. \end{align*} Taking $\sigma=\varnothing$ gives the faces $\varnothing,\{b_1\},\{b_2\}$, and taking $\tau=\varnothing$ gives the faces $\varnothing,\{a_1\},\{a_2\}$. If $\sigma$ and $\tau$ are both singletons, then \begin{align*} \{a_i\}\cup\{b_j\}=\{a_i,b_j\} \end{align*} for $i,j\in\{1,2\}$, so the two-element faces are \begin{align*} \{a_1,b_1\},\{a_1,b_2\},\{a_2,b_1\},\{a_2,b_2\}. \end{align*} There are no larger faces: every face of $K$ has at most one $a$-vertex and every face of $L$ has at most one $b$-vertex, so every union $\sigma\cup\tau$ has cardinality at most $1+1=2$. Thus the facets of $K*L$ are exactly the four edges above. They form the cycle \begin{align*} a_1-b_1-a_2-b_2-a_1, \end{align*} because the consecutive pairs are precisely the edges $\{a_1,b_1\}$, $\{a_2,b_1\}$, $\{a_2,b_2\}$, and $\{a_1,b_2\}$. Hence $K*L$ is a $1$-dimensional complex whose geometric realization is a $4$-cycle, showing that the join of two disconnected $0$-dimensional complexes can be connected. [/example] ## Realization and Subdivision When does an abstract complex become a topological space rather than a list of finite sets? The answer is to choose affinely independent points for the vertices and glue geometric simplices along their common faces. This passage is essential because homotopy, homeomorphism, and contractibility are topological notions. [definition: Geometric Realization] Let $K$ be a finite abstract simplicial complex with vertex set $V$. Its geometric realization is the space \begin{align*} |K|=\left\{x:V\to[0,1] : \operatorname{supp}x\in K,\ \sum_{v\in V}x(v)=1\right\}, \end{align*} with the [subspace topology](/page/Subspace%20Topology) inherited from $\mathbb R^V$. [/definition] The coordinates $x(v)$ are barycentric coordinates. A point lies in the simplex indexed by its support, and the closure relations among simplices reproduce the face relations in $K$. The full simplex and its boundary give the basic model for this translation. [example: Realizing a Filled Triangle] Let $K$ be the full simplex on $\{1,2,3\}$, so every subset of $\{1,2,3\}$ is a face. By the definition of geometric realization, a point of $|K|$ is a function $x:\{1,2,3\}\to[0,1]$ such that $\operatorname{supp}x\in K$ and \begin{align*} x(1)+x(2)+x(3)=1. \end{align*} Since every subset is a face of $K$, the support condition imposes no additional restriction. Writing $t_1=x(1)$, $t_2=x(2)$, and $t_3=x(3)$ gives \begin{align*} |K|=\{(t_1,t_2,t_3)\in\mathbb R^3:t_1,t_2,t_3\in[0,1],\ t_1+t_2+t_3=1\}. \end{align*} This is the same as \begin{align*} |K|=\{(t_1,t_2,t_3)\in\mathbb R^3:t_i\ge 0\text{ for }i=1,2,3,\ t_1+t_2+t_3=1\}, \end{align*} because the conditions $t_i\ge 0$ and $t_1+t_2+t_3=1$ imply $t_i\le t_1+t_2+t_3=1$ for each $i$. The three coordinate vertices are $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$. Every point in the displayed set is their convex combination, since \begin{align*} t_1(1,0,0)+t_2(0,1,0)+t_3(0,0,1)=(t_1,t_2,t_3). \end{align*} Thus $|K|$ is the closed triangular region spanned by these three vertices. If the face $\{1,2,3\}$ is removed while all proper subsets remain, then a point is allowed exactly when its support is a proper subset of $\{1,2,3\}$. This means at least one coordinate is zero, so the realization becomes \begin{align*} \{(t_1,t_2,t_3)\in\mathbb R^3:t_i\ge 0\text{ for }i=1,2,3,\ t_1+t_2+t_3=1,\ t_1t_2t_3=0\}. \end{align*} Equivalently, it is the union of the three line segments in the triangular region cut out by $t_1=0$, $t_2=0$, and $t_3=0$. These three segments are exactly the boundary edges of the triangle, so the realization changes from a filled triangle to its boundary circle. [/example] The filled triangle and its boundary can be refined without changing the space they realize, but a refinement must be described using only the face data of the original complex. The obstruction is that inserting barycentres is geometric language, while the complex itself is combinatorial. Barycentric subdivision resolves this by replacing each old face with a new vertex and using nested chains of old faces as the new simplices. [definition: Barycentric Subdivision] Let $K$ be a finite simplicial complex. The barycentric subdivision $\operatorname{sd}K$ is the simplicial complex whose vertices are the nonempty faces of $K$, and whose faces are chains \begin{align*} \sigma_0 \subsetneq \sigma_1 \subsetneq \cdots \subsetneq \sigma_r \end{align*} of nonempty faces of $K$. [/definition] Subdividing increases the number of vertices and changes the list of facets, so it is not a harmless operation at the combinatorial level. The question is whether these new flags merely retile each old simplex or whether they can alter the topological space being represented. The needed result is that, for finite complexes, barycentric subdivision changes the triangulation but preserves the underlying realization up to homeomorphism. The next theorem is the point where subdivision becomes a legitimate topological tool rather than just a combinatorial refinement. It lets later arguments replace a complex by its face-chain complex while keeping the same underlying polyhedron. In the quoted theorem, $K'$ denotes the barycentric subdivision $\operatorname{sd}K$ just defined above. [quotetheorem:1917] [citeproof:1917] For later applications, the important consequence is that $\operatorname{sd}K$ may replace $K$ whenever chains of faces are easier to use than the original simplices. The replacement preserves the underlying polyhedron while exposing order-complex structure, so topological statements about $|K|$ can be transported to the subdivided complex without changing the space being studied. The finiteness hypothesis is part of the theorem's scope. For locally finite infinite complexes, analogous statements require a more careful topology on the realization; with arbitrary infinite complexes, the same sentence can fail under naive topologies. For instance, if one realizes an infinite simplex on vertices $v_1,v_2,\dots$ as finite-support barycentric coordinate functions inside the product space $[0,1]^{\mathbb N}$, then the sequence of vertices $v_n$ converges to the zero function in the ambient product, which is not a point of the realization. This kind of nonclosed behaviour shows why infinite realizations need separate conventions. The theorem preserves the underlying topological space, but it does not preserve combinatorial data such as the number of vertices, the facets, or whether the complex is flag. Its value is that it allows us to replace a complex by its subdivision whenever the combinatorics of chains is more convenient, especially when passing between simplicial complexes and posets. ## Complexes from Graphs, Posets, and Covers Which combinatorial objects naturally produce spaces? The constructions in this section are functorial recipes: independent sets, cliques, chains, matchings, and intersections of sets all define complexes. The guiding principle is that a compatible finite family becomes a face. [definition: Independence Complex] Let $G=(V,E)$ be a finite graph. The independence complex of $G$ is \begin{align*} \operatorname{Ind}(G)=\{\sigma\subset V : \text{no two distinct vertices of }\sigma\text{ are adjacent in }G\}. \end{align*} [/definition] Independence complexes turn graph constraints into topology. A large face is a large independent set, while the shape of the whole complex records how independent sets overlap. Paths and cycles show the first topological behaviours that can arise from this construction. [example: Independence Complex of a Path] Let $P_3$ be the path on vertices $1,2,3$ with edge set $\{\{1,2\},\{2,3\}\}$. By the definition of the independence complex, a subset $\sigma\subset\{1,2,3\}$ is a face of $\operatorname{Ind}(P_3)$ exactly when no two distinct vertices of $\sigma$ form one of these two edges. The subsets of $\{1,2,3\}$ are \begin{align*} \varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}. \end{align*} The empty set and all one-element subsets are independent, because they contain no pair of distinct vertices. Among the two-element subsets, \begin{align*} \{1,2\}\notin \operatorname{Ind}(P_3) \end{align*} because $\{1,2\}$ is an edge of $P_3$, \begin{align*} \{2,3\}\notin \operatorname{Ind}(P_3) \end{align*} because $\{2,3\}$ is an edge of $P_3$, while \begin{align*} \{1,3\}\in \operatorname{Ind}(P_3) \end{align*} because $\{1,3\}$ is not an edge of $P_3$. Finally, \begin{align*} \{1,2,3\}\notin \operatorname{Ind}(P_3), \end{align*} since it contains the adjacent pair $\{1,2\}$, and also contains the adjacent pair $\{2,3\}$. Therefore \begin{align*} \operatorname{Ind}(P_3)=\{\varnothing,\{1\},\{2\},\{3\},\{1,3\}\}. \end{align*} The only two-element face is $\{1,3\}$, so it contributes one edge with endpoints $\{1\}$ and $\{3\}$. The vertex $\{2\}$ is not contained in any two-element face, because neither $\{1,2\}$ nor $\{2,3\}$ is independent. Hence $\operatorname{Ind}(P_3)$ is one edge $\{1,3\}$ together with the isolated vertex $\{2\}$, showing that the independence complex of a connected graph can be disconnected. [/example] A path already shows disconnectedness. A cycle can go further and create a loop in the resulting complex. [example: Independence Complex of a Cycle] Let $C_5$ have vertex set $\{1,2,3,4,5\}$ and edge set \begin{align*} \{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\}\}. \end{align*} A subset of vertices is a face of $\operatorname{Ind}(C_5)$ exactly when it contains no one of these five adjacent pairs. First, no independent set has three vertices. Indeed, if $1$ is chosen, then $2$ and $5$ cannot be chosen, so a three-element independent set containing $1$ would have to be $\{1,3,4\}$; but $\{3,4\}$ is an edge. The same argument after cyclic relabelling excludes every three-element independent set. Thus every maximal face has at most two vertices. The independent two-element subsets are exactly the nonedges of $C_5$: \begin{align*} \{1,3\},\{1,4\},\{2,4\},\{2,5\},\{3,5\}. \end{align*} For example, $\{1,3\}$ is independent because neither $\{1,3\}$ nor any smaller two-vertex pair inside it is an edge of $C_5$, while $\{1,2\}$ is not independent because it is an edge. Since every singleton is contained in one of the displayed independent pairs, the maximal faces of $\operatorname{Ind}(C_5)$ are precisely these five two-element faces. Therefore $\operatorname{Ind}(C_5)$ is a $1$-dimensional complex with edges \begin{align*} \{1,3\},\{3,5\},\{5,2\},\{2,4\},\{4,1\}. \end{align*} These edges occur consecutively in the vertex order \begin{align*} 1-3-5-2-4-1, \end{align*} and there are no additional edges or $2$-faces. Hence the geometric realization is a polygonal $5$-cycle, so $|\operatorname{Ind}(C_5)|$ is homeomorphic to $S^1$. This shows that an independence complex can have noncontractible topology even when it is built from a finite graph. [/example] Independence complexes turn nonadjacency into compatibility, so they deliberately exclude graph edges from faces. A different problem starts with edges as positive compatibility data. If every pair in a finite vertex set is compatible, then the simplicial complex should include the whole set as a face rather than remembering only its pairwise edges. The clique complex is the construction that performs this filling operation. [definition: Clique Complex] Let $G=(V,E)$ be a finite graph. The clique complex of $G$ is \begin{align*} \operatorname{Cl}(G)=\{\sigma\subset V : \text{every two distinct vertices of }\sigma\text{ are adjacent in }G\}. \end{align*} [/definition] The clique complex fills in every complete subgraph. This construction is also called the flag complex of $G$, because all missing faces are detected by missing edges. A square with one diagonal shows how cliques become filled triangles. [example: Clique Complex of a Square with a Diagonal] Let $G$ have vertex set $\{1,2,3,4\}$ and edge set \begin{align*} \{\{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,3\}\}. \end{align*} By the definition of the clique complex, a subset $\sigma\subset\{1,2,3,4\}$ is a face of $\operatorname{Cl}(G)$ exactly when every two distinct vertices in $\sigma$ are joined by an edge of $G$. The one-element subsets are all cliques, since there are no pairs of distinct vertices to check. The two-element cliques are exactly the edges of $G$, namely \begin{align*} \{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,3\}. \end{align*} For three-element subsets, we check the four possibilities: \begin{align*} \{1,2,3\}\in \operatorname{Cl}(G) \end{align*} because its two-element subsets $\{1,2\}$, $\{2,3\}$, and $\{1,3\}$ are all edges of $G$; \begin{align*} \{1,3,4\}\in \operatorname{Cl}(G) \end{align*} because $\{1,3\}$, $\{3,4\}$, and $\{1,4\}$ are all edges of $G$. On the other hand, \begin{align*} \{1,2,4\}\notin \operatorname{Cl}(G) \end{align*} because $\{2,4\}$ is not an edge, and \begin{align*} \{2,3,4\}\notin \operatorname{Cl}(G) \end{align*} because $\{2,4\}$ is not an edge. Finally, \begin{align*} \{1,2,3,4\}\notin \operatorname{Cl}(G), \end{align*} again because it contains the nonedge $\{2,4\}$. Therefore the facets are precisely $\{1,2,3\}$ and $\{1,3,4\}$. These two triangular faces have common intersection \begin{align*} \{1,2,3\}\cap\{1,3,4\}=\{1,3\}, \end{align*} so $\operatorname{Cl}(G)$ is two filled triangles glued along the diagonal edge $\{1,3\}$. Geometrically, this is a square cut into two triangles by one diagonal, hence a triangulated disk. [/example] Graphs only record pairwise adjacency, but containment, refinement, and divisibility are not naturally symmetric pairwise relations; they are ordered relations. For ordered data, the analogue of a compatible set is a chain: a finite list whose elements can be placed in one increasing sequence. We need a construction that turns this chain condition into the face relation of a simplicial complex while preserving the order-theoretic information. [definition: Order Complex] Let $P$ be a finite poset. The order complex $\Delta(P)$ is the simplicial complex whose vertices are elements of $P$ and whose faces are finite chains \begin{align*} p_0 < p_1 < \cdots < p_r. \end{align*} [/definition] Order complexes convert order-theoretic structure into topology. Barycentric subdivision is the special case where $P$ is the face poset of nonempty faces of a complex. The Boolean lattice gives the standard sphere example. [example: Proper Part of a Boolean Lattice] Let $B_n$ be the Boolean lattice of all subsets of $[n]=\{1,\dots,n\}$ ordered by inclusion, and let \begin{align*} \overline{B}_n=B_n\setminus\{\varnothing,[n]\}. \end{align*} A face of the order complex $\Delta(\overline{B}_n)$ is a chain \begin{align*} A_0\subsetneq A_1\subsetneq \cdots \subsetneq A_r \end{align*} where each $A_i$ is a nonempty proper subset of $[n]$. Let $\partial\Delta^{n-1}$ be the boundary complex of the full simplex on vertex set $[n]$. Its faces are precisely the proper subsets of $[n]$, and its nonempty faces are precisely the nonempty proper subsets of $[n]$. Therefore the vertices of $\operatorname{sd}(\partial\Delta^{n-1})$ are exactly the elements of $\overline{B}_n$. By the definition of barycentric subdivision, a face of $\operatorname{sd}(\partial\Delta^{n-1})$ is a chain of nonempty faces of $\partial\Delta^{n-1}$, hence a chain \begin{align*} A_0\subsetneq A_1\subsetneq \cdots \subsetneq A_r \end{align*} of nonempty proper subsets of $[n]$. This is exactly the same condition defining a face of $\Delta(\overline{B}_n)$, so \begin{align*} \Delta(\overline{B}_n)=\operatorname{sd}(\partial\Delta^{n-1}). \end{align*} By *[Barycentric Subdivision Preserves the Polyhedron](/theorems/1917)*, \begin{align*} |\Delta(\overline{B}_n)| =|\operatorname{sd}(\partial\Delta^{n-1})| \cong |\partial\Delta^{n-1}|. \end{align*} The realization $|\partial\Delta^{n-1}|$ is the boundary of an $(n-1)$-simplex, which is homeomorphic to $S^{n-2}$. Hence \begin{align*} |\Delta(\overline{B}_n)|\cong S^{n-2}. \end{align*} Thus the proper part of the Boolean lattice has order complex equal to the barycentric subdivision of a simplex boundary, so its topology is spherical. [/example] Some graph questions are about choosing edges rather than vertices. The obstruction is that endpoint conflicts are relations among edges, not among the original vertices of the graph. To encode which edge choices can coexist, the simplicial complex must promote graph edges to vertices and use disjointness as the face condition. This is the role of the matching complex. [definition: Matching Complex] Let $G=(V,E)$ be a finite graph. The matching complex $M(G)$ is the simplicial complex whose vertices are the edges of $G$, and whose faces are matchings in $G$. [/definition] A face in $M(G)$ is a collection of graph edges with no shared endpoints. Thus the dimension of a face is one less than the number of edges in the matching. The smallest cycle shows that this construction can be disconnected at once. [example: Matching Complex of a Triangle] Let $G=C_3$ have vertex set $\{1,2,3\}$ and edge set \begin{align*} E(G)=\{\{1,2\},\{2,3\},\{1,3\}\}. \end{align*} By the definition of the matching complex, the vertices of $M(C_3)$ are the edges of $C_3$. Thus the vertex set of $M(C_3)$ is \begin{align*} \bigl\{\{1,2\},\{2,3\},\{1,3\}\bigr\}. \end{align*} A two-element face of $M(C_3)$ would be a pair of disjoint edges in $C_3$. The three possible pairs of graph edges are not disjoint: \begin{align*} \{1,2\}\cap\{2,3\}=\{2\}. \end{align*} Also, \begin{align*} \{1,2\}\cap\{1,3\}=\{1\}. \end{align*} Finally, \begin{align*} \{2,3\}\cap\{1,3\}=\{3\}. \end{align*} Each intersection is nonempty, so no pair of edges is a matching. Therefore $M(C_3)$ has no two-element faces. It also has no higher-dimensional faces, because any matching with at least three edges would contain a two-edge matching as a subset. Hence \begin{align*} M(C_3)=\{\varnothing,\{\{1,2\}\},\{\{2,3\}\},\{\{1,3\}\}\}. \end{align*} So the matching complex of a triangle consists of three isolated vertices, one for each edge of the triangle. [/example] The preceding constructions start from discrete objects, but covers of spaces contain a different kind of combinatorial information. When a family of sets covers a space, the individual sets may be geometrically complicated, while the pattern of which subfamilies meet is finite and easier to compute with. The next construction discards the internal shape of the cover elements and records only the nonempty intersections among subfamilies. [definition: Nerve Complex] Let $\mathcal U=\{U_i\}_{i\in I}$ be a finite family of sets. The nerve of $\mathcal U$ is the simplicial complex \begin{align*} N(\mathcal U)=\{\varnothing\}\cup\left\{\varnothing\ne\sigma\subset I : \bigcap_{i\in\sigma}U_i\ne\varnothing\right\}. \end{align*} [/definition] Because the nerve discards the internal geometry of each set, it can easily lose information if the sets or their overlaps have holes. The obstruction is not the bookkeeping of intersections, but whether each nonempty intersection is topologically simple enough that no hidden homotopy remains inside the cover pieces. Under contractibility hypotheses on all finite intersections, the [nerve theorem](/theorems/6468) identifies when the intersection pattern retains the homotopy type of the union. [remark: Nerve Theorem External Input] We use the following standard form of the nerve theorem as an external topological input. Let $X$ be a paracompact Hausdorff topological space and let $\mathcal U=\{U_i\}_{i\in I}$ be a finite family of open subsets of $X$ with \begin{align*} X=\bigcup_{i\in I}U_i. \end{align*} If every nonempty finite intersection \begin{align*} \bigcap_{i\in\sigma}U_i \end{align*} is either empty or contractible, then $X$ is homotopy equivalent to $|N(\mathcal U)|$. [/remark] The paracompact Hausdorff hypothesis is included so that the open cover is numerable and partitions of unity subordinate to the cover are available. The theorem is also often stated for good covers of CW complexes or polyhedra, where equivalent homotopy-colimit proofs apply. In this course we use it as a bridge from intersection combinatorics to topology: a cover with contractible pieces and contractible overlaps lets the nerve carry the homotopy type of the covered space. Later equivariant and homological arguments often begin by replacing a geometric space by such a nerve, then computing with the resulting finite complex. [example: Three Arcs Covering a Circle] Let $S^1$ be covered by three open arcs $U_1,U_2,U_3$ such that \begin{align*} U_i\cap U_j\ne\varnothing \quad \text{for } i\ne j, \end{align*} but \begin{align*} U_1\cap U_2\cap U_3=\varnothing. \end{align*} Assume the arcs are chosen so that each $U_i$ and each nonempty pairwise intersection $U_i\cap U_j$ is an open arc, hence contractible. By the definition of the nerve, the vertices are $\{1\}$, $\{2\}$, and $\{3\}$, because \begin{align*} U_1\ne\varnothing,\qquad U_2\ne\varnothing,\qquad U_3\ne\varnothing. \end{align*} The two-element faces are exactly \begin{align*} \{1,2\},\{1,3\},\{2,3\}, \end{align*} since the corresponding intersections $U_1\cap U_2$, $U_1\cap U_3$, and $U_2\cap U_3$ are nonempty. There is no three-element face, because \begin{align*} \bigcap_{i\in\{1,2,3\}}U_i=U_1\cap U_2\cap U_3=\varnothing. \end{align*} Therefore \begin{align*} N(\mathcal U)=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}\}. \end{align*} This is the boundary complex of a triangle: it has the three edges but not the filled face $\{1,2,3\}$. Hence $|N(\mathcal U)|$ is a circle. Since every nonempty intersection in the cover is contractible, the hypotheses of the *Nerve Theorem* apply, so $S^1$ is homotopy equivalent to $|N(\mathcal U)|$. Thus the nerve records the circular homotopy type of the cover. [/example] ## Homotopy Type and Collapses How much of a complex matters if we only care about its shape up to continuous deformation? Homotopy type is the flexible invariant used throughout topological combinatorics, while collapsibility is a stronger combinatorial way of simplifying a complex. The difference between the two is important: a complex can be contractible without admitting a sequence of elementary collapses. [definition: Homotopy Equivalence and Contractible Complex] Let $K$ and $L$ be finite simplicial complexes. They have the same homotopy type if $|K|$ and $|L|$ are homotopy equivalent topological spaces. A finite simplicial complex $K$ is contractible if $|K|$ is homotopy equivalent to a point. [/definition] Homotopy equivalence allows continuous deformation and does not insist on preserving the visible simplices. A combinatorial simplification must be more restrictive. Deleting a shared boundary face can change how neighbouring facets are attached, while deleting a boundary piece belonging to only one facet should remove redundant material. The next definition isolates the local condition that makes such a deletion legitimate and names the corresponding elementary move. [definition: Free Face and Elementary Collapse] Let $K$ be a finite simplicial complex. A face $\sigma\in K$ is a free face if there is a unique facet $\tau$ of $K$ such that $\sigma\subsetneq\tau$. The elementary collapse associated to the pair $(\sigma,\tau)$ removes all faces $\eta$ satisfying \begin{align*} \sigma\subset \eta\subset \tau. \end{align*} The resulting subcomplex is denoted $K\searrow K'$. [/definition] A single elementary collapse only removes one locally redundant pair of faces. To certify that an entire complex has no essential shape left, one needs a finite sequence of such local deletions ending at the smallest possible complex. Collapsibility names complexes for which this purely combinatorial reduction to one vertex exists. [definition: Collapsible Complex] A finite simplicial complex $K$ is collapsible if there is a sequence of elementary collapses reducing $K$ to a single vertex. [/definition] A collapse sequence is combinatorial, whereas contractibility is a statement about the realization as a topological space. The possible obstruction is that deleting faces from a combinatorial list might change the realized space rather than merely simplify it. What must be justified is that each allowed elementary collapse corresponds to a homotopy-preserving deformation. The following theorem supplies that bridge, turning a finite collapse sequence to one vertex into a certificate of contractibility. [quotetheorem:6469] [citeproof:6469] This implication turns collapsibility into a usable topological certificate, but every part of the definition is doing work. Here collapsibility is defined only for finite complexes, so termination is built into the notion rather than a separate consequence. For infinite complexes, the delicate question is different: an infinite deletion process needs extra control before the successive local deformation retractions assemble into a deformation of the whole realization. The free-face condition is also essential: removing an arbitrary face from a shared boundary can tear apart neighbouring facets and change homotopy type. The theorem gives only a sufficient condition for contractibility, and the converse fails, so absence of a collapse sequence is not by itself evidence of noncontractibility. Later arguments use collapses when they provide explicit combinatorial reductions, while homological or nerve-theoretic methods are needed when no such certificate is visible. The simplest certificate appears for a simplex itself, where the free faces can be removed one after another. [example: A Filled Triangle Collapses to a Vertex] Let $K$ be the full simplex on vertices $1,2,3$, so \begin{align*} K=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}. \end{align*} The only facet of $K$ is $\{1,2,3\}$, because every proper face is strictly contained in it. Hence the edge $\{1,2\}$ is a free face with unique containing facet $\{1,2,3\}$. The elementary collapse associated to \begin{align*} \sigma=\{1,2\},\qquad \tau=\{1,2,3\} \end{align*} removes exactly the faces $\eta$ with $\{1,2\}\subseteq \eta\subseteq \{1,2,3\}$, namely \begin{align*} \eta=\{1,2\}\quad\text{or}\quad \eta=\{1,2,3\}. \end{align*} After this collapse, the remaining complex is \begin{align*} K_1=\{\varnothing,\{1\},\{2\},\{3\},\{1,3\},\{2,3\}\}. \end{align*} In $K_1$, the facets are $\{1,3\}$ and $\{2,3\}$. The vertex $\{1\}$ is contained in the unique facet $\{1,3\}$, so $\{1\}$ is free. Collapsing the pair \begin{align*} \{1\}\subset \{1,3\} \end{align*} removes $\{1\}$ and $\{1,3\}$, leaving \begin{align*} K_2=\{\varnothing,\{2\},\{3\},\{2,3\}\}. \end{align*} Now $\{2\}$ is contained in the unique facet $\{2,3\}$, so another elementary collapse removes $\{2\}$ and $\{2,3\}$. The remaining complex is \begin{align*} K_3=\{\varnothing,\{3\}\}, \end{align*} which is a single vertex. Thus the filled triangle admits a sequence of elementary collapses to one vertex, so the full $2$-simplex is collapsible. [/example] The converse fails, and this failure matters later because topological methods often prove contractibility or connectivity without giving explicit collapse sequences. [remark: Contractible Need Not Mean Collapsible] There exist finite simplicial complexes whose realizations are contractible but which are not collapsible. The classical examples include triangulations related to the dunce cap. This distinction warns us that homotopy information can be weaker than combinatorial simplification data. [/remark] Cones show the opposite extreme: adding one apex destroys all homotopy and usually gives a direct collapse strategy. They will reappear when we decompose complexes by vertices and links. [example: Cone Construction] Let $K$ be a finite simplicial complex and let $v$ be a new vertex. The cone on $K$ is the join \begin{align*} v*K=\{\sigma\cup\tau:\sigma\in \{\varnothing,\{v\}\},\ \tau\in K\}. \end{align*} Thus every face of $v*K$ is either a face $\tau\in K$ or a face $\{v\}\cup\tau$ with $\tau\in K$. We show that $v*K$ collapses to the single vertex $\{v\}$. Since $K$ is finite, list the nonempty faces of $K$ as \begin{align*} \tau_1,\tau_2,\dots,\tau_m \end{align*} so that whenever $\tau_i\subsetneq \tau_j$, the face $\tau_j$ appears earlier in the list than $\tau_i$. Equivalently, we remove larger faces of $K$ before their proper subfaces. At the first step, take $\tau_1$ maximal among nonempty faces of $K$. Then $\tau_1$ is contained in the cone face $\{v\}\cup\tau_1$. If a remaining facet of $v*K$ contains $\tau_1$, it must be of the form $\{v\}\cup\eta$ with $\tau_1\subseteq \eta\in K$. Maximality of $\tau_1$ gives $\eta=\tau_1$, so the unique containing facet is $\{v\}\cup\tau_1$. Hence $\tau_1$ is a free face, and the elementary collapse removes precisely \begin{align*} \tau_1 \qquad\text{and}\qquad \{v\}\cup\tau_1, \end{align*} because these are the faces $\alpha$ satisfying \begin{align*} \tau_1\subseteq \alpha\subseteq \{v\}\cup\tau_1. \end{align*} Continue through the ordered list. Suppose $\tau_i$ is the next nonempty face of $K$ not yet removed. Any remaining facet containing $\tau_i$ has the form $\{v\}\cup\eta$ with $\tau_i\subseteq\eta\in K$. If $\eta\ne\tau_i$, then $\tau_i\subsetneq\eta$, so $\eta$ appeared earlier in the list. The earlier collapse for $\eta$ removed $\{v\}\cup\eta$, so it is no longer present. Therefore the only remaining facet containing $\tau_i$ is $\{v\}\cup\tau_i$, and the collapse removes \begin{align*} \tau_i \qquad\text{and}\qquad \{v\}\cup\tau_i. \end{align*} After all nonempty faces of $K$ have been removed in this way, the only remaining faces are \begin{align*} \varnothing \qquad\text{and}\qquad \{v\}. \end{align*} Thus $v*K$ collapses to the single vertex $\{v\}$, so it is collapsible. By *[Collapsible Complexes Are Contractible](/theorems/6469)*, the cone $v*K$ is contractible. Coning therefore preserves the base complex as a visible subcomplex but destroys its homotopy type by adding the apex $v$. [/example] The constructions in this chapter will be combined with reduced homology, exact sequences, and connectivity estimates in Chapter 2. Nerves turn intersection problems into finite complexes, order complexes translate poset structure into chain topology, and graph complexes supply the independence, clique, and matching examples on which the later calculations are tested. For now, the main point is that many combinatorial problems naturally produce simplicial complexes, and their topology is controlled by links, joins, subdivisions, nerves, and collapses. Once combinatorial data has been encoded as a simplicial complex, the next question is how to measure its topology in a way that detects obstruction. Homology, connectivity, and the language of links and joins provide exactly that toolset, so Chapter 2 turns the geometric dictionary from Chapter 1 into computable invariants. # 2. Homology, Connectivity, and Obstruction Language This chapter turns the simplicial complexes, nerves, links, joins, and collapses from Chapter 1 into algebraic invariants that can be computed, estimated, and compared. The main point is not homology for its own sake, but a working language for saying that a complex has no low-dimensional holes, or that a map cannot exist because a topological obstruction survives. We move from reduced homology and Euler characteristic to exact sequences, then to connectivity estimates for joins and deleted joins, which are the constructions that later support Borsuk-Ulam type arguments. ## Measuring Holes in Finite Complexes What information about a finite simplicial complex survives after we forget the labels of its vertices and remember only how its faces are glued together? The first answer is homology: it records cycles modulo boundaries, and reduced homology adjusts the degree-zero term so that connectedness fits the same pattern as higher-dimensional hole detection. Let $K$ be a finite simplicial complex and let $K_i$ denote its set of $i$-dimensional faces. We use coefficients in a field $k$ unless a different coefficient ring is specified; this avoids torsion in the first pass and makes Betti numbers dimensions of vector spaces. To turn faces into algebra, we first need a vector space whose basis consists of oriented faces. [definition: Simplicial Chain Group] For $i \ge 0$, the $i$-th simplicial chain group of $K$ over $k$ is the $k$-vector space \begin{align*} C_i(K;k) := k\langle [v_0,\dots,v_i] : \{v_0,\dots,v_i\} \in K,\ v_0<\cdots<v_i\rangle. \end{align*} For $i < 0$, set $C_i(K;k)=0$. [/definition] The ordering of vertices fixes signs in a basis for chains. Since holes should be detected by whether a formal sum has boundary zero, the next construction is the signed map that sends each face to its codimension-one boundary. [definition: Simplicial Boundary Map] For $i\ge 1$, the boundary map $\partial_i:C_i(K;k)\to C_{i-1}(K;k)$ is the $k$-[linear map](/page/Linear%20Map) defined on oriented faces by \begin{align*} \partial_i[v_0,\dots,v_i] = \sum_{j=0}^{i}(-1)^j[v_0,\dots,\widehat{v_j},\dots,v_i]. \end{align*} In degree $0$, set $\partial_0:C_0(K;k)\to C_{-1}(K;k)=0$ to be the zero map. [/definition] The boundary of a boundary vanishes, so cycles and boundaries form a quotient. Ordinary degree-zero homology counts connected components, but in this course it is more convenient for a connected nonempty complex to have no degree-zero reduced homology; this motivates the reduced homology definition with an augmentation. [definition: Reduced Homology] The augmented chain complex of $K$ is \begin{align*} \cdots \to C_1(K;k) \xrightarrow{\partial_1} C_0(K;k) \xrightarrow{\varepsilon} k \xrightarrow{0} 0, \end{align*} where $\varepsilon(\sum a_v[v])=\sum a_v$. The reduced homology groups are \begin{align*} \widetilde{H}_i(K;k) := \ker \partial_i / \operatorname{im}\partial_{i+1}\quad (i\ge 1), \end{align*} with \begin{align*} \widetilde{H}_0(K;k):=\ker \varepsilon / \operatorname{im}\partial_1, \end{align*} and \begin{align*} \widetilde{H}_{-1}(K;k):=\ker(0:k\to 0)/\operatorname{im}\varepsilon=k/\operatorname{im}\varepsilon. \end{align*} [/definition] For a nonempty complex, the augmentation $\varepsilon$ is surjective, so $\widetilde{H}_{-1}(K;k)=0$. For the void complex, $C_0(K;k)=0$ and $\operatorname{im}\varepsilon=0$, so this convention gives $\widetilde{H}_{-1}(\varnothing;k)\cong k$. The empty complex enters mainly through joins and deleted constructions, where this reduced convention keeps formulas uniform. [example: Boundary Of A Simplex] Let $\Delta^d$ have ordered vertices $0,\dots,d$, and let $K=\partial\Delta^d$ consist of all proper faces. Thus $C_i(K;k)=C_i(\Delta^d;k)$ for $0\le i\le d-1$, while $C_d(K;k)=0$. The augmented chain complex of the full simplex $\Delta^d$ is exact because $\Delta^d$ is a cone. Therefore, for every degree below the top boundary degree, the boundary maps in $K$ are the same as the corresponding maps in $\Delta^d$, so no reduced homology survives there. More explicitly, for $0\le i\le d-2$ we have \begin{align*} \ker(\partial_i:C_i(K;k)\to C_{i-1}(K;k))=\operatorname{im}(\partial_{i+1}:C_{i+1}(K;k)\to C_i(K;k)). \end{align*} In degree $0$, when $d\ge 2$, the same statement is read with the augmentation: $\ker\varepsilon=\operatorname{im}\partial_1$. Hence $\widetilde{H}_i(K;k)=0$ for $i<d-1$. It remains to identify the top reduced group. In the full simplex, the boundary of the missing $d$-simplex is \begin{align*} z=\partial_d[0,1,\dots,d]=\sum_{j=0}^{d}(-1)^j[0,\dots,\widehat{j},\dots,d]. \end{align*} Its boundary is zero because each codimension-two face appears twice with opposite signs. For $0\le p<q\le d$, the face obtained by deleting $p$ and $q$ occurs once by first deleting $q$ after $p$, with sign $(-1)^p(-1)^{q-1}$, and once by first deleting $p$ after $q$, with sign $(-1)^q(-1)^p$. The total coefficient is \begin{align*} (-1)^p(-1)^{q-1}+(-1)^q(-1)^p=(-1)^{p+q-1}+(-1)^{p+q}=0. \end{align*} Thus $z$ is a cycle. Exactness of the augmented chain complex of $\Delta^d$ says that the relevant kernel in degree $d-1$ is exactly the one-dimensional image of $\partial_d:C_d(\Delta^d;k)\to C_{d-1}(\Delta^d;k)$, generated by $z$. Since $K$ has no $d$-simplex, $\operatorname{im}\partial_d=0$ inside the chain complex of $K$. Therefore \begin{align*} \widetilde{H}_{d-1}(K;k)=k\langle z\rangle/0\cong k. \end{align*} For $d=1$, this same statement means $\widetilde{H}_0(K;k)=\ker\varepsilon/0$, generated by $[1]-[0]$. In the smallest circular case $d=2$, the boundary is a triangle and \begin{align*} z=[1,2]-[0,2]+[0,1]. \end{align*} Its boundary is \begin{align*} \partial_1z=([2]-[1])-([2]-[0])+([1]-[0])=0. \end{align*} There is no $2$-simplex in $K$, so this $1$-cycle is not a boundary in $K$; it is the single reduced $1$-dimensional homology class. [/example] This example shows that the position and number of nonzero homology groups are the data we will repeatedly compare. To make those comparisons numerical, we package the dimension of each reduced homology group as a Betti number. [definition: Betti Number] For each $i\in\mathbb Z$, the $i$-th reduced Betti number over $k$ is the function \begin{align*} \widetilde{\beta}_i(-;k):\{\text{finite simplicial complexes}\}\to \mathbb Z_{\ge 0} \end{align*} defined by \begin{align*} \widetilde{\beta}_i(K;k):=\dim_k\widetilde{H}_i(K;k). \end{align*} [/definition] Betti numbers are topological, while face numbers are combinatorial. The alternating face count is the simplest invariant connecting those two kinds of data; this motivates the reduced Euler characteristic. [definition: Reduced Euler Characteristic] The reduced Euler characteristic is the function \begin{align*} \widetilde{\chi}:\{\text{finite simplicial complexes}\}\to\mathbb Z \end{align*} defined by \begin{align*} \widetilde{\chi}(K):=\sum_{i\ge -1}(-1)^i f_i(K), \end{align*} where $f_i(K)$ is the number of $i$-dimensional faces and $f_{-1}(K)=1$ for the empty face. [/definition] The unreduced Euler characteristic is $\chi(K)=\widetilde{\chi}(K)+1$ for a nonempty complex. At this point there are two different kinds of data: face numbers count the chosen triangulation, while homology measures holes and is invariant under subdivision. The obstruction is that a face count could appear to depend on the particular complex, so we need a reason that its alternating sum survives passage to homology. In the theorem below, $\chi_{\mathbb Z}(X)$ denotes the alternating sum of the ranks of the integral homology groups of $X$, while $\chi_{\mathbb F}(X)$ denotes the alternating sum of the dimensions of homology over a field $\mathbb F$. The following formula says that these homological Euler characteristics agree with the combinatorial Euler characteristic when the relevant groups are finite. [quotetheorem:2266] [citeproof:2266] Finiteness is doing real work here: the alternating sums of chain dimensions are finite, so the cancellation in the proof is legitimate. If $K$ is an infinite discrete complex with countably many vertices, then the face count gives an infinite $f_0$ and the reduced degree-zero homology has countable dimension; the displayed equality is no longer an identity of integers. Over a field the right-hand side is phrased in terms of Betti numbers because homology groups are vector spaces; over a general coefficient ring one must replace dimension by rank, and torsion information is invisible to the Euler characteristic. For infinite complexes the same formula needs hypotheses such as finite-dimensional homology in only finitely many degrees, otherwise neither side may be a well-defined integer. The formula also has a sharp limitation: it gives only an alternating sum, not the individual homology groups. For example, a point has reduced Euler characteristic $0$, and a space with one reduced $0$-dimensional class and one reduced $1$-dimensional class also has reduced Euler characteristic $0$, but their reduced homology groups are not the same. Thus this formula is most useful after independent reasoning has shown that only a few homology groups can survive; then an alternating face count determines the remaining Betti number. [example: Wedge Of Circles] Let $K$ be formed from cycle graphs $C_{n_1},\dots,C_{n_r}$ by identifying one chosen vertex from each cycle to a single common vertex. The graph $K$ is connected and nonempty, so $\operatorname{im}\partial_1=\ker\varepsilon$ in degree $0$, and therefore $\widetilde{H}_0(K;k)=0$. Write $f_0=f_0(K)$ and $f_1=f_1(K)$. Since $K$ is a graph, $C_2(K;k)=0$, so \begin{align*} \widetilde{H}_1(K;k)=H_1(K;k)=\ker(\partial_1:C_1(K;k)\to C_0(K;k)). \end{align*} Choose a spanning tree $T\subset K$. Because $K$ is connected, $T$ has $f_0-1$ edges. Let the common vertex be $v_0$, and orient each tree edge away from $v_0$. For every non-root vertex $v$, the unique tree path from $v_0$ to $v$ expresses $[v]-[v_0]$ as a sum of boundaries of oriented tree edges along that path, with signs chosen according to the path orientation. Hence the boundary vectors of the tree edges span \begin{align*} \ker\varepsilon=\left\{\sum_v a_v[v]:\sum_v a_v=0\right\}. \end{align*} The vectors $[v]-[v_0]$ for $v\ne v_0$ are linearly independent: if $\sum_{v\ne v_0} b_v([v]-[v_0])=0$, then the coefficient of $[v]$ is $b_v$, so every $b_v=0$. Thus $\dim_k\ker\varepsilon=f_0-1$, and since $\operatorname{im}\partial_1=\ker\varepsilon$, we have \begin{align*} \operatorname{rank}\partial_1=f_0-1. \end{align*} By rank-nullity applied to $\partial_1:C_1(K;k)\to C_0(K;k)$, \begin{align*} \dim_k\ker\partial_1=\dim_k C_1(K;k)-\operatorname{rank}\partial_1. \end{align*} Substituting $\dim_k C_1(K;k)=f_1$ and $\operatorname{rank}\partial_1=f_0-1$ gives \begin{align*} \widetilde{\beta}_1(K;k)=f_1-f_0+1. \end{align*} For the wedge of the $r$ cycles, the edge count is \begin{align*} f_1=n_1+\cdots+n_r. \end{align*} Before identification the cycles have $n_1+\cdots+n_r$ vertices, and identifying $r$ chosen vertices into one vertex reduces the vertex count by $r-1$, so \begin{align*} f_0=n_1+\cdots+n_r-(r-1). \end{align*} Therefore \begin{align*} \widetilde{\beta}_1(K;k)=(n_1+\cdots+n_r)-\bigl(n_1+\cdots+n_r-(r-1)\bigr)+1=r. \end{align*} Finally, because a graph has no faces in dimensions $i\ge 2$ and $f_{-1}=1$, \begin{align*} \widetilde{\chi}(K)=-1+f_0-f_1. \end{align*} Substituting the same face counts gives \begin{align*} \widetilde{\chi}(K)=-1+\bigl(n_1+\cdots+n_r-(r-1)\bigr)-(n_1+\cdots+n_r)=-r. \end{align*} Thus the wedge has exactly one kind of surviving reduced homology: $\widetilde{H}_0(K;k)=0$ and $\dim_k\widetilde{H}_1(K;k)=r$, so the reduced Euler characteristic is the alternating record of those $r$ independent circle classes. [/example] The wedge example illustrates a common pattern: rather than remembering every Betti number, we often only need a vanishing range. This motivates a compact connectivity language for saying that all low-dimensional reduced homology groups vanish. [definition: Homological Connectivity] A nonempty finite simplicial complex $K$ is homologically $r$-connected over $k$ if \begin{align*} \widetilde{H}_i(K;k)=0 \quad \text{for all } -1\le i\le r. \end{align*} The homological connectivity of $K$ over $k$ is \begin{align*} \operatorname{hconn}_k:\{\text{nonempty finite simplicial complexes}\}\to \mathbb Z\cup\{\infty\}, \end{align*} defined by \begin{align*} \operatorname{hconn}_k(K):=\sup\{r\in\mathbb Z : K \text{ is homologically } r\text{-connected over }k\}. \end{align*} [/definition] Thus homological $0$-connected means connected, and homological $1$-connected means connected with vanishing first reduced homology. This is weaker than simple connectedness, but it is the version most directly controlled by exact sequences and spectral estimates. [remark: Homotopical Versus Homological Connectivity] A space is $r$-connected in the homotopy sense if $\pi_i$ vanishes for $0\le i\le r$. Homotopical connectivity implies homological connectivity under the usual hypotheses by the Hurewicz theorem, but the converse can fail. Many combinatorial arguments only require the homological statement because the obstruction lives in cohomology. [/remark] ## Exact Sequences as Computational Tools How do we compute homology without writing every boundary matrix? Exact sequences let us cut a complex into pieces, compute locally, and reconstruct global information from the algebraic failure of cycles to glue or bound. The first tool compares a complex with a subcomplex. This is useful when a complex is built by attaching faces, or when a forbidden subcomplex is removed. To make such a comparison, we quotient out the chains already present in the subcomplex. [definition: Relative Chain Complex] Let $L\subset K$ be a subcomplex. The relative chain group is \begin{align*} C_i(K,L;k):=C_i(K;k)/C_i(L;k). \end{align*} The relative differential is the $k$-linear map \begin{align*} d_i:C_i(K,L;k)\to C_{i-1}(K,L;k), \qquad d_i([c])=[\partial_i c], \end{align*} where $[c]$ denotes the class of $c\in C_i(K;k)$ modulo $C_i(L;k)$. [/definition] Relative chains record the part of $K$ not already present in $L$, while still remembering when their boundaries land inside $L$. This motivates the long exact sequence connecting the homology of $L$, $K$, and the relative complex. [quotetheorem:2249] [citeproof:2249] The connecting homomorphism is often the important part: it measures the boundary left behind when a relative cycle is lifted to an absolute chain. The assumption that $L$ is a subcomplex is necessary because $C_i(L;k)$ must be a subspace preserved by the boundary operation; otherwise the quotient groups need not form a chain complex. For instance, if one tries to quotient a triangulated interval by a single interior point that is not a subcomplex of the chosen triangulation, then the boundary of an edge may not descend to a well-defined class modulo the proposed subspace. The finiteness hypothesis keeps the statement inside the finite simplicial category used throughout the chapter, where all chain groups are finite-dimensional and every displayed reduced group is an ordinary finite-dimensional vector space. The construction of a long exact sequence itself is more general, but for these notes finiteness is the condition that matches the surrounding Betti-number and Euler-characteristic language. Exactness also does not compute every group automatically. It says that the image of each map equals the kernel of the next, so the dimensions and maps surrounding an unknown term constrain it, but extension data and the ranks of connecting maps may still have to be determined separately. In applications, the sequence becomes powerful only when the homology of two of the three objects, or enough information about the maps between them, is already known. [example: Attaching A Two Cell To A Circle] Let $K$ be a triangulated disk and let $L=\partial K$. Choose an orientation of the disk and orient each $2$-simplex accordingly. The fundamental relative $2$-chain is \begin{align*} c=\sum_{\tau\in K_2}\epsilon_\tau[\tau], \end{align*} where $\epsilon_\tau\in\{1,-1\}$ records whether the ordered simplex agrees with the chosen orientation. In $\partial c$, every interior edge occurs in exactly two adjacent triangles with opposite induced orientations, so those two coefficients cancel. The only remaining terms are the oriented boundary edges of $L$, hence \begin{align*} \partial c=z_L, \end{align*} where $z_L$ is the simplicial $1$-cycle going once around the boundary circle. In the relative chain complex $C_*(K,L;k)$, the boundary chain $z_L$ is zero because it lies in $C_1(L;k)$. Therefore \begin{align*} d_2[c]=[\partial c]=[z_L]=0. \end{align*} Thus $[c]$ is a relative $2$-cycle. Since a disk relative to its boundary has no relative $1$-cycles and one relative top class, its relative homology is \begin{align*} H_2(K,L;k)=k\langle[c]\rangle. \end{align*} Also, \begin{align*} H_1(K,L;k)=0. \end{align*} The connecting homomorphism sends a relative cycle represented by a chain $u$ to the homology class of $\partial u$ in $L$, by *[Long Exact Sequence Of A Pair](/theorems/2249)*. Applying this to $c$ gives \begin{align*} \delta([c])=[\partial c]=[z_L]\in \widetilde{H}_1(L;k). \end{align*} The cycle $z_L$ generates the reduced first homology of the boundary circle, so \begin{align*} \operatorname{im}\delta=\widetilde{H}_1(L;k). \end{align*} Now take the exact part of the pair sequence \begin{align*} H_2(K,L;k)\xrightarrow{\delta}\widetilde{H}_1(L;k)\to \widetilde{H}_1(K;k)\to H_1(K,L;k). \end{align*} Since $\operatorname{im}\delta=\widetilde{H}_1(L;k)$, exactness gives \begin{align*} \ker\bigl(\widetilde{H}_1(L;k)\to \widetilde{H}_1(K;k)\bigr)=\widetilde{H}_1(L;k). \end{align*} Hence the map $\widetilde{H}_1(L;k)\to \widetilde{H}_1(K;k)$ is the zero map, so the next map has kernel \begin{align*} \ker\bigl(\widetilde{H}_1(K;k)\to H_1(K,L;k)\bigr)=0. \end{align*} But $H_1(K,L;k)=0$, so the map $\widetilde{H}_1(K;k)\to H_1(K,L;k)$ has zero target and therefore has kernel all of $\widetilde{H}_1(K;k)$. Thus \begin{align*} \widetilde{H}_1(K;k)=0. \end{align*} Finally, the disk $K$ is nonempty and connected, so \begin{align*} \ker\varepsilon=\operatorname{im}\partial_1. \end{align*} Therefore \begin{align*} \widetilde{H}_0(K;k)=\ker\varepsilon/\operatorname{im}\partial_1=0. \end{align*} The relative top class of the disk maps exactly to the boundary circle class, so attaching the two-dimensional filling kills that circle class and leaves no reduced homology in degrees $0$ or $1$. [/example] The pair sequence handles attachment to a single subcomplex. When a complex is presented as a union of two simpler subcomplexes, the corresponding computational question is how cycles in the union split across the two pieces; this motivates Mayer-Vietoris. [quotetheorem:6470] [citeproof:6470] Mayer-Vietoris turns a topological computation into a cover design problem. The hypotheses $K=A\cup B$ and $A,B\subset K$ being subcomplexes ensure that every simplex of $K$ lies in at least one chain complex on the left and that $A\cap B$ is itself a subcomplex with a well-defined chain complex. If the intersection is ignored, cycles can be counted twice or glued with the wrong boundary; two contractible arcs covering a circle have homology only because their two-point intersection contributes a reduced $0$-class. The finite hypothesis again keeps the theorem aligned with the finite-dimensional chain complexes used in the chapter. Mayer-Vietoris can be formulated for broader spaces and covers, but then one must specify the homology theory and any local finiteness or excision assumptions separately. The sequence also does not decide the homology of $K$ from the abstract groups alone. The maps matter: a zero connecting map and an injective connecting map can give different middle homology groups even when the displayed groups have the same dimensions. We choose $A$ and $B$ so that they and their intersection are simpler than $K$, and then we still track the maps that describe how the pieces are glued. [example: A Cycle As Two Paths] Let the vertices of $C_n$ be $v_0,\dots,v_{n-1}$ in cyclic order, with indices read modulo $n$. Choose $1\le m\le n-1$, let $A$ be the path with edges $[v_0,v_1],\dots,[v_{m-1},v_m]$, and let $B$ be the complementary path with edges $[v_m,v_{m+1}],\dots,[v_{n-1},v_0]$. Then \begin{align*} A\cap B=\{v_0,v_m\}. \end{align*} Each of $A$ and $B$ is a nonempty connected path with no $1$-cycles, so \begin{align*} \widetilde{H}_1(A;k)\oplus\widetilde{H}_1(B;k)=0. \end{align*} Also, \begin{align*} \widetilde{H}_0(A;k)\oplus\widetilde{H}_0(B;k)=0. \end{align*} For the two-point complex $A\cap B$, there are no edges, so $\operatorname{im}\partial_1=0$. The augmentation satisfies \begin{align*} \ker\varepsilon=\{a[v_0]+b[v_m]:a+b=0\}. \end{align*} Since $a+b=0$ means $b=-a$, every element of $\ker\varepsilon$ has the form \begin{align*} a[v_0]-a[v_m]=-a([v_m]-[v_0]). \end{align*} Hence \begin{align*} \ker\varepsilon=k\langle [v_m]-[v_0]\rangle. \end{align*} Therefore \begin{align*} \widetilde{H}_0(A\cap B;k)=k\langle [v_m]-[v_0]\rangle. \end{align*} The relevant part of *Mayer Vietoris Sequence* is \begin{align*} \widetilde{H}_1(A;k)\oplus\widetilde{H}_1(B;k)\to \widetilde{H}_1(K;k)\xrightarrow{\delta}\widetilde{H}_0(A\cap B;k)\to \widetilde{H}_0(A;k)\oplus\widetilde{H}_0(B;k). \end{align*} Substituting the vanishing groups just computed gives \begin{align*} 0\to \widetilde{H}_1(K;k)\xrightarrow{\delta}k\langle [v_m]-[v_0]\rangle\to 0. \end{align*} Exactness forces $\delta$ to be both injective and surjective, so \begin{align*} \widetilde{H}_1(K;k)\cong k. \end{align*} The generator can be seen at the chain level. Let \begin{align*} z=[v_0,v_1]+\cdots+[v_{n-2},v_{n-1}]+[v_{n-1},v_0]. \end{align*} Its boundary is the telescoping sum \begin{align*} \partial z=([v_1]-[v_0])+\cdots+([v_{n-1}]-[v_{n-2}])+([v_0]-[v_{n-1}]). \end{align*} Every vertex appears once with coefficient $1$ and once with coefficient $-1$, so \begin{align*} \partial z=0. \end{align*} Split $z=a+b$, where \begin{align*} a=[v_0,v_1]+\cdots+[v_{m-1},v_m] \end{align*} and \begin{align*} b=[v_m,v_{m+1}]+\cdots+[v_{n-2},v_{n-1}]+[v_{n-1},v_0]. \end{align*} Then the boundary of $a$ is \begin{align*} \partial a=([v_1]-[v_0])+\cdots+([v_m]-[v_{m-1}]). \end{align*} The intermediate vertex terms cancel, leaving \begin{align*} \partial a=[v_m]-[v_0]. \end{align*} Similarly, \begin{align*} \partial b=([v_{m+1}]-[v_m])+\cdots+([v_{n-1}]-[v_{n-2}])+([v_0]-[v_{n-1}]). \end{align*} Again the intermediate terms cancel, so \begin{align*} \partial b=[v_0]-[v_m]. \end{align*} Thus the Mayer-Vietoris connecting map sends the cycle class of $z$ to the reduced $0$-class represented by $[v_m]-[v_0]$, up to the sign determined by the chosen convention for the connecting map. The two endpoints in the overlap are the only obstruction to gluing the two contractible paths without creating a circle, and that obstruction becomes the unique reduced $1$-homology class of $C_n$. [/example] For larger covers, repeatedly applying Mayer-Vietoris becomes hard to organize. Pairwise gluing data is not enough: three sets can have all pairwise intersections nonempty while the triple intersection is empty, and this distinction changes the resulting cycle pattern. We therefore need a single combinatorial object that remembers every finite intersection at once, including which higher intersections are absent. The construction should forget the internal geometry of each covering subcomplex and retain only the incidence pattern needed for cover arguments. This motivates the nerve of a cover, which records the pattern of all nonempty intersections in one simplicial complex. The definition below turns a cover into a combinatorial object by assigning one vertex to each member of the cover and one simplex to each nonempty common intersection. This is the right data for later comparison theorems because it records exactly which subfamilies can contribute simultaneous local information. [definition: Nerve Of A Cover] Let $K$ be a simplicial complex and let $\mathcal U=\{K_a:a\in A\}$ be a finite family of subcomplexes with $K=\bigcup_{a\in A}K_a$. The nerve $N(\mathcal U)$ is the simplicial complex on vertex set $A$ whose faces are the finite sets $\sigma\subset A$ such that \begin{align*} \bigcap_{a\in\sigma}K_a \ne \varnothing. \end{align*} [/definition] The useful hypothesis is not merely that intersections are nonempty, but that they have enough vanishing homology. This motivates a [homological nerve theorem](/theorems/6471): under connectivity assumptions on intersections, the nerve carries the low-dimensional homology of the union. [quotetheorem:6471] [citeproof:6471] This theorem is the formal justification for replacing a complicated union by an intersection pattern, but the intersection hypotheses are essential. A concrete failure already occurs for a cycle graph $C_n$ covered by two contractible paths $A$ and $B$ whose intersection consists of two isolated vertices. The nerve is a single edge, hence has no reduced homology, while $C_n$ has $\widetilde{H}_1(C_n;k)\cong k$; the disconnected intersection has supplied the missing class. The connectivity assumptions are exactly what prevents hidden homology inside the intersections from contributing in the low degrees being compared. The conclusion is also deliberately limited. It gives isomorphisms only through degree $r$, while in degree $r+1$ it gives only a surjection, so a class in the nerve in that degree must lift from $K$ but two classes in $K$ may still become equal in the nerve. Above degree $r+1$ the theorem makes no claim. Later, equivariant versions of the same idea allow us to preserve group actions while simplifying complexes, but they require similarly careful control of all fixed-point and intersection data. [example: Three Contractible Sets With Circular Nerve] Suppose $K=K_1\cup K_2\cup K_3$, where each $K_i$ is contractible, each $K_i\cap K_j$ for $i\ne j$ is nonempty and contractible, and $K_1\cap K_2\cap K_3=\varnothing$. The nerve $N$ has vertices $1,2,3$, has the three edges $\{1,2\}$, $\{2,3\}$, and $\{1,3\}$ because the pairwise intersections are nonempty, and has no $2$-simplex because the triple intersection is empty. Hence $N=\partial\Delta^2$. The hypotheses of the *Homological Nerve Theorem* hold with $r=1$. For a one-element set $\sigma$, the required connectivity is \begin{align*} 1-|\sigma|+2=1-1+2=2, \end{align*} and each $K_i$ is contractible, so each $K_i$ has zero reduced homology in every degree. For a two-element set $\sigma$, the required connectivity is \begin{align*} 1-|\sigma|+2=1-2+2=1, \end{align*} and each nonempty pairwise intersection is contractible. For $|\sigma|=3$, there is no condition to check because $K_1\cap K_2\cap K_3=\varnothing$. Therefore \begin{align*} \widetilde{H}_i(K;k)\cong \widetilde{H}_i(N;k)\quad\text{for }i\le 1. \end{align*} It remains to compute the reduced homology of $N$. Orient the edges as $[1,2]$, $[2,3]$, and $[1,3]$. The boundary map gives \begin{align*} \partial_1[1,2]=[2]-[1]. \end{align*} Also, \begin{align*} \partial_1[2,3]=[3]-[2]. \end{align*} And \begin{align*} \partial_1[1,3]=[3]-[1]. \end{align*} For \begin{align*} z=[1,2]+[2,3]-[1,3], \end{align*} we have \begin{align*} \partial_1z=([2]-[1])+([3]-[2])-([3]-[1]). \end{align*} Expanding the signs, \begin{align*} \partial_1z=[2]-[1]+[3]-[2]-[3]+[1]=0. \end{align*} Conversely, let \begin{align*} u=a[1,2]+b[2,3]+c[1,3]. \end{align*} Then \begin{align*} \partial_1u=a([2]-[1])+b([3]-[2])+c([3]-[1]). \end{align*} Collecting coefficients of the vertex basis gives \begin{align*} \partial_1u=(-a-c)[1]+(a-b)[2]+(b+c)[3]. \end{align*} Thus $\partial_1u=0$ exactly when \begin{align*} -a-c=0. \end{align*} The same condition also requires \begin{align*} a-b=0. \end{align*} And it requires \begin{align*} b+c=0. \end{align*} These equations give $b=a$ and $c=-a$, so \begin{align*} u=a[1,2]+a[2,3]-a[1,3]=a z. \end{align*} Therefore \begin{align*} \ker\partial_1=k\langle z\rangle. \end{align*} Since $N$ has no $2$-simplices, $C_2(N;k)=0$, so $\operatorname{im}\partial_2=0$. Hence \begin{align*} \widetilde{H}_1(N;k)=H_1(N;k)=\ker\partial_1/\operatorname{im}\partial_2=k\langle z\rangle/0\cong k. \end{align*} The graph $N$ is connected, so $\widetilde{H}_0(N;k)=0$. Applying the nerve isomorphisms gives \begin{align*} \widetilde{H}_0(K;k)=0 \end{align*} and \begin{align*} \widetilde{H}_1(K;k)\cong k. \end{align*} The theorem gives no conclusion about $\widetilde{H}_i(K;k)$ for $i\ge 2$, because with $r=1$ its isomorphism range stops at degree $1$. [/example] ## Joins, Deleted Joins, and Connectivity Estimates Why do joins appear so often in Borsuk-Ulam methods? They are a way to combine independent choices: a point of a join records a convex mixture of points from several complexes, and a deleted join records several choices that are forced to use disjoint faces. The join operation was defined combinatorially in Chapter 1. Here we focus on its homological effect, so we restate the definition in the form needed to identify its chains. [definition: Join Of Complexes] Let $K$ and $L$ be simplicial complexes on disjoint vertex sets. Their join is \begin{align*} K*L:=\{\sigma\cup\tau : \sigma\in K,\ \tau\in L\}. \end{align*} [/definition] A simplex from $K*L$ consists of a face of $K$ and a face of $L$ chosen independently. The homological question is how this independent choice changes cycles and dimensions. A join adds a suspension-like direction, so ordinary product intuition gives the wrong degree unless the shift is accounted for. The symbol $\otimes_k$ denotes [tensor product](/page/Tensor%20Product) over the field $k$: for finite-dimensional $k$-vector spaces it is the vector space generated by formal products $u\otimes v$, bilinear in $u$ and $v$, and it records independent choices of a homology class from each factor. The following formula records this tensor-product contribution with the correct reduced-degree shift. [quotetheorem:6472] [citeproof:6472] The field hypothesis removes Tor terms from the [Kunneth formula](/theorems/3933); with integral coefficients the same slogan needs an additional torsion contribution for the suspended tensor complex. For instance, if $K=L=\mathbb{R}P^2$ are triangulated real projective planes, then $\widetilde{H}_1(K;\mathbb Z)\cong \mathbb Z/2$ and $\widetilde{H}_2(K;\mathbb Z)=0$. The tensor term $\widetilde{H}_1(K;\mathbb Z)\otimes \widetilde{H}_1(L;\mathbb Z)$ contributes in degree $3$ of the join, while the corresponding Tor term contributes one degree higher. These torsion classes are invisible in the field-coefficient formula when the characteristic is not $2$. Reduced homology is also not cosmetic: it accounts for the suspension shift in the join and makes examples such as $K*\varnothing$ and joins with contractible complexes behave uniformly. The disjoint-vertex convention matters because the join is meant to record two independent choices; if the same vertex set is used without relabelling, the combinatorial object is a different complex. Finiteness is another real hypothesis in the stated form, because the chain-level identification is being used with finite-dimensional homology groups and finite direct sums in each degree. If $K$ is an infinite discrete complex and $L$ is a point, then the join is an infinite cone and has different finiteness behaviour from the finite complexes used in these notes; applying the displayed finite-dimensional formula without checking locally finite or direct-sum conventions would mix algebraic objects of different sizes. For this chapter, every join is taken inside the finite simplicial category. The formula computes homology groups, not the full homotopy type. Spaces can have the same reduced homology and different fundamental groups, so the join formula alone cannot prove homotopy equivalence. Its main use in this chapter is more focused: if the first possible nonzero homology groups of $K$ and $L$ occur only in high degrees, the formula predicts that the first possible nonzero homology group of $K*L$ occurs in an even higher degree. This is the vanishing statement isolated in the next theorem. [quotetheorem:6473] [citeproof:6473] The bound is often sharp: if $K$ has its first nonzero reduced homology in degree $r+1$ and $L$ has its first nonzero reduced homology in degree $s+1$, then the [join homology formula](/theorems/6472) gives a possible first nonzero group in degree $r+s+3$. The vanishing assumptions cannot be weakened without changing the conclusion; for example, joining two disconnected nonempty complexes can create a connected complex with nonzero first homology, reflecting the missing $0$-connectedness input. The theorem is homological rather than homotopical, so it does not by itself say that low homotopy groups vanish. Iterating the theorem says that repeated joins rapidly increase homological connectivity. This explains why configuration spaces built from many independent choices often have enough vanishing homology for obstruction theory, while separate arguments may still be needed when the obstruction theorem asks for homotopical connectivity. [example: Join Of Two Spheres] Let $K=\partial\Delta^a$ and $L=\partial\Delta^b$, with $a,b\ge 1$. From the boundary-of-a-simplex computation, the only nonzero reduced homology group of $K$ is \begin{align*} \widetilde{H}_{a-1}(K;k)\cong k, \end{align*} and $\widetilde{H}_i(K;k)=0$ for $i\ne a-1$. Similarly, \begin{align*} \widetilde{H}_{b-1}(L;k)\cong k, \end{align*} and $\widetilde{H}_j(L;k)=0$ for $j\ne b-1$. By *Join Homology Formula*, \begin{align*} \widetilde{H}_m(K*L;k)\cong \bigoplus_{i+j=m-1}\widetilde{H}_i(K;k)\otimes_k \widetilde{H}_j(L;k). \end{align*} A tensor summand can be nonzero only when $i=a-1$ and $j=b-1$. In that case, \begin{align*} m-1=i+j=(a-1)+(b-1)=a+b-2, \end{align*} so \begin{align*} m=a+b-1. \end{align*} Therefore the only possible nonzero reduced homology degree of $K*L$ is $a+b-1$. In that degree, \begin{align*} \widetilde{H}_{a+b-1}(K*L;k)\cong \widetilde{H}_{a-1}(K;k)\otimes_k \widetilde{H}_{b-1}(L;k). \end{align*} Substituting the two one-dimensional groups gives \begin{align*} \widetilde{H}_{a+b-1}(K*L;k)\cong k\otimes_k k\cong k. \end{align*} For every $m\ne a+b-1$, every summand in the join formula contains either $\widetilde{H}_i(K;k)$ with $i\ne a-1$ or $\widetilde{H}_j(L;k)$ with $j\ne b-1$, so every summand is zero and \begin{align*} \widetilde{H}_m(K*L;k)=0. \end{align*} Thus $K*L$ has the reduced homology of $S^{a+b-1}$, matching the standard geometric homeomorphism $S^{a-1}*S^{b-1}\cong S^{a+b-1}$. This does not mean that $\partial\Delta^a*\partial\Delta^b$ is usually the boundary of a simplex. For example, $\partial\Delta^1$ consists of two isolated vertices. If the first copy has vertices $0,1$ and the second has vertices $0',1'$, then $\partial\Delta^1*\partial\Delta^1$ has the four edges \begin{align*} [0,0'],\ [0,1'],\ [1,0'],\ [1,1']. \end{align*} It has no $2$-simplices, because neither factor contains an edge. With the cyclic ordering $0,0',1,1'$, these edges form the $1$-cycle \begin{align*} z=[0,0']+[0',1]+[1,1']+[1',0]. \end{align*} Taking boundaries edge by edge, \begin{align*} \partial_1z=([0']-[0])+([1]-[0'])+([1']-[1])+([0]-[1']). \end{align*} Collecting the vertex terms gives \begin{align*} \partial_1z=-[0]+[0']-[0']+[1]-[1]+[1']-[1']+[0]=0. \end{align*} Hence $\partial\Delta^1*\partial\Delta^1$ is a $4$-cycle, not the boundary of a simplex. [/example] Ordinary joins allow the same original vertex to be used in several factors after relabelling. Many combinatorial problems require choices to be disjoint, so we restrict the join by deleting faces that reuse an original vertex. [definition: Pairwise Deleted Join] Let $K$ be a simplicial complex. The $r$-fold pairwise deleted join of $K$ is the subcomplex \begin{align*} K^{*r}_{\Delta}:=\{\sigma_1\uplus\cdots\uplus\sigma_r\in K*K*\cdots*K : \sigma_i\cap\sigma_j=\varnothing \text{ for } i\ne j\}, \end{align*} where the vertices in different join factors are treated as formally distinct. [/definition] The notation $\uplus$ reminds us that the join factors are labelled even when the original vertex of $K$ is the same. The deleted condition forbids using that original vertex in two different factors. Without this condition, a point of the ordinary join could choose the same combinatorial vertex several times, which is useless in problems where the choices are supposed to be disjoint faces. [example: Deleted Join Of A Simplex] Let $K=\Delta^{n-1}$ on vertex set $[n]$. In the ordinary $r$-fold join, the $j$-th copy of a vertex $x\in[n]$ is formally distinct from its copies in the other join factors, so a face can be written as \begin{align*} \sigma_1\uplus\cdots\uplus\sigma_r \end{align*} with each $\sigma_j\subseteq [n]$. Since $K$ is the full simplex, every subset $\sigma_j\subseteq[n]$ is a face of $K$. The deleted condition requires \begin{align*} \sigma_i\cap\sigma_j=\varnothing \quad \text{whenever } i\ne j. \end{align*} Thus, for each original vertex $x\in[n]$, there is at most one index $j\in[r]$ such that $x\in\sigma_j$. Define a partial function \begin{align*} f_{\sigma}:[n]\dashrightarrow [r] \end{align*} by declaring \begin{align*} f_{\sigma}(x)=j \quad \text{exactly when } x\in\sigma_j. \end{align*} This is well-defined because the sets $\sigma_1,\dots,\sigma_r$ are pairwise disjoint. Conversely, given a partial function $f:[n]\dashrightarrow[r]$, set \begin{align*} \sigma_j=f^{-1}(\{j\})=\{x\in[n]:f(x)=j\}. \end{align*} If $i\ne j$, then no element of $[n]$ can satisfy both $f(x)=i$ and $f(x)=j$, so \begin{align*} \sigma_i\cap\sigma_j=\varnothing. \end{align*} Therefore \begin{align*} \sigma_1\uplus\cdots\uplus\sigma_r \end{align*} is a face of $K^{*r}_{\Delta}$. The two constructions are inverse: starting from $\sigma_1,\dots,\sigma_r$, forming $f_\sigma$, and taking inverse images gives back each $\sigma_j$; starting from $f$, forming the sets $f^{-1}(\{j\})$, and then assigning labels recovers $f$ on its domain. Hence the faces of $K^{*r}_{\Delta}$ are exactly the partial functions $[n]\dashrightarrow[r]$. This partial-function model records $n$ independent choices, each either unused or assigned to one of the $r$ labelled join factors, which is the combinatorial configuration space used in the topological Tverberg setup. [/example] The deleted join is not usually a full join of copies of $K$, so the [join connectivity theorem](/theorems/6473) does not apply directly in that form. For a simplex there is a simpler model: the only condition is that each original vertex is assigned to at most one labelled factor. The example above identifies that model as a partial-function complex; the next theorem turns the identification into the vanishing range used later in obstruction arguments. This is the point where the disjoint-choice construction becomes a homological input rather than only a combinatorial encoding. [quotetheorem:6474] [citeproof:6474] This estimate records the natural vanishing range of the simplex model. The simplex hypothesis matters because every subset of vertices is a face, so the only restriction in the deleted join is disjointness among the $r$ labelled choices. For a general complex $K$, missing faces impose additional constraints, and the partial-function identification no longer describes the whole deleted join. The condition $r\ge 2$ separates the genuinely deleted configuration space from the case $r=1$, where $K^{*1}_{\Delta}=K$ and the statement would reduce to contractibility of the simplex itself. The bound should not be read as a universal deleted-join theorem: if $K$ is disconnected or has sparse facets, its deleted join can have much lower connectivity than the simplex case. Thus the theorem supplies a model estimate, and later applications either reduce to this model or prove an analogue for the specific complex under consideration. [example: Small Deleted Join Of A Simplex] Let $K=\Delta^2$ have vertex set $[3]$ and take $r=2$. By the partial-function description of the deleted join of a simplex, a face of $K^{*2}_{\Delta}$ assigns each $x\in[3]$ either no label or exactly one label in $\{1,2\}$. Thus \begin{align*} K^{*2}_{\Delta}\cong E_2*E_2*E_2, \end{align*} where each copy of $E_2$ is a two-point complex. If the two vertices in the $x$-th copy are written $x_1$ and $x_2$, then a maximal face chooses one vertex from each pair $\{x_1,x_2\}$. Hence the facets are \begin{align*} \{1_{\epsilon_1},2_{\epsilon_2},3_{\epsilon_3}\}\quad\text{with}\quad \epsilon_1,\epsilon_2,\epsilon_3\in\{1,2\}. \end{align*} These are exactly the triangular facets of the boundary of the $3$-dimensional cross-polytope, that is, the octahedron. Now compute the reduced homology using *Join Homology Formula*. For $E_2=\{p,q\}$, there are no edges, so $\operatorname{im}\partial_1=0$. The augmentation kernel is \begin{align*} \ker\varepsilon=\{a[p]+b[q]:a+b=0\}. \end{align*} The equation $a+b=0$ gives $b=-a$, so \begin{align*} \ker\varepsilon=\{a[p]-a[q]:a\in k\}=k\langle [p]-[q]\rangle. \end{align*} Therefore \begin{align*} \widetilde{H}_0(E_2;k)=\ker\varepsilon/\operatorname{im}\partial_1\cong k, \end{align*} and \begin{align*} \widetilde{H}_i(E_2;k)=0\quad\text{for }i\ne 0. \end{align*} Applying *Join Homology Formula* to two copies of $E_2$, a summand \begin{align*} \widetilde{H}_i(E_2;k)\otimes_k\widetilde{H}_j(E_2;k) \end{align*} can be nonzero only when $i=0$ and $j=0$. Since the join formula places this summand in degree $m$ with \begin{align*} i+j=m-1, \end{align*} we get \begin{align*} m-1=0+0=0, \end{align*} so $m=1$. Hence \begin{align*} \widetilde{H}_1(E_2*E_2;k)\cong k\otimes_k k\cong k, \end{align*} while all other reduced homology groups of $E_2*E_2$ vanish. Apply the join formula once more to $(E_2*E_2)*E_2$. The first factor has only one nonzero reduced homology group, in degree $1$, and the second factor has only one nonzero reduced homology group, in degree $0$. Thus a nonzero summand requires \begin{align*} i=1\quad\text{and}\quad j=0. \end{align*} Again $i+j=m-1$, so \begin{align*} m-1=1+0=1, \end{align*} and therefore $m=2$. In that degree, \begin{align*} \widetilde{H}_2(E_2*E_2*E_2;k)\cong \widetilde{H}_1(E_2*E_2;k)\otimes_k\widetilde{H}_0(E_2;k)\cong k\otimes_k k\cong k. \end{align*} For $m\ne 2$, every summand in the join formula contains a zero reduced homology group, so \begin{align*} \widetilde{H}_m(E_2*E_2*E_2;k)=0. \end{align*} Since $K^{*2}_{\Delta}\cong E_2*E_2*E_2$, we have \begin{align*} \widetilde{H}_{-1}(K^{*2}_{\Delta};k)=\widetilde{H}_0(K^{*2}_{\Delta};k)=\widetilde{H}_1(K^{*2}_{\Delta};k)=0, \end{align*} and \begin{align*} \widetilde{H}_2(K^{*2}_{\Delta};k)\cong k. \end{align*} Here $n=3$, so *[Connectivity Estimate For Deleted Joins Of A Simplex](/theorems/6474)* predicts homological $(n-2)=1$-connectedness; the computation shows exactly that vanishing range, with the first surviving reduced homology class appearing in degree $2$. [/example] The same language also describes obstructions without yet proving a full obstruction theorem. A highly connected complex has no low-dimensional homological obstruction to extending maps into it; a nonzero top homology class can become the obstruction that prevents an equivariant map from existing. [explanation: Obstruction Language In This Course] Beginning in Chapter 3 and continuing through Chapters 5, 6, and 8, an equivariant combinatorial problem will be translated into the existence of a $G$-equivariant map $X\to Y$. The space $X$ is often a deleted join or deleted product encoding disjoint choices, while $Y$ is usually a sphere or representation sphere encoding a forbidden coincidence. Connectivity estimates for $X$ and homology computations for $Y$ determine the first degree in which an obstruction can live. The word obstruction should be read concretely here: it is a cohomology class whose nonvanishing prevents an extension or equivariant map. This chapter supplies the input data for those classes, namely vanishing ranges, Euler characteristic checks, and exact sequences that identify the relevant homology groups. [/explanation] The pattern for the rest of the course is now visible. Convert a combinatorial configuration into a simplicial complex, estimate the connectivity of that complex by joins, covers, and exact sequences, and then use an obstruction theorem to force the desired combinatorial conclusion. After the algebraic invariants have been introduced, the course is ready for the central symmetry principle behind many obstructions. The Borsuk-Ulam theorem is the prototype result explaining why equivariant maps from highly symmetric spaces to lower-dimensional targets cannot exist. # 3. The Borsuk–Ulam Theorem Chapter 2 built the obstruction language, especially reduced homology, connectivity, joins, and deleted joins, needed to turn combinatorial questions into topological non-existence statements. This chapter introduces the Borsuk-Ulam theorem, the prototype result behind that method: symmetry on a sphere forces coincidence. The prerequisites are basic point-set topology, the homology and cohomology of spheres and real projective spaces with $\mathbb F_2$ coefficients, and the notion of degree modulo $2$ for maps between closed manifolds. We focus on antipodal symmetry, its formulations in terms of odd and equivariant maps, and two proof mechanisms that recur throughout the course: degree modulo $2$ and cohomological index. ## Antipodal Symmetry and Equivariance What does it mean for a topological problem to respect the symmetry $x \mapsto -x$ on a sphere? The Borsuk-Ulam method begins by encoding that symmetry as a group action and then asking whether a map can preserve it. In combinatorics this is the language that turns signed labelings, deleted products, and coloring obstructions into topological statements. The basic geometric object is the sphere with its antipodal involution. [definition: Antipodal Sphere] For $n \ge 0$, the antipodal $n$-sphere is $S^n \subset \mathbb R^{n+1}$ equipped with the map $a:S^n \to S^n$ defined by $a(x)=-x$. [/definition] The map $a$ has no fixed points, and its orbits are unordered pairs $\{x,-x\}$. The quotient by these orbits is real projective space $\mathbb RP^n$, so an antipodal problem on $S^n$ often has an equivalent projective-space formulation. [example: Antipodal Pairs on the Circle] Write $S^1=\{e^{i\theta}:\theta\in\mathbb R\}$. The antipodal point to $e^{i\theta}$ is computed from $-1=e^{i\pi}$: \begin{align*} -e^{i\theta}=e^{i\pi}e^{i\theta}=e^{i(\theta+\pi)}. \end{align*} Thus the orbit of $e^{i\theta}$ is the two-point set $\{e^{i\theta},e^{i(\theta+\pi)}\}$. A concrete model for the quotient by antipodal pairs is the map $q:S^1\to S^1$ defined by $q(e^{i\theta})=e^{2i\theta}$. It sends antipodal points to the same point because \begin{align*} q(-e^{i\theta})=q(e^{i(\theta+\pi)})=e^{2i(\theta+\pi)}=e^{2i\theta+2i\pi}=e^{2i\theta}=q(e^{i\theta}). \end{align*} Conversely, if $q(e^{i\alpha})=q(e^{i\beta})$, then $e^{2i\alpha}=e^{2i\beta}$, so $2\alpha-2\beta$ is an integer multiple of $2\pi$. Hence $\alpha-\beta$ is an integer multiple of $\pi$, and therefore $e^{i\alpha}=e^{i\beta}$ or $e^{i\alpha}=-e^{i\beta}$. Each fiber of $q$ is exactly one antipodal pair, so the orbit space $S^1/\{x\sim -x\}$ is another circle, usually written $\mathbb RP^1$, and the quotient map $S^1\to \mathbb RP^1$ is a two-to-one covering. This is the lowest-dimensional model for the double coverings used later in the cohomological proof. [/example] The circle illustrates the antipodal idea in a space that is already familiar, but later constructions produce deleted products, deleted joins, and other spaces carrying the same two-fold symmetry. To use one language for all of them, we isolate the features of the antipodal map that matter: applying the symmetry twice returns to the starting point, and no point is fixed. [definition: Free Z Over Two Action] A free $\mathbb Z/2$-action on a topological space $X$ is a specified action of the group $\mathbb Z/2=\{0,1\}$ by homeomorphisms on $X$ such that the non-identity element acts by a map $\tau:X \to X$ satisfying $\tau(\tau(x))=x$ and $\tau(x) \ne x$ for all $x \in X$. [/definition] A free action packages the idea of choosing between two opposite alternatives. When $X=S^n$, the standard choice is $\tau(x)=-x$; for deleted products and deleted joins, $\tau$ usually swaps two disjoint pieces of data. The next question is which maps preserve this paired structure, because a map that ignores the pairs cannot carry a symmetry obstruction. [definition: Equivariant Map] Let $(X,\tau)$ and $(Y,\sigma)$ be topological spaces with $\mathbb Z/2$-actions. A continuous map $f:X \to Y$ is equivariant if $f(\tau(x))=\sigma(f(x))$ for all $x \in X$. [/definition] Equivariant maps are the morphisms in the category of spaces with a chosen two-fold symmetry. For antipodal spheres, the equivariance equation becomes the concrete identity $f(-x)=-f(x)$. We introduce a separate definition for this special case because the Borsuk-Ulam theorem is usually applied by constructing maps satisfying exactly that identity. [definition: Odd Map] A continuous map $f:S^m \to S^n$ is odd if $f(-x)=-f(x)$ for every $x \in S^m$. [/definition] Thus an odd map $S^m \to S^n$ is the same thing as a $\mathbb Z/2$-equivariant map between antipodal spheres. The question at the heart of the chapter is whether such a symmetry-respecting map can lower dimension. [example: Odd Maps from the Circle to Itself] Let $k$ be an odd integer, so $k=2r+1$ for some $r\in\mathbb Z$, and define $f:S^1\to S^1$ by $f(e^{i\theta})=e^{ik\theta}$. Since $-1=e^{i\pi}$, the antipodal point to $e^{i\theta}$ is \begin{align*} -e^{i\theta}=e^{i\pi}e^{i\theta}=e^{i(\theta+\pi)}. \end{align*} Therefore \begin{align*} f(-e^{i\theta})=f(e^{i(\theta+\pi)})=e^{ik(\theta+\pi)}=e^{ik\theta}e^{ik\pi}. \end{align*} Using $k=2r+1$, we get \begin{align*} e^{ik\pi}=e^{i(2r+1)\pi}=e^{i2r\pi}e^{i\pi}=1\cdot(-1)=-1. \end{align*} Substituting this into the previous identity gives \begin{align*} f(-e^{i\theta})=e^{ik\theta}(-1)=-e^{ik\theta}=-f(e^{i\theta}). \end{align*} Thus $f$ is odd. The lift of $f$ along the covering map $\mathbb R\to S^1$, $\theta\mapsto e^{i\theta}$, is $F:\mathbb R\to\mathbb R$ with $F(\theta)=k\theta$, because $e^{iF(\theta)}=e^{ik\theta}=f(e^{i\theta})$. Over one full turn in the domain, \begin{align*} F(\theta+2\pi)-F(\theta)=k(\theta+2\pi)-k\theta=2\pi k. \end{align*} Hence the image winds around $S^1$ exactly $k$ times, so the ordinary degree of $f$ is $k$. Since $k=2r+1$, its mod-$2$ degree is \begin{align*} \deg_2(f)=k \pmod 2=1. \end{align*} This family shows explicitly that, for power maps on the circle, the oddness identity $f(-z)=-f(z)$ occurs exactly in the odd-degree cases. [/example] The degree parity in the example is not accidental. It is the first visible trace of the obstruction that forbids odd maps from $S^n$ to $S^{n-1}$. ## Equivalent Forms of Borsuk-Ulam How can a theorem about antipodal points become a statement about maps into Euclidean space or covers by closed sets? The answer is that the same obstruction can be seen before or after normalising a nonzero vector-valued function. This flexibility is why Borsuk-Ulam appears in graph coloring, convexity, and discrete geometry under many different names. [quotetheorem:6462] [citeproof:6462] This statement says that any continuous measurement of $n$ real quantities on the $n$-sphere must take the same value at some antipodal pair. Continuity is essential: a discontinuous rule can choose one representative from each antipodal pair and assign different values to the two representatives, so no topological obstruction remains. The target dimension is also sharp, since the inclusion $S^n \subset \mathbb R^{n+1}$ satisfies $x \ne -x$ for every $x \in S^n$. Thus Borsuk-Ulam is not a statement that antipodal pairs are always indistinguishable; it says that $n$ continuous real coordinates are insufficient to distinguish all antipodal pairs on $S^n$. To complete the proof and to obtain the version used in applications, we need the underlying obstruction: an equivariant map cannot reduce the dimension of an antipodal sphere by one. [quotetheorem:6475] [citeproof:6475] The no-map theorem is often the cleanest version for applications: construct an odd map from a hypothetical combinatorial object, then rule it out. Each hypothesis is doing work. If antipodality is dropped, the constant map $S^n \to S^{n-1}$ exists; if continuity is dropped, arbitrary choices can separate antipodal pairs without respecting topology; and if the target is not lower-dimensional, the identity map $S^n \to S^n$ is odd. The theorem also does not forbid maps $S^n \to S^{n-1}$ in general, only those compatible with the antipodal symmetry. Since different applications naturally produce either Euclidean maps or sphere-valued maps, we record the exact equivalence between the coincidence and no-map forms. [quotetheorem:6476] [citeproof:6476] The equivalence lets us choose whichever formulation matches the data in an application. The normalisation step explains why the non-vanishing condition is decisive: without $f(x)-f(-x) \ne 0$ everywhere, there is no sphere-valued map to construct, and the desired antipodal coincidence has already occurred. The ambient dimension is again sharp, because an odd map to $S^n$ exists but an odd map to $S^{n-1}$ does not. These forms are logically interchangeable only under the stated continuity and antipodal hypotheses; they should not be read as forbidding arbitrary non-equivariant maps. If equivariance is dropped, the constant map $S^n \to S^{n-1}$ exists. If continuity is dropped, choose one representative from each antipodal pair and send it to a fixed point $p \in S^{n-1}$ while sending its antipode to $-p$; this gives a set-theoretic odd map with no topological content. Covers by sets require a separate translation: instead of a numerical function, the input is information about which region contains each point, and the obstruction appears when every region tries to avoid antipodal pairs. [quotetheorem:6477] [citeproof:6477] The covering theorem is the bridge to many combinatorial applications: a coloring or labeling creates a cover, and the theorem forces a symmetric conflict. The closedness assumption ensures that partition-of-unity or distance-function constructions behave continuously; without a closedness or openness hypothesis, pathological covers need not yield continuous coordinate functions. The theorem is an at-most-$(n+1)$ statement: if fewer closed sets cover $S^n$, padding the cover by empty sets reduces it to the displayed form. The bound is sharp in the upward direction, because $S^1$ can be covered by three short closed arcs arranged around the circle, each of length less than $\pi$, so no one arc contains an antipodal pair. Thus the theorem does not extend to arbitrary larger covers or to non-continuous labeling data. [example: Three Closed Sets on the Two-Sphere] Suppose $S^2=F_0\cup F_1\cup F_2$ with each $F_i$ closed. Applying *[Lyusternik-Schnirelmann Covering Theorem](/theorems/6477)* with $n=2$ gives an index $i\in\{0,1,2\}$ and a point $x\in S^2$ such that \begin{align*} x\in F_i \quad\text{and}\quad -x\in F_i. \end{align*} Thus one of the three closed sets contains an antipodal pair. For a concrete instance, let $c:S^2\to \mathbb R^3$ be a continuous rule, with coordinates $c(x)=(c_0(x),c_1(x),c_2(x))$, and define \begin{align*} F_i=\{x\in S^2: c_i(x)\ge c_0(x),\ c_i(x)\ge c_1(x),\ c_i(x)\ge c_2(x)\}. \end{align*} Each $F_i$ is closed because \begin{align*} F_i = (c_i-c_0)^{-1}([0,\infty)) \cap (c_i-c_1)^{-1}([0,\infty)) \cap (c_i-c_2)^{-1}([0,\infty)), \end{align*} and the functions $c_i-c_j$ are continuous. The three sets cover $S^2$ because, for every $x$, the three [real numbers](/page/Real%20Numbers) $c_0(x),c_1(x),c_2(x)$ have at least one maximum. Therefore some $F_i$ contains $x$ and $-x$, which means \begin{align*} c_i(x)\ge c_j(x) \quad\text{and}\quad c_i(-x)\ge c_j(-x) \qquad\text{for every }j\in\{0,1,2\}. \end{align*} So the same alternative $i$ is among the largest choices at both antipodal inputs. [/example] ## Degree Modulo Two Why should antipodal symmetry know anything about dimension? Degree is the first invariant that detects the obstruction. Since signs are inconvenient for arbitrary maps and orientations, the course uses degree modulo $2$, which counts preimages of a regular value by parity. [definition: Degree Modulo Two] Let $M$ and $N$ be smooth compact connected $n$-manifolds without boundary, and let $f:M \to N$ be continuous. If $y \in N$ is a regular value for a smooth approximation of $f$, the degree modulo $2$ of $f$ is \begin{align*} \deg_2(f) = |f^{-1}(y)| \pmod 2. \end{align*} [/definition] The definition is independent of the regular value and of the smooth approximation. In homological language, it is the scalar by which $f_*$ acts on $H_n(-;\mathbb F_2)\cong \mathbb F_2$. For antipodal maps, this scalar is forced to be nonzero, which is the degree-theoretic source of Borsuk-Ulam. [quotetheorem:6478] [citeproof:6478] This result is the parity engine behind Borsuk-Ulam. Oddness is essential: on $S^1$, the map $z \mapsto z^2$ has even degree and satisfies $f(-z)=f(z)$ rather than $f(-z)=-f(z)$. The equal-dimension hypothesis is also part of the statement, since degree is a top-dimensional invariant for maps between manifolds of the same dimension. The theorem does not say that every odd map has degree $1$ over $\mathbb Z$; the map $z \mapsto z^3$ on $S^1$ is odd and has ordinary degree $3$, but has mod-$2$ degree $1$. It also does not assign a degree to maps between spaces of different dimensions. If an odd map lowered dimension and then returned by inclusion, it would create an odd self-map of the sphere whose top homology action factors through a group that is zero in that degree. [example: Degree Parity on the Circle] Let $k\in\mathbb Z$ and define $f:S^1\to S^1$ by $f(e^{i\theta})=e^{ik\theta}$. The lift of $f$ to the covering map $\mathbb R\to S^1$, $\theta\mapsto e^{i\theta}$, is $F(\theta)=k\theta$, because \begin{align*} e^{iF(\theta)}=e^{ik\theta}=f(e^{i\theta}). \end{align*} Over one full turn in the domain, the lift changes by \begin{align*} F(\theta+2\pi)-F(\theta)=k(\theta+2\pi)-k\theta=k\theta+2\pi k-k\theta=2\pi k. \end{align*} Thus the image winds around $S^1$ exactly $k$ times, so the ordinary degree of $f$ is $k$. Now compute the antipodal condition. Since $-1=e^{i\pi}$, \begin{align*} -e^{i\theta}=e^{i\pi}e^{i\theta}=e^{i(\theta+\pi)}. \end{align*} Therefore \begin{align*} f(-e^{i\theta})=f(e^{i(\theta+\pi)})=e^{ik(\theta+\pi)}=e^{ik\theta}e^{ik\pi}. \end{align*} If $k=2r+1$ is odd, then \begin{align*} e^{ik\pi}=e^{i(2r+1)\pi}=e^{i2r\pi}e^{i\pi}=1\cdot(-1)=-1. \end{align*} Substituting gives \begin{align*} f(-e^{i\theta})=e^{ik\theta}(-1)=-e^{ik\theta}=-f(e^{i\theta}). \end{align*} So $f$ is odd when $k$ is odd, and its mod-$2$ degree is \begin{align*} \deg_2(f)=k \pmod 2=1. \end{align*} If $k=2r$ is even, then \begin{align*} e^{ik\pi}=e^{i2r\pi}=1, \end{align*} and hence \begin{align*} f(-e^{i\theta})=e^{ik\theta}=f(e^{i\theta}). \end{align*} Thus the even-degree maps identify antipodal inputs, while the odd-degree maps preserve antipodality and have nonzero mod-$2$ degree. [/example] The circle case captures the full pattern: antipodal symmetry forces an odd number of sheets over a generic point. Higher-dimensional proofs replace [winding number](/page/Winding%20Number) by top homology or projective cohomology. [remark: Why Mod Two Is Natural] Degree over $\mathbb Z$ requires orientations and signs of Jacobians. Modulo $2$, each transverse preimage contributes $1$, so cancellation by opposite signs disappears. This is well suited to combinatorial applications, where parity is often more robust than orientation. [/remark] ## Cohomological Index Degree proves the sphere-to-sphere obstruction, but later chapters need a version for arbitrary free $\mathbb Z/2$-spaces built from complexes. The cohomological index measures how much antipodal sphere-like content a free $\mathbb Z/2$-space carries. It is monotone under equivariant maps, which turns topology into a [comparison principle](/theorems/4870). [definition: Cohomological Index] Let $(X,\tau)$ be a free $\mathbb Z/2$-space, and let $X/(\mathbb Z/2)$ be its orbit space. The cohomological index $\operatorname{ind}(X)$ is the supremum of the integers $k \ge 0$ such that $w^k \ne 0$ in $H^k(X/(\mathbb Z/2);\mathbb F_2)$, where $w \in H^1(X/(\mathbb Z/2);\mathbb F_2)$ is the first Stiefel-Whitney class of the associated double cover $X \to X/(\mathbb Z/2)$. If nonzero powers occur in arbitrarily large degree, set $\operatorname{ind}(X)=\infty$. [/definition] For the antipodal sphere, the orbit space is $\mathbb RP^n$, whose mod-$2$ [cohomology ring](/theorems/2271) has a generator in degree $1$ surviving through degree $n$. Hence $\operatorname{ind}(S^n)=n$. We now need the comparison theorem that makes this number an obstruction: if a symmetry-preserving map exists, the index of the domain must fit inside the index of the target. [quotetheorem:6479] [citeproof:6479] This theorem is the abstract obstruction template used later for Kneser graphs and deleted joins. Equivariance is the crucial hypothesis: an ordinary constant map $X \to Y$ may exist even when $\operatorname{ind}(X)>\operatorname{ind}(Y)$, but it carries no information about the two-fold symmetry. For example, there is a constant map $S^2 \to S^0$, although monotonicity forbids any antipodal equivariant map because $2>0$. Freeness is also part of the setup because the index is defined from the associated double cover of the orbit space; if $\mathbb Z/2$ acts on a one-point space by fixing the point, the quotient map is not a two-to-one cover and the Stiefel-Whitney class used in the definition is not available. Monotonicity is only a comparison principle, so it rules out maps after the indices are known but does not by itself compute the index of a complicated deleted complex. A proposed coloring often gives an equivariant map into a sphere of low dimension; index monotonicity then rules it out. [example: Index Obstruction for Spheres] For the antipodal action on $S^n$, the orbit space is $\mathbb RP^n$. Its mod-$2$ cohomology ring is \begin{align*} H^*(\mathbb RP^n;\mathbb F_2)\cong \mathbb F_2[t]/(t^{n+1}), \end{align*} where $t$ has degree $1$. Thus \begin{align*} t^0,t^1,\dots,t^n \ne 0 \quad\text{and}\quad t^{n+1}=0, \end{align*} so the largest exponent with nonzero power is $n$, and therefore $\operatorname{ind}(S^n)=n$. Replacing $n$ by $n-1$ gives \begin{align*} H^*(\mathbb RP^{n-1};\mathbb F_2)\cong \mathbb F_2[t]/(t^n), \end{align*} so \begin{align*} t^0,t^1,\dots,t^{n-1}\ne 0 \quad\text{and}\quad t^n=0, \end{align*} and hence $\operatorname{ind}(S^{n-1})=n-1$. Now suppose there were an equivariant map $S^n\to S^{n-1}$. By *[Monotonicity of Cohomological Index](/theorems/6479)*, \begin{align*} \operatorname{ind}(S^n)\le \operatorname{ind}(S^{n-1}). \end{align*} Substituting the two computed indices gives \begin{align*} n\le n-1, \end{align*} which is impossible for $n\ge 1$ because subtracting $n$ from both sides gives $0\le -1$. Therefore no equivariant map $S^n\to S^{n-1}$ exists. This recovers the no-map form of Borsuk-Ulam from index comparison alone, and the same argument applies whenever a more complicated free $\mathbb Z/2$-space has an index lower bound computed by homology. [/example] The index viewpoint changes the Borsuk-Ulam theorem from a theorem about spheres into a reusable principle. The cost is that one must compute or bound the index of the combinatorial space under study. ## Tucker's Lemma as a Combinatorial Shadow How does the continuous theorem appear in a finite combinatorial setting? [Tucker's lemma](/theorems/6480) replaces maps from spheres by antipodal labelings of triangulated balls or spheres. It is the discrete statement that later feeds algorithms, labeling arguments, and proofs of Kneser-type results. [definition: Antipodal Labeling] Let $K$ be a triangulation of $S^n$ that is invariant under the antipodal map. An antipodal labeling is a function $\lambda:V(K) \to \{\pm 1,\dots,\pm m\}$ on the vertex set such that $\lambda(-v)=-\lambda(v)$ for every vertex $v \in V(K)$. [/definition] A complementary edge is an edge whose endpoints receive opposite labels of the same absolute value. If no such edge exists, the labeling can be converted into a simplicial map to the boundary of a cross-polytope. The next theorem states that this attempted conversion must fail when the target has dimension too small. The obstruction is localised in one edge. If every edge avoids opposite labels of the same size, the labels define a symmetry-preserving map into the boundary of the $n$-dimensional cross-polytope, which is $S^{n-1}$; Borsuk-Ulam says that such a map cannot exist. [quotetheorem:6480] [citeproof:6480] Tucker's lemma is stated here as the combinatorial analogue of Borsuk-Ulam; its proof is developed in Chapter 4, in the discussion of Tucker's lemma, Ky Fan's lemma, and simplicial approximation. The main point for this chapter is the dictionary: an antipodal labeling without complementary edges would produce a simplicial equivariant map into a sphere of one lower dimension. The hypotheses are the discrete counterparts of the topological hypotheses above, and each has a concrete failure mode. Antipodal symmetry of the triangulation is needed so that the vertex involution extends over simplices; without it, take an arbitrary triangulation with no antipodal mate for some edge and label vertices locally without any forced opposite edge. The condition $\lambda(-v)=-\lambda(v)$ is what makes the resulting simplicial map equivariant; if it is dropped, a constant labeling by $+1$ has no complementary edge. The bound by labels $\{\pm 1,\dots,\pm n\}$ makes the target the boundary of an $n$-dimensional cross-polytope, namely $S^{n-1}$; if labels up to $\pm(n+1)$ are allowed, the map $\lambda(v)=i$ on vertices near the $i$th coordinate direction models the identity-type antipodal map into $S^n$, so Borsuk-Ulam gives no contradiction. The theorem is therefore a lower-dimensional obstruction, not a general statement that every symmetric labeling must contain a complementary edge regardless of the label range. [example: Antipodal Labeling of a Triangulated Circle] Triangulate $S^1$ as an even cycle with vertices \begin{align*} v_0,v_1,\dots,v_{2m-1},v_0 \end{align*} where indices are read modulo $2m$, and suppose the antipodal vertex to $v_j$ is $v_{j+m}$. Let $\lambda(v_j)\in\{+1,-1\}$ and assume $\lambda(v_{j+m})=-\lambda(v_j)$ for every $j$. We show that some edge has endpoints labeled $+1$ and $-1$. Write $a_j=\lambda(v_j)$. Along the half-cycle from $v_0$ to $v_m$, let $t$ be the number of indices $j\in\{0,\dots,m-1\}$ for which $a_{j+1}=-a_j$. If the label changes across the edge $v_jv_{j+1}$, then $a_{j+1}a_j=-1$; if the label does not change, then $a_{j+1}a_j=1$. Therefore \begin{align*} \prod_{j=0}^{m-1} a_{j+1}a_j=(-1)^t. \end{align*} The same product also telescopes: \begin{align*} \prod_{j=0}^{m-1} a_{j+1}a_j=(a_1a_0)(a_2a_1)\cdots(a_ma_{m-1}). \end{align*} Reordering the factors gives \begin{align*} (a_1a_0)(a_2a_1)\cdots(a_ma_{m-1})=a_0a_m(a_1^2)(a_2^2)\cdots(a_{m-1}^2). \end{align*} Since each $a_j$ is either $1$ or $-1$, we have $a_j^2=1$ for every $j$, so \begin{align*} a_0a_m(a_1^2)(a_2^2)\cdots(a_{m-1}^2)=a_0a_m. \end{align*} Because $v_m=-v_0$, antipodality of the labeling gives $a_m=-a_0$. Hence \begin{align*} a_0a_m=a_0(-a_0)=-a_0^2=-1. \end{align*} Combining the two computations of the product gives \begin{align*} (-1)^t=-1. \end{align*} Thus $t$ is odd, so $t\ge 1$. At least one edge on the half-cycle has opposite labels, and since the only labels are $+1$ and $-1$, that edge is complementary. This is exactly the $n=1$ case of Tucker's lemma. [/example] The circle example is the finite parity version of the degree computation for odd maps $S^1 \to S^1$. Both say that antipodal symmetry forces an odd transition count. [explanation: From Labels to Maps] Given an antipodal labeling with no complementary edge, assign to each positive label $i$ the vertex $e_i$ of a cross-polytope and to each negative label $-i$ the vertex $-e_i$. Extending linearly over simplices gives a simplicial map into the boundary of the cross-polytope, which is homeomorphic to $S^{m-1}$. Antipodality of the labeling makes the map equivariant. When $m=n$, this would give an equivariant map $S^n \to S^{n-1}$, contradicting Borsuk-Ulam. [/explanation] This construction is the basic combinatorial Borsuk-Ulam pipeline. A forbidden coloring becomes a symmetric labeling; the absence of a local conflict becomes a continuous equivariant map; topology rules out the map; therefore the local conflict must exist. The Borsuk-Ulam theorem gives the topological contradiction, but the next step is to express it in finite combinatorial form. Tucker's lemma, Ky Fan's lemma, and [Sperner's lemma](/theorems/6481) do this by turning antipodal symmetry into labeling rules on triangulations. # 4. Combinatorial Borsuk–Ulam: Tucker, Ky Fan, and Sperner This chapter turns the Borsuk-Ulam theorem from Chapter 3 into finite labeling statements that can be checked on triangulations. The prerequisites are the Borsuk-Ulam theorem and its no-retraction form, the basic language of finite simplicial complexes and triangulations, and the parity-counting style of proof used for Sperner's lemma. The central move is to replace a continuous antipodal map by signs placed on vertices, then read a topological contradiction from a forbidden local pattern. We begin with Sperner's lemma as the model for this method, then pass to Tucker's antipodal version and Ky Fan's sharpened alternating-sequence form. ## Labeling a Simplex Without a Fully Colored Face The first question is how a boundary condition on labels can force a completely labelled simplex in the interior. Sperner's lemma is the prototype: it converts a global boundary rule on a triangulated simplex into the existence of one small simplex carrying all possible labels. [definition: Triangulated Simplex] Let $\tau$ be a finite simplicial complex whose geometric realization $|\tau|$ is homeomorphic to the standard $d$-simplex $\triangle^d$. A face of the boundary $\triangle^d$ is identified with the corresponding subcomplex of $\tau$ contained in that face. [/definition] A triangulated simplex gives the finite mesh on which labels can be placed, but the topological information would be lost if boundary vertices were allowed arbitrary colours. The next definition records exactly which labels are allowed on each boundary face, so that the small triangulation remembers the large simplex containing it. [definition: Sperner Labeling] Let $\tau$ be a triangulation of the standard $d$-simplex with vertices of $\triangle^d$ labelled $0,1,\dots,d$. A Sperner labeling is a map $\lambda:V(\tau)\to \{0,1,\dots,d\}$ such that if a vertex $v\in V(\tau)$ lies in the face spanned by $\{i_0,\dots,i_k\}$, then $\lambda(v)\in \{i_0,\dots,i_k\}$. [/definition] The Sperner condition is designed to prevent all fully labelled simplices from being pushed away from the interior. The theorem below is the basic parity statement behind many later labeling arguments: a boundary labelling with the correct restrictions forces a complete local pattern. [quotetheorem:6481] [citeproof:6481] The boundary hypothesis is essential: if a boundary vertex on the edge spanned by $0$ and $1$ were allowed to receive label $2$, then a triangulation could place the missing label entirely on the boundary and avoid any fully labelled small triangle in the interior. The theorem also does not say which simplex is fully labelled or how many such simplices occur; the parity proof only forces an odd count in the relevant sense. Its role in the course is to supply a finite obstruction that survives refinement. The parity proof explains why the conclusion is robust under subdivision, and the smallest nontrivial case is already geometric. A labelled triangle lets us see the boundary restrictions, the interior freedom, and the forced tricoloured face in one picture. [example: Sperner Labeling of a Triangle] Let $\triangle^2$ have corner vertices $a_0,a_1,a_2$ with $\lambda(a_0)=0$, $\lambda(a_1)=1$, and $\lambda(a_2)=2$. Subdivide $\triangle^2$ by adding the barycentre $b$ and the side midpoints $m_{01},m_{12},m_{20}$, where $m_{ij}$ lies on the side spanned by $a_i$ and $a_j$, and join $b$ to each corner and each midpoint in the barycentric subdivision. Define $\lambda(m_{01})=1$, $\lambda(m_{12})=2$, $\lambda(m_{20})=0$, and $\lambda(b)=0$. The boundary condition is satisfied vertex by vertex. On the side $a_0a_1$, the allowed labels are $\{0,1\}$, and $\lambda(m_{01})=1$ lies in this set. On the side $a_1a_2$, the allowed labels are $\{1,2\}$, and $\lambda(m_{12})=2$ lies in this set. On the side $a_2a_0$, the allowed labels are $\{2,0\}$, and $\lambda(m_{20})=0$ lies in this set. The barycentre $b$ is an interior vertex, so the Sperner boundary rule imposes no restriction on $\lambda(b)$. Now consider the small triangle with vertices $a_1,m_{12},b$. Its three labels are $\lambda(a_1)=1$, $\lambda(m_{12})=2$, and $\lambda(b)=0$, so the set of labels on this small triangle is $\{0,1,2\}$. Thus this subdivision contains a fully labelled small triangle, showing concretely how the boundary rule can force a tricoloured face even when the interior label is chosen freely. [/example] Once Sperner's lemma is available, the same finite obstruction can be used to prove a continuous fixed point theorem. The obstruction to a fixed-point-free map is that every point would be displaced in at least one coordinate direction, and a sufficiently fine triangulation can record those displacements as Sperner labels. Compactness then forces a limiting point where the displacement disappears. This is the simplex form of Brouwer's fixed point theorem. [quotetheorem:80] [citeproof:80] The compact convex simplex hypothesis is doing real work. On a non-compact set, a continuous map such as $x\mapsto x+1$ on $\mathbb R$ has no fixed point, and on a space with different topology, such as a circle rotation, fixed points need not exist. The theorem gives existence only; it gives no method for locating the fixed point and no uniqueness. Here it is used mainly to demonstrate how a combinatorial labeling lemma becomes a continuous theorem by refinement and compactness. This proof shows the standard two-stage pattern: first solve a finite labeling problem, then pass to a limit along finer triangulations. It is useful to separate the combinatorial obstruction from the analytic limiting step, because Tucker and Ky Fan will reuse the first part with a different boundary symmetry. [remark: Brouwer as a Labeling Theorem] The argument does not use differentiability, convexity beyond the simplex structure, or metric estimates other than mesh size tending to zero. The topological content enters through Sperner's parity count, while the limiting step translates finite labels back into a continuous fixed point. [/remark] ## Antipodal Labels on a Symmetric Ball The next problem is what replaces Sperner's boundary condition when the underlying topology is not a simplex but a centrally symmetric ball. Borsuk-Ulam predicts an obstruction to antipodal odd behavior, so the correct discrete boundary rule should force a pair of opposite labels on an edge. [definition: Antipodal Triangulation] Let $K$ be a finite triangulation of the $d$-ball $B^d$ such that the boundary sphere $\partial B^d$ is preserved by the antipodal map $x\mapsto -x$. The triangulation is antipodal on the boundary if $v\in V(K)\cap \partial B^d$ implies $-v\in V(K)\cap \partial B^d$, and every boundary simplex $\sigma$ has antipodal simplex $-\sigma$. [/definition] An antipodal triangulation gives a finite model of the symmetry $x\mapsto -x$ only on the boundary, which is where the obstruction lives. To express an odd boundary condition combinatorially, the labels must come in signed pairs and boundary antipodes must receive opposite signs. [definition: Tucker Labeling] Let $K$ be an antipodal triangulation of $B^d$. A Tucker labeling is a map $\lambda:V(K)\to \{\pm 1,\pm 2,\dots,\pm d\}$ such that $\lambda(-v)=-\lambda(v)$ for every boundary vertex $v\in V(K)\cap \partial B^d$. A complementary edge is an edge $uv\in K$ such that $\lambda(u)+\lambda(v)=0$. [/definition] The forbidden pattern is now an edge whose labels cancel. If no such edge existed, the signed labels would define a nonzero piecewise-linear map to $\mathbb R^d$ with antipodal boundary behavior, contradicting the same obstruction that drives Borsuk-Ulam. [quotetheorem:6480] [citeproof:6480] The antipodal boundary condition is essential. If boundary opposite vertices were not required to receive opposite labels, every vertex could be labelled $+1$, producing no complementary edge. The restriction to $d$ signed label pairs is also tied to the dimension: it is what makes the attempted map land in $\mathbb R^d$ and lets the Borsuk-Ulam obstruction apply. The lemma does not identify where the complementary edge lies or how many exist; it only forces at least one local cancellation. The conclusion is local, but the reason is global: the symmetric boundary cannot be filled without producing cancellation somewhere in the triangulated disk or ball. The two-dimensional case is the best place to see how a boundary sign pattern forces an interior crossing. [example: Two-Dimensional Tucker Labeling] Take a centrally symmetric triangulated disk whose boundary is the hexagon with cyclically ordered vertices $v_1,v_2,v_3,-v_1,-v_2,-v_3$. Label these six boundary vertices by $\lambda(v_1)=+1$, $\lambda(v_2)=+2$, $\lambda(v_3)=-1$, $\lambda(-v_1)=-1$, $\lambda(-v_2)=-2$, and $\lambda(-v_3)=+1$. The antipodal boundary rule holds because $\lambda(-v_1)=-1=-\lambda(v_1)$, $\lambda(-v_2)=-2=-\lambda(v_2)$, and $\lambda(-v_3)=+1=-\lambda(v_3)$. Now check the six boundary edges one at a time: \begin{align*} \lambda(v_1)+\lambda(v_2)=1+2=3. \end{align*} \begin{align*} \lambda(v_2)+\lambda(v_3)=2+(-1)=1. \end{align*} \begin{align*} \lambda(v_3)+\lambda(-v_1)=(-1)+(-1)=-2. \end{align*} \begin{align*} \lambda(-v_1)+\lambda(-v_2)=(-1)+(-2)=-3. \end{align*} \begin{align*} \lambda(-v_2)+\lambda(-v_3)=(-2)+1=-1. \end{align*} \begin{align*} \lambda(-v_3)+\lambda(v_1)=1+1=2. \end{align*} None of these sums is $0$, so no boundary edge is complementary. Label every interior vertex by any element of $\{\pm1,\pm2\}$. By *Tucker Lemma*, the full triangulation must contain an edge $xy$ with $\lambda(x)+\lambda(y)=0$. Since the only possible labels are $\pm1$ and $\pm2$, this means either $\{\lambda(x),\lambda(y)\}=\{+1,-1\}$ or $\{\lambda(x),\lambda(y)\}=\{+2,-2\}$. The boundary calculation above shows that this edge cannot be one of the six boundary edges, so the forced complementary edge occurs in the interior part of the triangulation. This is the two-dimensional obstruction in visible form: the antipodal boundary pattern cannot be extended across the disk without producing one local cancellation. [/example] The example suggests that Tucker's lemma is not merely inspired by Borsuk-Ulam; it is a finite version of it. To make that precise, one proves both implications: Borsuk-Ulam forbids a complementary-edge-free labeling, and Tucker on arbitrarily fine triangulations recovers zeros of odd maps. [quotetheorem:6482] [citeproof:6482] The dimension bookkeeping matters: the boundary of the $d$-ball is $S^{d-1}$, and the signed labels $\{\pm1,\dots,\pm d\}$ map to the vertices of the $d$-dimensional crosspolytope in $\mathbb R^d$. The equivalence does not identify Tucker directly with the zero form for maps $S^d\to\mathbb R^d$ without adding a suspension or hemisphere reduction; using the no-retraction form keeps the discrete and continuous dimensions aligned. In later applications, this is the form that complementary-edge arguments actually use. [remark: Why Complementary Edges Matter] A complementary edge is the discrete trace of an attempted zero. If $+i$ and $-i$ occur at adjacent vertices in a fine triangulation, then the $i$th coordinate of the underlying odd map must change sign over a very small region; compactness upgrades these approximate sign changes into an actual zero in the limiting argument. [/remark] ## Alternating Signs and Ky Fan's Strengthening Tucker's lemma guarantees a local contradiction, but it does not count or organize the obstruction. Ky Fan's lemma refines Tucker by looking for a simplex whose labels have increasing absolute values and alternating signs. [definition: Alternating Simplex] Let $K$ be a labelled simplicial complex with labels in $\{\pm1,\dots,\pm m\}$. A simplex with vertex labels $\epsilon_0 i_0,\epsilon_1 i_1,\dots,\epsilon_k i_k$ is alternating if $1\le i_0<i_1<\cdots<i_k\le m$ and $\epsilon_j=-\epsilon_{j+1}$ for every $0\le j<k$ after ordering by increasing absolute value. [/definition] The alternating condition keeps more information than the presence of opposite labels. It records a signed chain in the label poset, and the parity of maximal such chains is the stronger obstruction used in Ky Fan's lemma. [quotetheorem:6483] [citeproof:6483] The no-complementary-edge assumption is what allows the label map to land in $C_m$: an edge labelled $+i,-i$ would already be Tucker's conclusion and would not define a simplex of the crosspolytope boundary. The number of available absolute labels also matters; the alternating $d$-simplex alternative has content only when $m\ge d+1$, because it requires $d+1$ distinct absolute labels. When $m\le d$, the same statement collapses to Tucker's forced complementary edge. The theorem does not count all alternating simplices explicitly here, but it gives the existence statement needed for the refinement. The statement is easiest to parse in dimension two, where an alternating simplex is a triangle whose signs change at every step as the absolute values increase. This example separates the alternating condition from the weaker condition of using several signed labels. [example: Alternating Triangle] Let $d=2$ and use labels in $\{\pm1,\pm2,\pm3\}$. For a triangle labelled $+1,-2,+3$, ordering the labels by increasing absolute value gives \begin{align*} |+1|=1,\qquad |-2|=2,\qquad |+3|=3, \end{align*} so the ordered labels are $+1,-2,+3$. Their signs are \begin{align*} +,\quad -,\quad +, \end{align*} and the adjacent signs are opposite in both places. Hence $+1,-2,+3$ is alternating. Similarly, for a triangle labelled $-1,+2,-3$, the absolute values satisfy \begin{align*} |-1|=1,\qquad |+2|=2,\qquad |-3|=3, \end{align*} so the ordered labels are $-1,+2,-3$. Their signs are \begin{align*} -,\quad +,\quad -, \end{align*} again alternating from one label to the next. By contrast, a triangle labelled $+1,+2,-3$ has ordered labels $+1,+2,-3$, whose first two signs are both positive: \begin{align*} \operatorname{sign}(+1)=+,\qquad \operatorname{sign}(+2)=+. \end{align*} Therefore this triangle is not alternating. Thus, in dimension $2$, *[Ky Fan Lemma](/theorems/6483)* says that an antipodal disk labeling with no complementary edge must contain a small triangle whose ordered signs are either $+,-,+$ or $-,+,-$. [/example] Ky Fan's statement implies Tucker by taking only $m=d$ labels. The reason is that an alternating $d$-simplex would need too many distinct absolute values, so the alternative to a complementary edge cannot occur. [quotetheorem:6484] [citeproof:6484] The hypothesis $m=d$ is exactly the point: Ky Fan's alternative would require $d+1$ distinct absolute labels, but only $d$ are available. If $m>d$, the same argument would not prove Tucker by contradiction, because an alternating $d$-simplex could genuinely exist without a complementary edge. Thus the implication records a sharp specialisation of the stronger lemma rather than an independent proof of Tucker in all signed label ranges. This final implication places the chapter's results in a hierarchy: Sperner is the simplex labeling model, Tucker is the antipodal edge-forcing version, and Ky Fan is the alternating-chain refinement. The shared method is important enough to name explicitly before moving to applications. [explanation: The Labeling Method] The three lemmas in this chapter share the same architecture. A boundary rule is imposed on a triangulated space, a forbidden local pattern is assumed absent, and the labels are converted into a map to a model polytope. The boundary rule gives a topological obstruction, while the absence of the local pattern would make the model map too well behaved. The contradiction forces a simplex or edge with the desired pattern. Sperner uses a simplex and fully labelled faces; Tucker uses a symmetric ball and complementary edges; Ky Fan uses the same symmetry but records alternating chains. Later applications, including graph coloring and discrete geometry, repeatedly use this template with labels built from the combinatorial object under study. [/explanation] The combinatorial Borsuk-Ulam results show how labeling arguments force the existence of certain configurations, and the next chapter applies that pipeline to a concrete and famous graph-coloring problem. Kneser graphs are the first place where the abstract machinery from Chapters 1 through 4 produces a sharp and classical theorem. # 5. Kneser Graphs and Lovász's Theorem This chapter applies the antipodal methods from Chapters 3 and 4, together with the complex-building language from Chapter 1, to a concrete problem in graph coloring. The prerequisites are the Borsuk--Ulam theorem, its open-cover form, and the basic language of graph colorings and simplicial complexes. The main goal is to prove Kneser's conjecture: the graph whose vertices are $k$-subsets of $[n]$ and whose edges record disjointness has chromatic number exactly $n-2k+2$. The chapter gives two complementary routes to the same lower bound, first through Gale configurations and antipodal covers of spheres, and then through Lovasz's neighborhood complex. ## Kneser Graphs, Colorings, and Stable Sets What does it mean to color a graph whose vertices are all $k$-subsets of an $n$-element set, and why should topology know anything about this number? Kneser graphs package a set-system disjointness problem into graph language: a proper coloring partitions the $k$-subsets into families in which no two disjoint members share a color. [definition: Kneser Graph] For integers $n,k \in \mathbb N$ with $n \ge 2k$, the Kneser graph $KG(n,k)$ is the graph with vertex set \begin{align*} \binom{[n]}{k} = \{A \subset \{1,\dots,n\} : |A|=k\}, \end{align*} and with an edge between distinct vertices $A$ and $B$ exactly when $A \cap B = \varnothing$. [/definition] The condition $n \ge 2k$ is the range in which disjoint $k$-sets exist. A coloring of $KG(n,k)$ is therefore a partition of all $k$-subsets into intersecting families, so the next invariant asks for the least possible number of such families. [definition: Chromatic Number] For a graph $G$, the chromatic number $\chi(G)$ is the least integer $m$ for which there exists a map $c:V(G)\to \{1,\dots,m\}$ such that $c(u)\ne c(v)$ whenever $uv$ is an edge of $G$. [/definition] For Kneser graphs, a color class is exactly a family of $k$-subsets with the property that any two members intersect. The most economical-looking way to build such families is to group sets according to a small element they contain, because two sets with the same forced element cannot be disjoint. This gives a visible upper bound before any topology enters the argument, and it is useful because Lovasz's theorem says that this direct construction is optimal. [example: Standard Coloring Of A Kneser Graph] Let $A\in \binom{[n]}{k}$. Define a coloring $c:\binom{[n]}{k}\to \{1,\dots,n-2k+2\}$ as follows: if $\min A\le n-2k+1$, set $c(A)=\min A$; if $\min A\ge n-2k+2$, set $c(A)=n-2k+2$. Thus every $k$-set receives one of the colors $1,\dots,n-2k+2$. We check that no adjacent vertices receive the same color. Suppose $A,B\in \binom{[n]}{k}$ both receive a color $i$ with $i\le n-2k+1$. Then $c(A)=i$ forces $\min A=i$, and $c(B)=i$ forces $\min B=i$. Hence $i\in A$ and $i\in B$, so $i\in A\cap B$. Therefore $A\cap B\ne\varnothing$, and $A$ and $B$ are not adjacent in $KG(n,k)$. It remains to check the final color. If $c(A)=c(B)=n-2k+2$, then $\min A\ge n-2k+2$ and $\min B\ge n-2k+2$, so both $A$ and $B$ are contained in $\{n-2k+2,n-2k+3,\dots,n\}$. This set has \begin{align*} n-(n-2k+2)+1=2k-1 \end{align*} elements. If $A$ and $B$ were disjoint, then \begin{align*} |A\cup B|=|A|+|B|=k+k=2k. \end{align*} But $A\cup B$ is contained in a set of size $2k-1$, so $|A\cup B|\le 2k-1$, contradicting $|A\cup B|=2k$. Thus two $k$-sets with the same final color also cannot be disjoint. In every color class, any two vertices intersect, so no edge of $KG(n,k)$ has both endpoints in the same color class. Therefore the least-element construction gives a proper coloring with $n-2k+2$ colors. [/example] The first genuinely constrained case already has a familiar name, so the construction is not merely formal. This example also sharpens the central problem: the upper bound is visible by inspection, while the matching lower bound requires a method capable of excluding all possible colorings with fewer colors. [example: Petersen Graph] The graph $KG(5,2)$ has vertex set \begin{align*} \binom{[5]}{2}=\{\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}\}, \end{align*} so it has $10$ vertices. Two vertices are adjacent exactly when the corresponding $2$-subsets are disjoint. For instance, $\{1,2\}$ is adjacent exactly to the $2$-subsets of its complement: \begin{align*} [5]\setminus \{1,2\}=\{3,4,5\}. \end{align*} Those adjacent vertices are $\{3,4\}$, $\{3,5\}$, and $\{4,5\}$. The same count holds for every vertex. If $A\in\binom{[5]}{2}$, then $[5]\setminus A$ has $5-2=3$ elements, and a vertex $B\in\binom{[5]}{2}$ is adjacent to $A$ exactly when $B\subset [5]\setminus A$. The number of such $B$ is \begin{align*} \binom{3}{2}=3. \end{align*} Thus every vertex has degree $3$, so $KG(5,2)$ is a $3$-regular graph on $10$ vertices. This is the usual Petersen graph. For this graph, the Lovasz formula gives \begin{align*} \chi(KG(5,2))=5-2\cdot 2+2=5-4+2=3. \end{align*} Thus the Petersen graph is the first nontrivial Kneser graph where the least-element coloring uses exactly the predicted three colors. [/example] The Petersen graph indicates the right answer in a small case, but Kneser's conjecture asks for all $n$ and $k$. The upper bound comes from an explicit coloring, so the real obstruction is lower-bound: one must rule out every possible coloring with fewer colors, not just the obvious ones. The theorem gives exactly this global obstruction and shows that no hidden combinatorial trick can improve on the least-element coloring. [quotetheorem:6485] [citeproof:6485] The hypothesis $n\ge 2k$ is exactly the range in which the graph has edges, because two disjoint $k$-subsets of $[n]$ can exist only then. If $n<2k$, then $KG(n,k)$ has vertices but no edges, so its chromatic number is $1$ whenever vertices exist; the formula $n-2k+2$ would not describe the coloring problem. At the boundary $n=2k$, every $k$-set is adjacent only to its complement, so the graph is a matching and the theorem gives $\chi(KG(2k,k))=2$. The theorem determines the number of colors, not the structure or uniqueness of optimal colorings; different optimal colorings can behave quite differently from the least-element coloring. The proof reduces the chromatic lower bound to finding the right geometric encoding of $[n]$. Before building that encoding, it is useful to know that the full Kneser graph contains a smaller cyclic core; this motivates isolating $k$-sets whose elements are evenly separated around a cycle. [definition: Stable Subset] A subset $A\subset [n]$ is stable if it contains no two cyclically consecutive elements, where $1$ and $n$ are also regarded as consecutive. [/definition] Stability is a cyclic spacing condition. It says that the chosen elements of $[n]$ are separated around an $n$-cycle, which raises the natural question of what happens when the Kneser graph is restricted to these spaced-out vertices. [definition: Schrijver Graph] For $n\ge 2k$, the Schrijver graph $SG(n,k)$ is the induced subgraph of $KG(n,k)$ whose vertices are the stable $k$-subsets of $[n]$. [/definition] The Schrijver graph keeps only the cyclically spread-out vertices. The theorem stated next is stronger than Lovasz's theorem because $SG(n,k)$ is a subgraph of $KG(n,k)$, yet it still demands the same number of colors. [remark: Schrijver Theorem External Input] For integers $n,k\in\mathbb N$ with $n\ge 2k$, \begin{align*} \chi(SG(n,k)) = n-2k+2. \end{align*} Moreover, $SG(n,k)$ is vertex-critical: deleting any vertex lowers the chromatic number. [/remark] The same restriction $n\ge 2k$ is again necessary for a disjointness graph with edges: if $n<2k$, then no two $k$-subsets of $[n]$ are disjoint, so the induced stable graph is edgeless and has chromatic number $1$ whenever it has a vertex. The boundary case $n=2k$ gives the alternating stable sets as complementary vertices, so the formula gives the matching value $2$ rather than a higher obstruction. The stability condition is also doing real work: if one keeps only the vertices of $KG(5,2)$ that contain the label $1$, the resulting induced subgraph is an independent set and has chromatic number $1$, so an arbitrary induced subgraph selected by a simple set-theoretic rule need not preserve the Lovasz chromatic number. Schrijver's cyclic spacing is the special restriction for which the topological obstruction survives. Vertex-criticality is a sharper statement than preserving the chromatic number on a subgraph: for every stable vertex $A$, the graph $SG(n,k)-A$ can be colored with one fewer color than $SG(n,k)$. This should not be read as a uniqueness statement. Even in the first nonmatching case $SG(5,2)$, which is the $5$-cycle, deleting any one vertex gives a path and lowers the chromatic number from $3$ to $2$, but the ambient graph $KG(5,2)$ has other $5$-cycles with the same critical behavior. The refinement rests on the stable Kneser graph, also called the Schrijver graph, and on a sharpened topological-combinatorial obstruction formulated through Tucker-type lemmas or equivalent index arguments for antipodal complexes. Thus the theorem locates a critical core inside the Kneser graph while keeping the same Lovasz lower bound. ## Gale's Lemma and Equivariant Covers How can a coloring of a finite graph produce a cover of a sphere? The bridge is a configuration of $n$ points on a sphere with the property that every open hemisphere contains enough of the points to encode a vertex of the Kneser graph. [quotetheorem:6487] [citeproof:6487] The dimension $S^{n-2k}$ is tuned to the desired chromatic lower bound: the antipodal cover theorem on $S^d$ obstructs covers by $d+1$ antipodal-free open sets, so $d=n-2k$ gives the forbidden number $n-2k+1$ of colors. The numerical hypothesis $n\ge 2k$ has a separate role: it is the range in which the sphere dimension is nonnegative and the Kneser graph has disjoint $k$-sets to detect. If $n<2k$, the requested sphere dimension would be negative, and the intended conclusion would demand that every open hemisphere contain more labels than can be forced by any antipodal-cover argument. The Gale construction is an additional geometric hypothesis, not a consequence of the inequality alone. The lemma does not say that every hemisphere contains exactly $k$ points, nor does it identify a unique configuration; it guarantees only the minimum occupancy needed for the coloring argument. If the points are placed without the Gale general-position property, the conclusion can fail even when the numerical range is correct: for $n=5$ and $k=2$, placing all five points in a small arc of $S^1$ leaves an opposite open semicircle containing no points. At the boundary $n=2k$, the sphere is $S^0=\{-1,1\}$, and the assertion reduces to placing the points so that each of the two open hemispheres contains at least $k$ labels, matching the complement-pair structure of $KG(2k,k)$. [Gale's lemma](/theorems/6487) turns every direction $x\in S^{n-2k}$ into a nonempty collection of $k$-subsets: take those contained among the points in the open hemisphere centered at $x$. The remaining problem is to convert this direction-by-direction information into an open cover whose sets remember the colors. A coloring assigns a label to each eligible $k$-subset, so each direction should be recorded by at least one color appearing inside its positive hemisphere. This construction has two constraints that must be built into the notation. First, the object attached to a color is not a single $k$-set but an open subset of the sphere of directions. Second, the assignment must remember the domain of the coloring and the target set of colors, because antipodal disjointness will compare the color data at $x$ and at $-x$. For each direction, the Gale property supplies at least one $k$-set in the positive hemisphere, and the coloring turns that $k$-set into a color. To apply the antipodal cover theorem, we must reverse this viewpoint: fix a color first, then collect all directions in which that color is witnessed by some hemispherical $k$-set. The strict inequality in the hemispherical condition is essential because it makes these direction sets open. [definition: Hemispherical Color Sets] Fix a Gale configuration $p_1,\dots,p_n\in S^d$ for $d=n-2k$. Given a proper coloring $c:V(KG(n,k))\to \{1,\dots,m\}$, define \begin{align*} U_i\subset S^d,\qquad U_i=\{x\in S^d : \text{there exists } A\in \binom{[n]}{k} \text{ with } c(A)=i \text{ and } p_a\cdot x>0 \text{ for all } a\in A\} \end{align*} for $i=1,\dots,m$. [/definition] These sets are open because each condition $p_a\cdot x>0$ is open. Gale's lemma says that the union of the $U_i$ is the whole sphere, since every open hemisphere contains some $k$-subset and that subset has a color. [remark: Antipodal Disjointness] If $x\in U_i$ and $-x\in U_i$, then there are $k$-sets $A$ and $B$ of color $i$ with $p_a\cdot x>0$ for $a\in A$ and $p_b\cdot x<0$ for $b\in B$. These inequalities force $A\cap B=\varnothing$. Hence a proper coloring prevents $U_i$ from containing an antipodal pair. [/remark] The color sets now form a cover of the sphere, and properness of the coloring prevents any one color set from containing an antipodal pair. This creates the topological obstruction needed for the lower bound: a sphere cannot be covered by too few open sets if each set avoids antipodal pairs. The following theorem is the Borsuk--Ulam form that turns this covering obstruction into a contradiction for an attempted coloring with too few colors. [quotetheorem:6488] [citeproof:6488] The number $d+1$ is sharp in the sense relevant here. Let $v_1,\dots,v_{d+2}$ be the vertices of a regular simplex centred at $0$ in $\mathbb R^{d+1}$, and set $U_i=\{x\in S^d:x\cdot v_i>0\}$. These $d+2$ open sets cover $S^d$, and no $U_i$ contains an antipodal pair, so the conclusion cannot be strengthened to $d+2$ sets. The sphere hypothesis is essential as well: an interval can be covered by one [open set](/page/Open%20Set) without containing any antipodal pair because there is no antipodal structure to test. Regularity of the cover also matters for this proof form. If arbitrary sets are allowed on $S^1$, the two half-open semicircles $\{e^{it}:0\le t<\pi\}$ and $\{e^{it}:\pi\le t<2\pi\}$ cover the circle and neither contains an antipodal pair, so one must use the open-cover theorem here or invoke a separate closed-set version with its own proof. In the Kneser argument, the sets are open precisely because membership is defined by strict inequalities $p_a\cdot x>0$. This openness lets the antipodal obstruction pass directly from Borsuk--Ulam to the color classes, and it is the final step before translating the topological contradiction back into two disjoint same-colored $k$-sets. Combining the previous ingredients gives the lower bound in Lovasz's theorem. If \begin{align*} m\le d+1=n-2k+1, \end{align*} then $m$ color sets cover $S^d$ while each avoids antipodal pairs, contradicting the antipodal cover theorem. [example: Lower Bound For KG(6,2)] For $KG(6,2)$, the Lovasz formula specializes to \begin{align*} \chi(KG(6,2))=6-2\cdot 2+2=6-4+2=4. \end{align*} The least-element coloring gives the matching upper bound: a pair $A\in\binom{[6]}{2}$ receives color $\min A$ when $\min A\in\{1,2,3\}$, and receives color $4$ when $\min A\ge 4$. In the final case, both elements of $A$ lie in $\{4,5,6\}$, so the fourth color is assigned exactly to the pairs contained in $\{4,5,6\}$. We show why three colors are impossible by the Gale-cover argument. Here \begin{align*} d=n-2k=6-2\cdot 2=2, \end{align*} so *Gale Lemma* gives points $p_1,\dots,p_6\in S^2$ such that every open hemisphere contains at least $2$ of them. If a proper $3$-coloring existed, define, for $i=1,2,3$, \begin{align*} U_i=\{x\in S^2:\text{there is a }2\text{-set }A\subset[6]\text{ with }c(A)=i\text{ and }p_a\cdot x>0\text{ for all }a\in A\}. \end{align*} Every $x\in S^2$ lies in some $U_i$, because the open hemisphere centered at $x$ contains at least two labels, those two labels form a vertex of $KG(6,2)$, and that vertex has one of the three colors. Each $U_i$ avoids antipodal pairs. If $x\in U_i$ and $-x\in U_i$, then there are same-colored pairs $A,B\in\binom{[6]}{2}$ such that $p_a\cdot x>0$ for every $a\in A$, and $p_b\cdot(-x)>0$ for every $b\in B$. The [second inequality](/theorems/2136) is the same as $p_b\cdot x<0$ for every $b\in B$. A label $\ell$ cannot lie in both $A$ and $B$, since then $p_\ell\cdot x>0$ and $p_\ell\cdot x<0$ would both hold. Hence $A\cap B=\varnothing$, so $A$ and $B$ are adjacent vertices of $KG(6,2)$ with the same color, contradicting properness. Therefore a hypothetical $3$-coloring would give an open cover $S^2=U_1\cup U_2\cup U_3$ in which no $U_i$ contains an antipodal pair. This contradicts the *Lyusternik Schnirelmann Antipodal Cover Theorem* for $d=2$, which says that any cover of $S^2$ by $d+1=3$ open sets has some set containing antipodal points. Hence $\chi(KG(6,2))\ge 4$, and together with the least-element coloring this gives $\chi(KG(6,2))=4$. [/example] ## The Neighborhood Complex Where is the topology of a graph located before any geometric Gale configuration is chosen? Lovasz's original proof packages it into the neighborhood complex, a simplicial complex built from common neighborhoods in the graph. [definition: Neighborhood Complex] For a graph $G$, the neighborhood complex $N(G)$ is the abstract simplicial complex whose vertices are the vertices of $G$ and whose faces are the nonempty finite subsets $\sigma\subset V(G)$ for which there exists $v\in V(G)$ adjacent to every vertex in $\sigma$. [/definition] The complex records which sets of vertices have a common neighbor. To see why this construction is relevant to coloring, we first compute it for the target graph of an $m$-coloring. [example: Neighborhood Complex Of A Complete Graph] Let $V(K_m)=\{1,\dots,m\}$. A face of $N(K_m)$ is a nonempty subset $\sigma\subset V(K_m)$ that has a common neighbor in $K_m$, meaning a vertex $v\in V(K_m)$ adjacent to every element of $\sigma$. If $\sigma$ is a proper nonempty subset of $V(K_m)$, choose $v\in V(K_m)\setminus \sigma$. Since $K_m$ has an edge between every two distinct vertices, $v$ is adjacent to every element of $\sigma$, so $\sigma$ is a face of $N(K_m)$. If $\sigma=V(K_m)$, then a common neighbor would have to be a vertex $v\in V(K_m)$ adjacent to every vertex of $V(K_m)$, including itself. But graphs here have no loops, so no vertex is adjacent to itself. Hence $V(K_m)$ is not a face of $N(K_m)$. Thus the faces of $N(K_m)$ are exactly the nonempty proper subsets of $\{1,\dots,m\}$. These are precisely the faces of the boundary of the simplex with vertex set $\{1,\dots,m\}$. Since that simplex has $m$ vertices, it has dimension $m-1$, and its boundary is homeomorphic to $S^{m-2}$. Now let $c:V(G)\to \{1,\dots,m\}$ be a proper $m$-coloring. If $uv$ is an edge of $G$, then properness gives $c(u)\ne c(v)$, so $c(u)c(v)$ is an edge of $K_m$. Therefore $c$ is a graph homomorphism $G\to K_m$. If $\sigma\in N(G)$, then some vertex $w\in V(G)$ is adjacent to every vertex of $\sigma$. Applying $c$, the vertex $c(w)$ is adjacent in $K_m$ to every vertex in $c(\sigma)$, so $c(\sigma)$ is a face of $N(K_m)$. Hence the coloring induces a simplicial map \begin{align*} N(G)\longrightarrow N(K_m)\cong S^{m-2}. \end{align*} So coloring $G$ with $m$ colors produces a canonical map from its neighborhood complex to a sphere of dimension $m-2$. [/example] This computation turns coloring into a map to a sphere. The obstruction theorem asks whether the source complex is too connected to admit such a map when $m$ is small. The proof below uses two standard tools from the topological-combinatorial formulation of graph coloring. The first is the Hom complex $\operatorname{Hom}(K_2,G)$, whose faces record complete bipartite subgraphs of $G$ and whose natural $\mathbb Z/2$-action swaps the two sides. The second is the $\mathbb Z/2$-index, an equivariant version of dimension: highly connected free $\mathbb Z/2$-complexes have large index, and equivariant maps cannot increase it. These tools are imported here to express the same Borsuk--Ulam obstruction used in the Gale-cover proof. [quotetheorem:6489] [citeproof:6489] The hypothesis is a connectivity hypothesis on the whole neighborhood complex, not merely on the graph $G$ itself. A connected graph can have a disconnected or even empty neighborhood complex: for instance, $N(K_2)$ consists of two isolated vertices, and $N(K_1)$ is empty. Thus the theorem is useful only after a genuine topological calculation of $N(G)$. In practice the method has three steps: compute $N(K_m)\cong S^{m-2}$ for the target complete graph, prove that $N(G)$ is sufficiently connected, and then translate the obstruction into a lower bound for $\chi(G)$. For Kneser graphs, the lower bound now depends on estimating the connectivity of a specific neighborhood complex. The required estimate says that $N(KG(n,k))$ is connected through exactly the range needed to recover Kneser's conjecture. [quotetheorem:6490] [citeproof:6490] The range is sharp for recovering Kneser's theorem through Lovasz's bound: increasing the connectivity conclusion by one would force the stronger lower bound $\chi(KG(n,k))\ge n-2k+3$, contradicting the explicit coloring already constructed. The theorem does not claim that the neighborhood complex is a sphere or determine its full homotopy type; it supplies only the connectivity needed for the chromatic obstruction. At the boundary $n=2k$, the asserted connectivity is $(-1)$-connected, meaning nonempty, which matches the fact that the neighborhood complex of a nonempty matching has vertices but need not be connected. Taking $r=n-2k$ in the neighborhood complex bound gives \begin{align*} \chi(KG(n,k))\ge n-2k+2, \end{align*} which matches the explicit coloring from the first section. Thus the neighborhood complex proof and the Gale-cover proof give the same lower bound through different topological encodings. [remark: Why Two Proof Languages] The Gale-cover proof is the most direct route from Borsuk--Ulam to Kneser's conjecture. The neighborhood-complex proof is more structural: it assigns a topological space to every graph and turns coloring into functorial topology. Later developments in topological combinatorics, including box complexes and Hom complexes, refine this second language because it interacts well with graph homomorphisms. [/remark] The chapter therefore ends with two equivalent perspectives on the same phenomenon. A coloring either gives an antipodal cover of a sphere through Gale's lemma, or it gives a map out of a highly connected graph complex. In both cases the topological obstruction measures the same combinatorial fact: disjointness graphs cannot be colored below the Lovasz bound. Lovász's theorem shows that symmetry and connectivity can force large chromatic number, but the same phenomenon becomes more flexible once it is packaged as an index or obstruction invariant. Chapter 6 abstracts the method so that many different test spaces and equivariant maps can be compared by a single obstruction framework. # 6. Index Theory and Equivariant Obstructions Index theory packages Borsuk--Ulam phenomena into a reusable obstruction: if a combinatorial construction would force an equivariant map that topology forbids, then the construction cannot exist. Chapters 2 through 5 developed connectivity, deleted joins, Borsuk-Ulam obstructions, and graph test spaces; this chapter introduces the cohomological index as a numerical invariant that turns equivariant nonexistence into inequalities. The central theme is monotonicity: equivariant maps can only decrease index, so lower bounds for source spaces and upper bounds for target spaces become combinatorial lower bounds. ## Measuring Free Involutions When a space carries a symmetry with no fixed points, the first question is how complicated that symmetry is. For $\tau:X\to X$ with $\tau^2=\operatorname{id}_X$, equivariant maps from $X$ to spheres compare the action on $X$ with the antipodal action. The index records the smallest sphere that can receive such a comparison map, or equivalently the largest cohomological obstruction visible in the quotient. [definition: Free Z Two Space] A free $\mathbb Z/2$-space is a topological space $X$ equipped with a continuous map $\tau:X\to X$ such that $\tau^2=\operatorname{id}_X$ and $\tau(x)\ne x$ for every $x\in X$. [/definition] The condition excludes fixed points because fixed points would collapse the antipodal obstruction at once: a constant map at a fixed point would respect the group action. The basic models are spheres with the antipodal action, and finite complexes whose vertices are paired by an involution extending to simplices. To compare two spaces with involutions, maps must preserve the symmetry. This is the categorical language behind every deleted-product and box-complex translation later in the chapter. [definition: Equivariant Map] Let $(X,\tau_X)$ and $(Y,\tau_Y)$ be free $\mathbb Z/2$-spaces. A continuous map $f:X\to Y$ is $\mathbb Z/2$-equivariant if \begin{align*} f(\tau_X x)=\tau_Y f(x) \end{align*} for all $x\in X$. [/definition] Equivariant maps are symmetry-preserving reductions. If a coloring problem produces such a map into a low-dimensional sphere, and topology says no such map exists, then the coloring cannot have existed. [definition: Spherical Index] For a free $\mathbb Z/2$-space $X$, the spherical $\mathbb Z/2$-index is \begin{align*} \operatorname{ind}_{\mathbb Z/2}(X)=\min\{n\ge 0: \text{there exists a }\mathbb Z/2\text{-equivariant map }X\to S^n\}, \end{align*} where $S^n$ has the antipodal action. If no such $n$ exists, set $\operatorname{ind}_{\mathbb Z/2}(X)=\infty$. [/definition] This definition is geometric and direct. Cohomology gives a computable version that behaves well under quotients, and in finite-complex examples it is often the form used to prove lower bounds. [definition: Cohomological Index] Let $X$ be a free $\mathbb Z/2$-space, and let $q:X\to X/(\mathbb Z/2)$ be the quotient map. The associated double cover has a first Stiefel--Whitney class $w_1(X)\in H^1(X/(\mathbb Z/2);\mathbb F_2)$. The cohomological $\mathbb Z/2$-index is \begin{align*} \operatorname{coind}_{\mathbb Z/2}(X)=\max\{k\ge 0: w_1(X)^k\ne 0\in H^k(X/(\mathbb Z/2);\mathbb F_2)\}, \end{align*} with value $-1$ if $X=\varnothing$. [/definition] The notation varies in the literature: some authors call this quantity the height or cohomological index. The next issue is whether this cohomological number really obstructs equivariant maps to spheres. The answer is yes because every equivariant map descends to quotient spaces and pulls the canonical class on projective space back to $w_1(X)$. [quotetheorem:6491] [citeproof:6491] The freeness hypothesis is essential because the quotient map must be a genuine double cover with a Stiefel--Whitney class; fixed points destroy that construction. The theorem gives only a lower bound for the spherical index, not a full calculation in general, because cohomology may miss obstructions that are not detected by powers of $w_1(X)$. Its role in the chapter is to turn quotient cohomology computations into index lower bounds that can later be combined with monotonicity. [example: Antipodal Sphere] Let $S^n=\{x\in\mathbb R^{n+1}: |x|=1\}$ and define $\tau:S^n\to S^n$ by $\tau(x)=-x$. Then \begin{align*} \tau^2(x)=\tau(-x)=-(-x)=x, \end{align*} and if $\tau(x)=x$, then $-x=x$, so $2x=0$, hence $x=0$, contradicting $|x|=1$. Thus $S^n$ is a free $\mathbb Z/2$-space. The identity map witnesses $\operatorname{ind}_{\mathbb Z/2}(S^n)\le n$, because \begin{align*} \operatorname{id}_{S^n}(\tau(x))=\operatorname{id}_{S^n}(-x)=-x=-\operatorname{id}_{S^n}(x). \end{align*} For the reverse inequality, the quotient of the antipodal action is $\mathbb RP^n$, and the associated first Stiefel--Whitney class is the standard generator $a\in H^1(\mathbb RP^n;\mathbb F_2)$. Since \begin{align*} H^*(\mathbb RP^n;\mathbb F_2)\cong \mathbb F_2[a]/(a^{n+1}), \end{align*} we have $a^n\ne 0$ and $a^{n+1}=0$, so $\operatorname{coind}_{\mathbb Z/2}(S^n)=n$. By *Cohomological Lower Bound*, \begin{align*} n=\operatorname{coind}_{\mathbb Z/2}(S^n)\le \operatorname{ind}_{\mathbb Z/2}(S^n). \end{align*} Combining the two inequalities gives $\operatorname{ind}_{\mathbb Z/2}(S^n)=n$. Thus the antipodal $n$-sphere is exactly the $n$-dimensional comparison object: it maps equivariantly to itself, but not to any lower-dimensional antipodal sphere. [/example] The lower bound makes cohomology a source of index estimates, but applications also require index estimates to pass through maps built from combinatorial data. This is the point of monotonicity: an equivariant reduction from $X$ to $Y$ cannot make the obstruction larger. The theorem below phrases the quotient maps as principal $\mathbb Z/2$-bundles. In the present setting this means exactly that the free action makes each orbit projection a two-sheeted cover whose two points in each fiber differ by the nontrivial element of $\mathbb Z/2$. Thus the principal-bundle language is the structured version of the double-cover language used to define $w_1(X)$. [quotetheorem:6492] [citeproof:6492] The direction of the inequality is part of the content: a map out of $X$ into $Y$ can only make $X$ no more difficult than $Y$ as an equivariant test space. Equivariance cannot be dropped, since ordinary continuous maps ignore the antipodal symmetry and would make many of these spaces comparable for irrelevant reasons. Monotonicity also does not assert that maps exist whenever the inequality holds; it is a necessary condition used mainly by contrapositive arguments. Monotonicity is the engine behind the obstruction method. Once the indices of spheres are known, it immediately recovers the antipodal-map form of Borsuk--Ulam. [example: Borsuk Ulam From Monotonicity] Assume, for contradiction, that there is an antipode-preserving map $f:S^n\to S^{n-1}$, so \begin{align*} f(-x)=-f(x) \end{align*} for every $x\in S^n$. This is exactly a $\mathbb Z/2$-equivariant map from the antipodal $S^n$ to the antipodal $S^{n-1}$. By *Monotonicity Of Z Two Index*, \begin{align*} \operatorname{ind}_{\mathbb Z/2}(S^n)\le \operatorname{ind}_{\mathbb Z/2}(S^{n-1}). \end{align*} By *Index Of Spheres*, the two indices are \begin{align*} \operatorname{ind}_{\mathbb Z/2}(S^n)=n \end{align*} and \begin{align*} \operatorname{ind}_{\mathbb Z/2}(S^{n-1})=n-1. \end{align*} Substituting these values into the monotonicity inequality gives \begin{align*} n\le n-1. \end{align*} Subtracting $n-1$ from both sides gives \begin{align*} 1\le 0, \end{align*} which is false. Therefore no antipode-preserving map $S^n\to S^{n-1}$ exists, which is the antipodal-map form of Borsuk--Ulam. [/example] ## Spheres, Joins, and Deleted Complexes The next problem is to compute the index for the spaces that actually arise in combinatorics. Spheres provide the calibration, joins build larger test spaces from smaller ones, and deleted complexes encode the instruction that selected faces must be disjoint. These three families are the standard inputs to Borsuk--Ulam methods. [quotetheorem:6493] [citeproof:6493] The theorem depends on the antipodal action, not merely on the underlying topological sphere. A sphere with a different involution would have a different quotient and a different Stiefel--Whitney class, so the projective-space calculation would no longer apply in this form. This calculation calibrates the whole obstruction method: whenever a combinatorial construction is shown to have the equivariant type of $S^n$, its index is exactly known. This theorem is the numerical content behind Borsuk--Ulam. To build higher-dimensional test spaces from smaller combinatorial pieces, we need an operation whose topology raises dimension and preserves the free symmetry. [definition: Join Of Free Z Two Spaces] Let $(X,\tau_X)$ and $(Y,\tau_Y)$ be free $\mathbb Z/2$-spaces. Their join $X*Y$ is the quotient of $X\times Y\times[0,1]$ by the relations identifying all points with the same $x$ at $t=0$ and all points with the same $y$ at $t=1$. The diagonal involution is the map $\tau:X*Y\to X*Y$ defined by \begin{align*} \tau:[x,y,t]\mapsto[\tau_Xx,\tau_Yy,t]. \end{align*} [/definition] The join construction turns two spaces into a space of interpolated choices. To use joins as test spaces, we must know how the index changes under this operation in the basic sphere case. The following calculation supplies that model and explains why repeated joins appear in deleted-join arguments. [quotetheorem:6494] [citeproof:6494] The square-root parametrisation matters because it lands on the unit sphere and handles the two endpoint identifications of the join. The statement is special to spheres with the diagonal antipodal action; for arbitrary free spaces the join often raises connectivity, but it need not have a spherical homeomorphism. The result justifies treating repeated joins of paired discrete choices as honest antipodal spheres in later deleted-join constructions. The sphere-join formula gives a combinatorial model for antipodal spheres whenever a complex is built from paired vertices. The most important special case is the cross-polytope boundary. [example: Iterated Join Of Zero Spheres] Write $J_r=(S^0)^{*r}$ for the $r$-fold join, with the diagonal action exchanging the two points in each copy of $S^0$. For $r=1$, this is $J_1=S^0=S^{1-1}$, and the action is the antipodal action because $1$ and $-1$ are exchanged. Assume that $J_r$ is equivariantly homeomorphic to $S^{r-1}$. Then \begin{align*} J_{r+1}=J_r*S^0. \end{align*} Using the inductive equivariant homeomorphism on the first factor gives \begin{align*} J_r*S^0\cong S^{r-1}*S^0. \end{align*} By *Sphere Join Index* with $a=r-1$ and $b=0$, \begin{align*} S^{r-1}*S^0\cong S^{(r-1)+0+1}=S^r \end{align*} equivariantly. Hence $J_{r+1}\cong S^r$ equivariantly, and induction gives \begin{align*} (S^0)^{*(n+1)}\cong S^n. \end{align*} In this join model there is one opposite pair of vertices from each copy of $S^0$, and a simplex chooses at most one vertex from each pair. That is exactly the boundary complex of the $(n+1)$-dimensional cross-polytope, so this boundary is a purely combinatorial model of the antipodal $n$-sphere. [/example] The iterated join example shows how paired choices produce spheres. In many combinatorial problems, however, the relevant pairs must also be disjoint, so the next construction removes all pairs of faces that share vertices. [definition: Deleted Product] Let $K$ be a finite simplicial complex. The deleted product of $K$ is \begin{align*} K^{\times 2}_{\Delta}=\bigcup\{\sigma\times\tau: \sigma,\tau\in K,\ \sigma\cap\tau=\varnothing\}\subset |K|\times |K|. \end{align*} It is equipped with the involution $\tau:K^{\times 2}_{\Delta}\to K^{\times 2}_{\Delta}$ defined by \begin{align*} \tau:(x,y)\mapsto(y,x). \end{align*} [/definition] The deleted product records ordered disjoint faces. For arguments involving convex combinations, the join version is often more flexible because it keeps the two weights as part of the topology. [definition: Deleted Join] Let $K$ be a finite simplicial complex. The deleted join of $K$ is \begin{align*} K^{*2}_{\Delta}=\bigcup\{\sigma*\tau: \sigma,\tau\in K,\ \sigma\cap\tau=\varnothing\}\subset K*K. \end{align*} It is equipped with the involution $\tau:K^{*2}_{\Delta}\to K^{*2}_{\Delta}$ defined by \begin{align*} \tau:[x,y,t]\mapsto[y,x,1-t]. \end{align*} [/definition] The deleted join is free because a point fixed by the swap would require the same support to occur in both disjoint faces. In applications, high connectivity or high index of a deleted join prevents maps to low-dimensional spheres. [example: Deleted Join Of A Simplex] Let $K=\Delta^n$ have vertex set $\{1,\dots,n+1\}$. A simplex of $K^{*2}_{\Delta}$ has the form $\sigma*\tau$ with $\sigma,\tau\subseteq \{1,\dots,n+1\}$ and $\sigma\cap\tau=\varnothing$. Thus, for each vertex $i$, the deleted join may contain $i$ from the first copy or $i$ from the second copy, but not both. Let \begin{align*} C=\operatorname{conv}\{\pm e_1,\dots,\pm e_{n+1}\}\subset\mathbb R^{n+1} \end{align*} be the $(n+1)$-dimensional cross-polytope. Its boundary complex has vertex set $\{e_i,-e_i:1\le i\le n+1\}$, and its simplices are exactly the subsets containing no opposite pair $\{e_i,-e_i\}$. Define a vertex map by sending the vertex $i$ in the first copy of $K$ to $e_i$, and the vertex $i$ in the second copy of $K$ to $-e_i$. Since $\sigma\cap\tau=\varnothing$, the image of every simplex $\sigma*\tau$ contains no pair $\{e_i,-e_i\}$, so it is a simplex of $\partial C$. Conversely, every simplex of $\partial C$ chooses at most one vertex from each pair $\{e_i,-e_i\}$, hence uniquely determines disjoint subsets $\sigma$ and $\tau$ of the two copies of $K$. Therefore the vertex map is a simplicial isomorphism \begin{align*} K^{*2}_{\Delta}\cong \partial C. \end{align*} The involution on $K^{*2}_{\Delta}$ swaps the two copies. Under the simplicial isomorphism, this sends \begin{align*} e_i\longmapsto -e_i \end{align*} for every $i$, which is exactly the antipodal action on $\partial C$. Finally, \begin{align*} C=\{x\in\mathbb R^{n+1}: |x_1|+\cdots+|x_{n+1}|\le 1\} \end{align*} and hence \begin{align*} \partial C=\{x\in\mathbb R^{n+1}: |x_1|+\cdots+|x_{n+1}|=1\}. \end{align*} The radial map \begin{align*} x\longmapsto \frac{x}{\|x\|} \end{align*} is a homeomorphism $\partial C\to S^n$, with inverse \begin{align*} u\longmapsto \frac{u}{|u_1|+\cdots+|u_{n+1}|}. \end{align*} The denominator in the inverse is nonzero because $u\in S^n$ is not the zero vector. Both maps commute with $x\mapsto -x$, so $K^{*2}_{\Delta}$ is equivariantly homeomorphic to the antipodal sphere $S^n$. Thus the standard Borsuk--Ulam test sphere is realized by the deleted join of a simplex. [/example] The deleted-join model shows why spheres are useful test objects, but later arguments need an obstruction when the source is only highly connected rather than literally a sphere. The problem is to rule out equivariant maps from such a source into a low-dimensional free complex; high connectivity supplies exactly that nonexistence criterion. [remark: Dold Theorem External Input] Let $X$ be an $n$-connected free $\mathbb Z/2$-CW complex, and let $Y$ be a free $\mathbb Z/2$-CW complex of dimension at most $n$. There is no $\mathbb Z/2$-equivariant map $X\to Y$. [/remark] In this course Dold's theorem is used as a black-box obstruction theorem. Its proof belongs to equivariant obstruction theory: the obstruction to constructing an equivariant map lies in cohomology groups of the quotient with twisted coefficients, and the hypotheses force the relevant obstruction to survive. The connectivity and dimension assumptions pull in opposite directions: the source is too highly connected for the target to receive an equivariant map of that dimension. Freeness is again essential, since the theorem is about maps compatible with a free group action rather than about ordinary maps between CW complexes. Dold's theorem is stronger than an index computation in many applications, but it does not supply the index value of either space; it supplies a nonexistence statement once the connectivity and target dimension are known. [example: Dold Obstruction To Low-Dimensional Targets] Let $X$ be an $n$-connected free $\mathbb Z/2$-CW complex. The antipodal sphere $S^n$ is also a free $\mathbb Z/2$-CW complex, and its CW dimension is $n$. Therefore the hypotheses of *[Dold Theorem](/theorems/6495)* apply with $Y=S^n$: the source is $n$-connected and free, while the target is free and has dimension at most $n$. Hence there is no $\mathbb Z/2$-equivariant map \begin{align*} X\longrightarrow S^n. \end{align*} In a combinatorial application, $X$ is often a deleted join equipped with its swapping involution. Once a join-connectivity theorem proves that this deleted join is $n$-connected, any proposed coloring, partition, or avoidance construction that produces an equivariant map \begin{align*} X\longrightarrow S^n \end{align*} contradicts the obstruction above. Thus the topological input rules out exactly those combinatorial constructions whose target sphere has dimension no larger than the verified connectivity of $X$. [/example] ## From Combinatorial Data to Equivariant Nonexistence The method now becomes a translation problem. A coloring, cover, or selection rule is converted into an equivariant map; an index calculation then says the map cannot exist in the asserted dimension. This section records the two main templates used later: cover-to-sphere maps and graph-coloring maps through box complexes. [explanation: The Obstruction Template] A typical Borsuk--Ulam argument has three steps. First, build a free $\mathbb Z/2$-space $X$ from the combinatorial problem, usually a deleted product, deleted join, or box complex. Second, show that a desired combinatorial structure, such as a $k$-coloring, would define an equivariant map $X\to S^{k-2}$ or to another low-index space. Third, prove $\operatorname{ind}_{\mathbb Z/2}(X)>k-2$, either by cohomology, connectivity, or comparison with a sphere. The conclusion is contrapositive: if the index of $X$ is too large for the proposed target, then the combinatorial structure cannot exist. This explains why the topology often appears as a lower bound for a discrete invariant. [/explanation] Covering problems give the cleanest instance of this template. The data of an open cover can be assembled into a map to a simplex by a [partition of unity](/page/Partition%20of%20Unity), and antipodal constraints force the image into a deleted or boundary subcomplex. [example: Antipodal Covering Obstruction] Let $S^n$ be covered by open sets $U_1,\dots,U_m$, and assume that no $U_i$ contains both $x$ and $-x$ for any $x\in S^n$. Choose a partition of unity $\lambda_1,\dots,\lambda_m$ subordinate to this cover, so $\lambda_i\ge 0$, $\sum_{i=1}^m\lambda_i(x)=1$, and $\lambda_i(x)>0$ implies $x\in U_i$. Define \begin{align*} g(x)=(\lambda_1(x)-\lambda_1(-x),\dots,\lambda_m(x)-\lambda_m(-x)). \end{align*} Then \begin{align*} \sum_{i=1}^m g_i(x)=\sum_{i=1}^m(\lambda_i(x)-\lambda_i(-x))=\sum_{i=1}^m\lambda_i(x)-\sum_{i=1}^m\lambda_i(-x)=1-1=0. \end{align*} Thus $g(x)$ lies in the hyperplane \begin{align*} H=\{y\in\mathbb R^m:y_1+\cdots+y_m=0\}. \end{align*} The vector $g(x)$ is never zero. If $g(x)=0$, then $\lambda_i(x)=\lambda_i(-x)$ for every $i$. Since $\sum_i\lambda_i(x)=1$, some $j$ satisfies $\lambda_j(x)>0$, and hence \begin{align*} \lambda_j(-x)=\lambda_j(x)>0. \end{align*} By subordination, $x\in U_j$ and $-x\in U_j$, contradicting the assumption that $U_j$ contains no antipodal pair. Therefore $g(x)\ne 0$ for all $x\in S^n$. Moreover, \begin{align*} g(-x)=(\lambda_1(-x)-\lambda_1(x),\dots,\lambda_m(-x)-\lambda_m(x))=-g(x). \end{align*} So the normalized map \begin{align*} h:S^n\to H\cap S^{m-1},\qquad h(x)=\frac{g(x)}{\|g(x)\|} \end{align*} is well-defined. Since $\|g(-x)\|=\|-g(x)\|=\|g(x)\|$, we get \begin{align*} h(-x)=\frac{g(-x)}{\|g(-x)\|}=\frac{-g(x)}{\|g(x)\|}=-h(x). \end{align*} Thus $h$ is antipode-preserving. The hyperplane $H$ has dimension $m-1$, so its unit sphere $H\cap S^{m-1}$ is homeomorphic to $S^{m-2}$ with the antipodal action. Hence $h$ is a $\mathbb Z/2$-equivariant map $S^n\to S^{m-2}$. If $m\le n+1$, then $m-2\le n-1$. By *Monotonicity Of Z Two Index* and *Index Of Spheres*, the existence of this equivariant map implies \begin{align*} n=\operatorname{ind}_{\mathbb Z/2}(S^n)\le \operatorname{ind}_{\mathbb Z/2}(S^{m-2})=m-2\le n-1. \end{align*} This gives $n\le n-1$, a contradiction. Therefore any open cover of $S^n$ by sets containing no antipodal pair must have at least $n+2$ sets. [/example] Graph coloring requires a test complex whose topology detects colorability. The box complex is one common choice: its vertices remember on which side of a bipartite test an original graph vertex is placed. [definition: Box Complex] Let $G$ be a finite graph. The box complex $B(G)$ is the order complex of the poset whose elements are ordered pairs $(A,B)$ of nonempty subsets of $V(G)$ such that every vertex of $A$ is adjacent in $G$ to every vertex of $B$, ordered by coordinatewise inclusion. Its involution is the simplicial map $\tau:B(G)\to B(G)$ induced by \begin{align*} \tau:(A,B)\mapsto(B,A). \end{align*} [/definition] The nonempty two-sided condition is the point that makes the complete-graph calibration come out in dimension $m-2$ rather than $m-1$. This variant is often denoted $\operatorname{Hom}(K_2,G)$, viewed either as a cell complex or as the order complex of its face poset. The box complex is useful because graph homomorphisms induce equivariant maps of box complexes. Since a proper coloring of $G$ is the same as a graph homomorphism $G\to K_m$, the next question is what obstruction this functoriality places on $m$. The answer is a lower bound for $\chi(G)$ in terms of $\operatorname{ind}_{\mathbb Z/2}(B(G))$. [quotetheorem:6496] [citeproof:6496] The theorem uses the specific box-complex model above; variants that allow empty sides have a different calibration and would change the numerical shift. It gives a lower bound only: a large index forces many colors, but a small index does not construct a coloring. The proof is functorial, so later applications reduce to proving high index for the graph's test complex rather than arguing directly about every possible coloring. The theorem converts topological information about $B(G)$ into a numerical lower bound for coloring. Complete graphs provide the calibration test for this estimate. [example: Complete Graphs] For $m\ge 2$, the complete-graph calibration gives a $\mathbb Z/2$-equivariant homotopy equivalence between $B(K_m)$ and the antipodal sphere $S^{m-2}$. Equivariant homotopy equivalence gives equivariant maps in both directions, so monotonicity gives both inequalities \begin{align*} \operatorname{ind}_{\mathbb Z/2}(B(K_m))\le \operatorname{ind}_{\mathbb Z/2}(S^{m-2}) \end{align*} and \begin{align*} \operatorname{ind}_{\mathbb Z/2}(S^{m-2})\le \operatorname{ind}_{\mathbb Z/2}(B(K_m)). \end{align*} Thus the two indices are equal. By *Index Of Spheres*, \begin{align*} \operatorname{ind}_{\mathbb Z/2}(S^{m-2})=m-2, \end{align*} so \begin{align*} \operatorname{ind}_{\mathbb Z/2}(B(K_m))=m-2. \end{align*} Applying *Box Complex Chromatic Lower Bound* to $G=K_m$ gives \begin{align*} \chi(K_m)\ge \operatorname{ind}_{\mathbb Z/2}(B(K_m))+2. \end{align*} Substituting the computed index gives \begin{align*} \chi(K_m)\ge (m-2)+2=m. \end{align*} For the opposite inequality, label the vertices of $K_m$ by $1,\dots,m$ and color vertex $i$ with color $i$. If $i\ne j$, then the edge $\{i,j\}$ has endpoint colors $i$ and $j$, which are distinct, so this is a proper $m$-coloring. Hence \begin{align*} \chi(K_m)\le m. \end{align*} Combining the lower and upper bounds gives \begin{align*} \chi(K_m)=m. \end{align*} Thus the box-complex lower bound is sharp on complete graphs. [/example] For Kneser-type graphs, the same theorem becomes powerful because the box complex has high index for geometric reasons. This is the point where the abstract obstruction language returns concrete chromatic information. [example: Kneser Graph Lower Bound] Let $KG(n,k)$ be the graph whose vertices are the $k$-subsets of $\{1,\dots,n\}$, with an edge between two vertices exactly when the corresponding $k$-subsets are disjoint. The topological input for Kneser graphs is the index estimate \begin{align*} \operatorname{ind}_{\mathbb Z/2}(B(KG(n,k)))\ge n-2k. \end{align*} Applying *Box Complex Chromatic Lower Bound* to $G=KG(n,k)$ gives \begin{align*} \chi(KG(n,k))\ge \operatorname{ind}_{\mathbb Z/2}(B(KG(n,k)))+2. \end{align*} Since $\operatorname{ind}_{\mathbb Z/2}(B(KG(n,k)))\ge n-2k$, adding $2$ to both sides gives \begin{align*} \operatorname{ind}_{\mathbb Z/2}(B(KG(n,k)))+2\ge n-2k+2. \end{align*} Combining the two inequalities yields \begin{align*} \chi(KG(n,k))\ge n-2k+2. \end{align*} Thus the box-complex obstruction proves the lower-bound half of Lovasz's theorem on Kneser graphs: every proper coloring of $KG(n,k)$ uses at least $n-2k+2$ colors. Together with the least-element coloring constructed earlier, which gives the matching upper bound, this yields the expected chromatic number. [/example] The Kneser example shows why the index language is worth the setup: a difficult coloring lower bound becomes the statement that no equivariant map to a small sphere can exist. This also clarifies a common misconception about the method. [remark: Why Equivariance Is The Whole Point] Without the involution, many of the spaces in this chapter are contractible or map to low-dimensional targets for uninteresting reasons. The obstruction is not merely that a continuous map fails to exist; it is that a map respecting the combinatorial symmetry fails to exist. This is why deleted constructions and box complexes are designed with a free swapping action built in. [/remark] The chapter's output is a reusable dictionary. High index of a test space means that every equivariant target sphere must have high dimension; a low-dimensional target produced from a coloring or cover would contradict monotonicity. Later chapters apply this dictionary to Lovasz's proof of Kneser's conjecture, Tucker--Ky Fan lemmas, and Tverberg-type partition theorems. With the obstruction language in place, the course moves from abstract nonexistence results to geometric partition theorems. Ham sandwich and mass partition statements are natural because they ask for symmetric cuts, and those are exactly the kind of problems that Borsuk-Ulam methods are built to handle. # 7. Ham Sandwich and Mass Partition Theorems This chapter turns the Borsuk-Ulam theorem into partition results in geometry and fair division. It uses the antipodal maps and Borsuk-Ulam theorem from Chapter 3, together with compactness, finite Borel measures, and the basic topology of spheres. The guiding question is simple to state: when several objects are spread through Euclidean space, can a single hyperplane divide each of them into two equal parts at once? We first express this question as a configuration-space problem, then prove the ham sandwich theorem, and finally record two discrete analogues that replace continuous masses by finite beads or finite measures. ## Bisecting Measures by Hyperplanes The geometric problem begins with the need to measure how much of an object lies on either side of a hyperplane. For point sets with boundary this is awkward if we count points, so the right input is a finite measure on Euclidean space. [definition: Finite Borel Measure On Euclidean Space] A finite Borel measure on $\mathbb R^d$ is a measure \begin{align*} \mu:\mathcal B(\mathbb R^d)\longrightarrow [0,\infty) \end{align*} such that $\mu(\mathbb R^d)<\infty$. [/definition] This includes area in planar regions, volume in solids, weighted density functions, and finite point configurations. The finiteness assumption makes it meaningful to ask for half of the total mass. [example: Area Measure Of A Planar Region] Let $A\subset \mathbb R^2$ be a bounded Borel set, and define $\mu(E)=\mathcal L^2(E\cap A)$ for every Borel set $E\subset \mathbb R^2$. Since $E\cap A$ is Borel, this assigns a number in $[0,\infty]$ to each Borel set. If $E_1,E_2,\ldots$ are pairwise disjoint Borel sets, then $E_i\cap A$ are pairwise disjoint and \begin{align*} \mu\!\left(\bigcup_{i=1}^{\infty}E_i\right)=\mathcal L^2\!\left(\bigcup_{i=1}^{\infty}(E_i\cap A)\right)=\sum_{i=1}^{\infty}\mathcal L^2(E_i\cap A)=\sum_{i=1}^{\infty}\mu(E_i). \end{align*} Thus $\mu$ is a Borel measure. Also, \begin{align*} \mu(\mathbb R^2)=\mathcal L^2(\mathbb R^2\cap A)=\mathcal L^2(A). \end{align*} Because $A$ is bounded, there is some $R>0$ with $A\subset [-R,R]^2$, so \begin{align*} \mathcal L^2(A)\le \mathcal L^2([-R,R]^2)=(2R)(2R)<\infty. \end{align*} Hence $\mu$ is finite. Now let $L=H(u,t)$ be a line, with closed half-planes $H^+(u,t)$ and $H^-(u,t)$. These satisfy $H^+(u,t)\cup H^-(u,t)=\mathbb R^2$ and $H^+(u,t)\cap H^-(u,t)=L$. Since a line has planar Lebesgue measure $0$, \begin{align*} \mu(L)=\mathcal L^2(L\cap A)=0. \end{align*} Therefore the two measured sides do not overlap in positive $\mu$-mass, and \begin{align*} \mu(H^+(u,t))+\mu(H^-(u,t))=\mu(\mathbb R^2)=\mathcal L^2(A). \end{align*} Thus $L$ bisects $\mu$ exactly when each closed half-plane contains at least half the total $\mu$-mass, which here forces \begin{align*} \mathcal L^2(A\cap H^+(u,t))=\mathcal L^2(A\cap H^-(u,t))=\frac{1}{2}\mathcal L^2(A). \end{align*} So this measure formalizes the geometric statement that the line cuts the planar region $A$ into two equal-area parts, with no ambiguity from area lying on the line because the line has planar area $0$. [/example] The example turns geometric area into a measure, but it has not yet specified how possible cuts are organized. To apply Borsuk-Ulam, we need a configuration space for all oriented cuts, with a symmetry that reverses the choice of side. [definition: Oriented Affine Hyperplane] An oriented affine hyperplane in $\mathbb R^d$ is a pair $(u,t)\in S^{d-1}\times \mathbb R$. It determines \begin{align*} H(u,t)&=\{x\in \mathbb R^d: u\cdot x=t\}. \end{align*} It also determines the closed half-spaces \begin{align*} H^+(u,t)&=\{x\in \mathbb R^d: u\cdot x\ge t\}, \end{align*} and \begin{align*} H^-(u,t)&=\{x\in \mathbb R^d: u\cdot x\le t\}. \end{align*} [/definition] Changing $(u,t)$ to $(-u,-t)$ keeps the same underlying hyperplane but swaps the two half-spaces. We need a balance condition that survives this change of orientation and still records that neither side contains more than half of the measure in the relevant sense. [definition: Bisecting Hyperplane] Let $\mu$ be a finite Borel measure on $\mathbb R^d$. An affine hyperplane $H(u,t)$ bisects $\mu$ if \begin{align*} \mu(H^+(u,t))\ge \frac{1}{2}\mu(\mathbb R^d) \quad\text{and}\quad \mu(H^-(u,t))\ge \frac{1}{2}\mu(\mathbb R^d). \end{align*} [/definition] If $\mu(H(u,t))=0$, the two inequalities are equalities. The inequality formulation is stable under atoms, so it handles point masses without requiring the hyperplane to avoid all mass. [example: Point Masses And Medians] Let $\mu=\sum_{i=1}^n a_i\delta_{x_i}$ on $\mathbb R$, where $a_i>0$ and $x_i\in\mathbb R$. In dimension $1$, an affine hyperplane is a point $t$. With orientation $u=1$, its closed half-spaces are \begin{align*} H^+(1,t)=\{x\in\mathbb R:x\ge t\} \end{align*} and \begin{align*} H^-(1,t)=\{x\in\mathbb R:x\le t\}. \end{align*} The total mass is \begin{align*} \mu(\mathbb R)=\sum_{i=1}^n a_i\delta_{x_i}(\mathbb R)=\sum_{i=1}^n a_i, \end{align*} because $\delta_{x_i}(\mathbb R)=1$ for every $i$. For the left closed side, \begin{align*} \mu(H^-(1,t))=\sum_{i=1}^n a_i\delta_{x_i}(\{x:x\le t\})=\sum_{\{i:x_i\le t\}}a_i. \end{align*} For the right closed side, \begin{align*} \mu(H^+(1,t))=\sum_{i=1}^n a_i\delta_{x_i}(\{x:x\ge t\})=\sum_{\{i:x_i\ge t\}}a_i. \end{align*} Therefore $t$ bisects $\mu$ exactly when \begin{align*} \sum_{\{i:x_i\le t\}}a_i\ge \frac{1}{2}\sum_{i=1}^n a_i \end{align*} and \begin{align*} \sum_{\{i:x_i\ge t\}}a_i\ge \frac{1}{2}\sum_{i=1}^n a_i. \end{align*} This is precisely the weighted median condition: at least half the total weight lies at or to the left of $t$, and at least half lies at or to the right of $t$. If some mass sits exactly at $t$, it is counted on both closed sides, which is why the inequality formulation handles atoms correctly. [/example] The median example explains the balance condition in dimension $1$, including the role of atoms. For the Borsuk-Ulam proof we need to convert balance into the vanishing of a signed coordinate, so we package each oriented hyperplane by its mass imbalance. [definition: Mass Imbalance Function] Let $\mu$ be a finite Borel measure on $\mathbb R^d$. The mass imbalance function of $\mu$ is the map \begin{align*} I_\mu:S^{d-1}\times \mathbb R\longrightarrow \mathbb R \end{align*} defined by \begin{align*} I_\mu(u,t)=\mu(H^+(u,t))-\mu(H^-(u,t)). \end{align*} [/definition] The equation $I_\mu(u,t)=0$ is the signed version of bisection when the boundary hyperplane carries no mass. In the general finite-measure setting, the proof is often phrased through approximation by [absolutely continuous measures](/page/Absolutely%20Continuous%20Measures) or through a compactified configuration space that absorbs boundary mass. ## The Ham Sandwich Theorem From Borsuk-Ulam The central question is whether $d$ masses in $\mathbb R^d$ can be bisected by the same hyperplane. The answer matches the dimension exactly: the $d$ parameters in the direction-offset space are enough to solve $d$ simultaneous balance equations. [quotetheorem:6464] [citeproof:6464] [example: Two Planar Regions Cut By One Line] Let $A,B\subset \mathbb R^2$ be bounded Borel regions with positive area, and define \begin{align*} \mu_A(E)=\mathcal L^2(E\cap A) \quad\text{and}\quad \mu_B(E)=\mathcal L^2(E\cap B) \end{align*} for every Borel set $E\subset \mathbb R^2$. These are finite Borel measures, with \begin{align*} \mu_A(\mathbb R^2)=\mathcal L^2(\mathbb R^2\cap A)=\mathcal L^2(A) \end{align*} and \begin{align*} \mu_B(\mathbb R^2)=\mathcal L^2(\mathbb R^2\cap B)=\mathcal L^2(B). \end{align*} By the *Ham Sandwich Theorem* with $d=2$, there is a line $L=H(u,t)$ whose closed half-planes $H^+(u,t)$ and $H^-(u,t)$ bisect both $\mu_A$ and $\mu_B$. For $A$, the bisection inequalities give \begin{align*} \mathcal L^2(A\cap H^+(u,t))=\mu_A(H^+(u,t))\ge \frac{1}{2}\mu_A(\mathbb R^2)=\frac{1}{2}\mathcal L^2(A) \end{align*} and \begin{align*} \mathcal L^2(A\cap H^-(u,t))=\mu_A(H^-(u,t))\ge \frac{1}{2}\mu_A(\mathbb R^2)=\frac{1}{2}\mathcal L^2(A). \end{align*} For $B$, the same conclusion is \begin{align*} \mathcal L^2(B\cap H^+(u,t))\ge \frac{1}{2}\mathcal L^2(B) \end{align*} and \begin{align*} \mathcal L^2(B\cap H^-(u,t))\ge \frac{1}{2}\mathcal L^2(B). \end{align*} If the cutting line carries no area from either region, then \begin{align*} \mathcal L^2(A\cap L)=0 \end{align*} and \begin{align*} \mathcal L^2(B\cap L)=0. \end{align*} Since \begin{align*} A=(A\cap H^+(u,t))\cup(A\cap H^-(u,t)) \end{align*} and \begin{align*} (A\cap H^+(u,t))\cap(A\cap H^-(u,t))=A\cap L, \end{align*} finite additivity gives \begin{align*} \mathcal L^2(A)=\mathcal L^2(A\cap H^+(u,t))+\mathcal L^2(A\cap H^-(u,t))-\mathcal L^2(A\cap L). \end{align*} Using $\mathcal L^2(A\cap L)=0$, this becomes \begin{align*} \mathcal L^2(A)=\mathcal L^2(A\cap H^+(u,t))+\mathcal L^2(A\cap H^-(u,t)). \end{align*} Both summands are at least $\frac{1}{2}\mathcal L^2(A)$, and their sum is exactly $\mathcal L^2(A)$, so \begin{align*} \mathcal L^2(A\cap H^+(u,t))=\mathcal L^2(A\cap H^-(u,t))=\frac{1}{2}\mathcal L^2(A). \end{align*} Repeating the same argument for $B$ gives \begin{align*} \mathcal L^2(B\cap H^+(u,t))=\mathcal L^2(B\cap H^-(u,t))=\frac{1}{2}\mathcal L^2(B). \end{align*} Thus one straight line cuts both planar regions into equal-area halves, with no discrepancy from material lying on the cut when the line has zero area inside each region. [/example] This example is the planar picture behind the theorem's name: two ingredients laid out in the plane can be cut fairly by one straight cut. The same proof does not become harder in dimension three, because the target dimension grows with the number of measures. [example: Three Solids Cut By One Plane] Let $A_1,A_2,A_3\subset \mathbb R^3$ be bounded Borel solids, and for each $i\in\{1,2,3\}$ define \begin{align*} \mu_i(E)=\mathcal L^3(E\cap A_i) \end{align*} for every Borel set $E\subset \mathbb R^3$. Since $E\cap A_i$ is Borel, this defines a Borel measure. Because $A_i$ is bounded, there is some $R_i>0$ such that $A_i\subset [-R_i,R_i]^3$, so \begin{align*} \mu_i(\mathbb R^3)=\mathcal L^3(\mathbb R^3\cap A_i)=\mathcal L^3(A_i)\le \mathcal L^3([-R_i,R_i]^3)=(2R_i)(2R_i)(2R_i)=8R_i^3<\infty. \end{align*} Thus $\mu_1,\mu_2,\mu_3$ are finite Borel measures on $\mathbb R^3$. By the *Ham Sandwich Theorem* with $d=3$, there is an affine plane $P=H(u,t)$ that bisects all three measures. For each $i\in\{1,2,3\}$, the bisection inequalities give \begin{align*} \mathcal L^3(A_i\cap H^+(u,t))=\mu_i(H^+(u,t))\ge \frac{1}{2}\mu_i(\mathbb R^3)=\frac{1}{2}\mathcal L^3(A_i) \end{align*} and \begin{align*} \mathcal L^3(A_i\cap H^-(u,t))=\mu_i(H^-(u,t))\ge \frac{1}{2}\mu_i(\mathbb R^3)=\frac{1}{2}\mathcal L^3(A_i). \end{align*} An affine plane in $\mathbb R^3$ has three-dimensional Lebesgue measure $0$, hence \begin{align*} \mathcal L^3(A_i\cap P)=0. \end{align*} Also, \begin{align*} A_i=(A_i\cap H^+(u,t))\cup(A_i\cap H^-(u,t)). \end{align*} The overlap of these two closed-side pieces is exactly the part lying on the cutting plane: \begin{align*} (A_i\cap H^+(u,t))\cap(A_i\cap H^-(u,t))=A_i\cap P. \end{align*} By finite additivity with overlap subtracted, \begin{align*} \mathcal L^3(A_i)=\mathcal L^3(A_i\cap H^+(u,t))+\mathcal L^3(A_i\cap H^-(u,t))-\mathcal L^3(A_i\cap P). \end{align*} Using $\mathcal L^3(A_i\cap P)=0$, this becomes \begin{align*} \mathcal L^3(A_i)=\mathcal L^3(A_i\cap H^+(u,t))+\mathcal L^3(A_i\cap H^-(u,t)). \end{align*} The two summands are each at least $\frac{1}{2}\mathcal L^3(A_i)$ and their sum is exactly $\mathcal L^3(A_i)$, so \begin{align*} \mathcal L^3(A_i\cap H^+(u,t))=\mathcal L^3(A_i\cap H^-(u,t))=\frac{1}{2}\mathcal L^3(A_i). \end{align*} Thus one planar cut divides each of the three solids into equal-volume halves, with no volume discrepancy from material lying in the cutting plane. [/example] The theorem is sharp in its basic dimension count. In general, $d+1$ unrelated finite measures in $\mathbb R^d$ cannot be expected to have a common bisecting hyperplane, because the configuration space has only $d$ degrees of freedom after compactification. [remark: Dimension Count] The ham sandwich theorem is not just a measure statement; it is a matching between the number of scalar equations and the topology of the configuration space. The sphere $S^d$ supports an odd map into $\mathbb R^d$ that must vanish, while an odd map into $\mathbb R^{d+1}$ can avoid the origin. This explains why Borsuk-Ulam gives exactly $d$ simultaneous bisections in $\mathbb R^d$. [/remark] ## Stone-Tukey And General Mass Partitions The ham sandwich theorem is often presented in a slightly broader form due to Stone and Tukey. The question now is how much regularity is really needed: must the objects be regions with volume, or can they be arbitrary finite measures? [remark: Stone-Tukey Theorem External Input] Let $\mu_1,\dots,\mu_d$ be finite Borel measures on $\mathbb R^d$. Then there exists an affine hyperplane that bisects all of $\mu_1,\dots,\mu_d$. [/remark] The course states this as the general measure-theoretic form of the ham sandwich theorem. Each hypothesis has content. Finiteness is needed because Lebesgue measure on all of $\mathbb R^d$ has no finite half-mass target, so a phrase such as “half the total mass” no longer defines a real balance condition. Borel measurability is needed because the two sides of a proposed cut must be measurable sets; for instance, if a measure were given only on the two-set $\sigma$-algebra $\{\varnothing,\mathbb R^d\}$, then ordinary half-spaces would not have assigned masses at all. The closed-half-space convention is needed for atoms: a point mass $\delta_a$ in $\mathbb R^d$ is bisected by any hyperplane through $a$ under the closed convention, while the two open sides both have mass $0$ and therefore cannot each contain half the mass. The theorem has limitations as well. It does not control which bisecting hyperplane is chosen, it does not guarantee equality on open sides, and it does not extend to more than $d$ unrelated measures in $\mathbb R^d$. In dimension $1$, two point masses $\delta_0$ and $\delta_1$ give a concrete obstruction: a point $t\in\mathbb R$ bisects $\delta_0$ only when $t=0$, and it bisects $\delta_1$ only when $t=1$, so no single point bisects both. Thus the Stone-Tukey form is not a statement that every finite family of measures admits a common median hyperplane; it is the exact $d$-measure conclusion supplied by the same Borsuk-Ulam dimension count as ham sandwich. The following discussion explains why the closed-half-space convention is the right way to state the conclusion when boundary mass is present. [explanation: Why Closed Inequalities Matter] For a measure with atoms, a hyperplane may carry positive mass. If bisection were defined by equality of the two open sides, a single atom sitting on the hyperplane would break the statement. The closed half-space inequalities instead say that neither side receives less than half the total mass, allowing boundary mass to count on both sides. This convention is also what makes limiting arguments work. If a sequence of hyperplanes bisects approximating measures, a limiting hyperplane may pick up extra mass on its boundary, but it still satisfies the two half-space inequalities for the limiting measure. [/explanation] This broader viewpoint also separates the geometric theorem from the physical imagery of slicing food. The theorem is about simultaneous median hyperplanes for measures, and regions with area or volume are only the most visual case. [example: A Mixed Continuous And Atomic Partition] Let $D\subset \mathbb R^2$ be a disk, and define \begin{align*} \mu_1(E)=\mathcal L^2(E\cap D) \end{align*} for every Borel set $E\subset \mathbb R^2$. Let $p_1,\dots,p_n\in\mathbb R^2$ and $a_1,\dots,a_n>0$, and define the atomic measure \begin{align*} \mu_2=\sum_{j=1}^n a_j\delta_{p_j}. \end{align*} Since $D$ is bounded, \begin{align*} \mu_1(\mathbb R^2)=\mathcal L^2(D)<\infty. \end{align*} Also, \begin{align*} \mu_2(\mathbb R^2)=\sum_{j=1}^n a_j\delta_{p_j}(\mathbb R^2)=\sum_{j=1}^n a_j<\infty. \end{align*} Thus $\mu_1$ and $\mu_2$ are finite Borel measures on $\mathbb R^2$. By the *[Stone-Tukey Theorem](/theorems/6497)* with $d=2$, there is a line $L=H(u,t)$ that bisects both measures. For the disk measure, the bisection inequalities give \begin{align*} \mathcal L^2(D\cap H^+(u,t))=\mu_1(H^+(u,t))\ge \frac{1}{2}\mu_1(\mathbb R^2)=\frac{1}{2}\mathcal L^2(D). \end{align*} Similarly, \begin{align*} \mathcal L^2(D\cap H^-(u,t))=\mu_1(H^-(u,t))\ge \frac{1}{2}\mu_1(\mathbb R^2)=\frac{1}{2}\mathcal L^2(D). \end{align*} A line has planar Lebesgue measure $0$, so \begin{align*} \mathcal L^2(D\cap L)=0. \end{align*} The two closed-side pieces cover $D$: \begin{align*} D=(D\cap H^+(u,t))\cup(D\cap H^-(u,t)). \end{align*} Their overlap is exactly the part of $D$ lying on the line: \begin{align*} (D\cap H^+(u,t))\cap(D\cap H^-(u,t))=D\cap L. \end{align*} Finite additivity with overlap subtracted gives \begin{align*} \mathcal L^2(D)=\mathcal L^2(D\cap H^+(u,t))+\mathcal L^2(D\cap H^-(u,t))-\mathcal L^2(D\cap L). \end{align*} Using $\mathcal L^2(D\cap L)=0$, this becomes \begin{align*} \mathcal L^2(D)=\mathcal L^2(D\cap H^+(u,t))+\mathcal L^2(D\cap H^-(u,t)). \end{align*} The two summands are each at least $\frac{1}{2}\mathcal L^2(D)$ and their sum is exactly $\mathcal L^2(D)$, hence \begin{align*} \mathcal L^2(D\cap H^+(u,t))=\mathcal L^2(D\cap H^-(u,t))=\frac{1}{2}\mathcal L^2(D). \end{align*} For the atomic measure, set $s_j=u\cdot p_j$. Then $p_j\in H^+(u,t)$ exactly when $s_j\ge t$, and $p_j\in H^-(u,t)$ exactly when $s_j\le t$. Therefore \begin{align*} \mu_2(H^+(u,t))=\sum_{j=1}^n a_j\delta_{p_j}(H^+(u,t))=\sum_{\{j:s_j\ge t\}}a_j. \end{align*} Likewise, \begin{align*} \mu_2(H^-(u,t))=\sum_{j=1}^n a_j\delta_{p_j}(H^-(u,t))=\sum_{\{j:s_j\le t\}}a_j. \end{align*} Since $L$ bisects $\mu_2$, these quantities satisfy \begin{align*} \sum_{\{j:s_j\ge t\}}a_j\ge \frac{1}{2}\sum_{j=1}^n a_j. \end{align*} Also, \begin{align*} \sum_{\{j:s_j\le t\}}a_j\ge \frac{1}{2}\sum_{j=1}^n a_j. \end{align*} Thus $t$ is a weighted median of the projected points $s_1,\dots,s_n$ with weights $a_1,\dots,a_n$. The same line cuts the disk into equal-area halves and simultaneously places at least half of the atomic weight on each closed side. [/example] ## Necklace Splitting As A Discrete Analogue A continuous hyperplane cut is not the only way to divide several types of mass fairly. The discrete analogue asks for a fair division of a string of colored beads using a bounded number of cuts. [definition: Colored Necklace] A colored necklace is a finite linearly ordered set of beads, each assigned one color from a fixed set of $q$ colors. For a color $c$, let $N_c$ denote the number of beads of color $c$. [/definition] The fair-division problem asks two thieves to split the necklace so that each receives the same number of beads of every color. Since the beads are indivisible, parity assumptions are necessary. [definition: Fair Two-Way Necklace Splitting] A fair two-way splitting of a colored necklace is a choice of cut positions between beads, followed by an assignment of the resulting intervals to two parts $A$ and $B$, such that for every color $c$ the two parts contain the same number of beads of color $c$. [/definition] The theorem below is the discrete counterpart of ham sandwich for two parts. The number of cuts depends on the number of colors, just as the number of masses in ham sandwich is controlled by dimension. [remark: Discrete Necklace Splitting Theorem External Input] Let a colored necklace have $q$ colors, and suppose that $N_c$ is even for every color $c$. Then there is a fair two-way necklace splitting using at most $q$ cuts. [/remark] The course states this theorem as a discrete analogue rather than proving it in full. The evenness hypothesis is necessary, because if some color occurs an odd number of times then two thieves cannot receive equal integer numbers of beads of that color. The cut bound is also sharp. Take the necklace \begin{align*} c_1c_1\,c_2c_2\,\cdots\,c_qc_q, \end{align*} with two consecutive beads of each color. In any fair splitting, the two beads of color $c_i$ must go to different thieves, so there must be a cut between those two adjacent beads. This forces at least one cut inside each monochromatic pair, hence at least $q$ cuts in total. The theorem controls only the color counts. It does not control the physical lengths of the pieces, the number of intervals received by each thief, the total number of beads in a thief's union when colors have unequal totals, or any preference about keeping neighbouring beads together. Standard proofs pass through a continuous necklace theorem, obtained by applying Borsuk-Ulam to interval measures, and then move the cuts to bead boundaries while preserving the color counts; the next example illustrates why separate colors may force separate cuts. [example: Two Colors Need At Most Two Cuts] Let the necklace contain $2r$ red beads and $2b$ blue beads, where $r,b\ge 0$ are integers. By the *[Discrete Necklace Splitting Theorem](/theorems/6498)* with $q=2$, there is a fair two-way splitting using at most two cuts, so each thief receives \begin{align*} \frac{2r}{2}=r \end{align*} red beads and \begin{align*} \frac{2b}{2}=b \end{align*} blue beads. In the ordered necklace \begin{align*} \underbrace{RR\cdots R}_{2r\text{ red beads}}\underbrace{BB\cdots B}_{2b\text{ blue beads}}, \end{align*} place the first cut after the first $r$ red beads and the second cut after the first $b$ blue beads. This produces the three intervals \begin{align*} \underbrace{RR\cdots R}_{r},\qquad \underbrace{RR\cdots R}_{r}\underbrace{BB\cdots B}_{b},\qquad \underbrace{BB\cdots B}_{b}. \end{align*} Give the first and third intervals to thief $A$, and give the middle interval to thief $B$. Then thief $A$ receives \begin{align*} r\text{ red beads}+b\text{ blue beads}, \end{align*} while thief $B$ receives \begin{align*} r\text{ red beads}+b\text{ blue beads}. \end{align*} Thus two cuts are enough in this block-arranged case, and the cuts are placed to halve each color count rather than to halve the physical length of the necklace. [/example] The example shows that the cuts are not trying to bisect physical length. They bisect each color count, so the relevant masses are the color classes rather than the geometry of the string. [remark: From Beads To Measures] If each color class is replaced by a measure on the interval $[0,1]$, a cut pattern partitions the interval into subintervals and assigns them to thieves. Borsuk-Ulam can then be used to force equality of the $q$ color measures between the two assigned parts. The discrete theorem can be viewed as the integral version of this continuous statement. [/remark] ## The Configuration-Space Pattern The final lesson of the chapter is methodological. Ham sandwich and necklace splitting look different combinatorially, but both are produced by the same topological template. [explanation: Borsuk-Ulam Template For Fair Division] First choose a configuration space whose points encode possible partitions. For hyperplane bisection this is a sphere of oriented hyperplanes after compactification; for continuous necklace splitting it is a space of cut locations and alternating assignments. Next define a test map whose coordinates measure the unfairness of the proposed partition. In the ham sandwich theorem these coordinates are signed mass imbalances. In necklace splitting they are differences between the two thieves' shares of each color. Finally identify a symmetry that reverses the sign of the test map. Swapping the two sides of a hyperplane or swapping the two thieves gives an antipodal action. Borsuk-Ulam-type results then force a zero of the test map, which is exactly a fair partition. [/explanation] This viewpoint is the bridge to later chapters. Once a combinatorial problem can be expressed as the nonexistence of an equivariant map, topological invariants become tools for proving discrete results. The partition theorems show how equivariant nonexistence translates into fair division, and the next chapter pushes the same idea into higher-dimensional discrete geometry. Tverberg-type theorems ask for forced intersections among many pieces, which are again proved by building a test map and showing topology forbids avoiding the origin. # 8. Tverberg-Type Theorems Chapters 3, 5, and 6 used Borsuk-Ulam methods, graph test spaces, and index theory to turn combinatorial statements into the nonexistence of equivariant maps. This chapter brings that method into discrete geometry, where the combinatorial object is a partition of points or faces and the geometric conclusion is an intersection. The guiding question is how much of Radon's elementary affine theorem survives when affine maps from point sets are replaced by continuous maps from simplices. ## Radon Partitions and Affine Tverberg Partitions What forces two convex hulls to intersect? In the plane, four points always split into two parts whose convex hulls meet; in higher dimensions the number is $d+2$. The first result is [Radon's theorem](/theorems/4086), which is the affine seed from which the Tverberg family grows. [definition: Radon Partition] Let $A = \{a_1, \dots, a_m\} \subset \mathbb R^d$ be a finite set. A Radon partition of $A$ is a decomposition $A = A_+ \sqcup A_-$ into two nonempty parts such that \begin{align*} \operatorname{conv}(A_+) \cap \operatorname{conv}(A_-) \ne \varnothing. \end{align*} [/definition] The definition records the desired intersection, but does not explain why such a partition should exist. We need the first universal threshold: affine dependence forces a Radon partition as soon as there are $d+2$ points. [quotetheorem:4086] [citeproof:4086] The number $d+2$ is necessary. With only $d+1$ points, take the vertices of a $d$-simplex in $\mathbb R^d$; the convex hulls of two disjoint subsets are disjoint faces of that simplex, so no Radon partition exists. Radon's theorem also does not prescribe the partition uniquely: for degenerate configurations several affine dependences may give different intersecting pairs. Its content is therefore a sharp existence statement for two parts, not a classification of all possible partitions. Radon's theorem is the two-part case. Tverberg's theorem asks for $r$ parts with a common intersection point, so the relevant threshold must grow with both $r$ and $d$. [definition: Tverberg Partition] Let $A \subset \mathbb R^d$ be a finite set and let $r \ge 2$. A Tverberg partition of $A$ into $r$ parts is a decomposition \begin{align*} A = A_1 \sqcup \cdots \sqcup A_r \end{align*} into nonempty subsets such that \begin{align*} \bigcap_{j=1}^r \operatorname{conv}(A_j) \ne \varnothing. \end{align*} [/definition] A Tverberg point is any point in this common intersection. We need the exact affine threshold at which every configuration is forced to have such an $r$-fold intersection; that threshold is $(r-1)(d+1)+1$ points. [quotetheorem:6499] [citeproof:6499] The bound is sharp. A standard lower-bound configuration takes $r-1$ points very close to each vertex of a $d$-simplex, giving only $(r-1)(d+1)$ points. Any common point of $r$ convex hulls would force each part to meet the same vertex class in the limiting simplex model, but each class contains only $r-1$ available points; after a sufficiently small perturbation the same obstruction remains. Thus the theorem gives the first possible universal number of points. The theorem also does not prescribe where the Tverberg point lies, whether the partition is unique, or which block sizes occur. It asserts existence of at least one suitable partition at the sharp threshold. Examples build geometric intuition for those possibilities, especially in the plane, where the intersection point need not be a vertex and the parts can have different sizes. [example: Radon Partitions In The Plane] Label the four points. If $x$ lies inside the triangle with vertices $a,b,c$, then there are coefficients $\alpha,\beta,\gamma>0$ with \begin{align*} \alpha+\beta+\gamma=1 \end{align*} and \begin{align*} x=\alpha a+\beta b+\gamma c. \end{align*} Thus $x$ is the convex combination $1\cdot x$ of the one-point set $\{x\}$ and also a convex combination of $\{a,b,c\}$. Equivalently, \begin{align*} 1\cdot x-\alpha a-\beta b-\gamma c=0, \qquad 1-\alpha-\beta-\gamma=0, \end{align*} so the positive coefficient is attached to $x$ and the negative coefficients are attached to $a,b,c$. Hence \begin{align*} x\in \operatorname{conv}\{x\}\cap \operatorname{conv}\{a,b,c\}, \end{align*} giving the Radon partition $\{x\}\sqcup\{a,b,c\}$. If the four points are the vertices $a,b,c,d$ of a convex quadrilateral in cyclic order, the diagonals $\overline{ac}$ and $\overline{bd}$ meet at a point $p$ in their interiors. Therefore there are numbers $0<t<1$ and $0<s<1$ such that \begin{align*} p=(1-t)a+tc \end{align*} and \begin{align*} p=(1-s)b+sd. \end{align*} Putting these two expressions for $p$ together gives \begin{align*} (1-t)a+tc=(1-s)b+sd, \end{align*} so \begin{align*} (1-t)a+tc-(1-s)b-sd=0. \end{align*} The coefficients also sum to zero: \begin{align*} (1-t)+t-(1-s)-s=1-1=0. \end{align*} The positive coefficients occur on $a,c$ and the negative coefficients occur on $b,d$, and the shared point is \begin{align*} p\in \operatorname{conv}\{a,c\}\cap \operatorname{conv}\{b,d\}. \end{align*} Thus the Radon partition is $\{a,c\}\sqcup\{b,d\}$. The two planar mechanisms are therefore containment of one point in a triangle and crossing of the two opposite-vertex segments. [/example] The planar Tverberg number for $r=3$ is \begin{align*} (3-1)(2+1)+1=7. \end{align*} Seven points must split into three parts whose convex hulls share a point, but the combinatorics of the partition can vary with the configuration. The Radon examples above show the two basic planar mechanisms, containment in a triangle and crossing of segments; a three-part Tverberg partition combines these mechanisms, so the next example records the typical shapes rather than a single canonical picture. [example: Tverberg Partitions Of Seven Points In The Plane] For $r=3$ and $d=2$, the affine Tverberg threshold is \begin{align*} (r-1)(d+1)+1=(3-1)(2+1)+1=2\cdot 3+1=7. \end{align*} Thus *Tverberg's theorem* says that every seven-point set in $\mathbb R^2$ has a partition into three nonempty blocks whose convex hulls share a point. One possible shape has block sizes $1,3,3$. Label the points $p,a,b,c,d,e,f$, and suppose $p$ lies in both triangles $\operatorname{conv}\{a,b,c\}$ and $\operatorname{conv}\{d,e,f\}$. Then there are coefficients $\alpha,\beta,\gamma\ge 0$ and $\lambda,\mu,\nu\ge 0$ with \begin{align*} \alpha+\beta+\gamma=1, \qquad \lambda+\mu+\nu=1, \end{align*} such that \begin{align*} p=\alpha a+\beta b+\gamma c \end{align*} and \begin{align*} p=\lambda d+\mu e+\nu f. \end{align*} The same point has the three convex-combination expressions \begin{align*} p=1\cdot p=\alpha a+\beta b+\gamma c=\lambda d+\mu e+\nu f. \end{align*} Therefore \begin{align*} p\in \operatorname{conv}\{p\}\cap \operatorname{conv}\{a,b,c\}\cap \operatorname{conv}\{d,e,f\}, \end{align*} so $\{p\}\sqcup\{a,b,c\}\sqcup\{d,e,f\}$ is a Tverberg partition. Another possible shape has block sizes $2,2,3$. Label the points $a,b,c,d,e,f,g$, and suppose a point $q$ lies on the two segments $\overline{ac}$ and $\overline{bd}$ and also in the triangle $\operatorname{conv}\{e,f,g\}$. Then there are numbers $0\le t,s\le 1$ and coefficients $\lambda,\mu,\nu\ge 0$ with \begin{align*} \lambda+\mu+\nu=1 \end{align*} such that \begin{align*} q=(1-t)a+tc, \qquad q=(1-s)b+sd, \qquad q=\lambda e+\mu f+\nu g. \end{align*} Hence \begin{align*} q\in \operatorname{conv}\{a,c\}\cap \operatorname{conv}\{b,d\}\cap \operatorname{conv}\{e,f,g\}, \end{align*} and the partition $\{a,c\}\sqcup\{b,d\}\sqcup\{e,f,g\}$ is a Tverberg partition. These two calculations show how a seven-point planar Tverberg partition can arise either from one point lying in two triangles or from two segments and a triangle sharing a common point. [/example] The affine proof uses convexity and linear separation. The topological version keeps the same partition question but replaces convex hulls of point sets by images of disjoint faces under a continuous map. ## Deleted Joins and the Configuration Space-Test Map Scheme How can a partition of vertices be encoded as a point of a topological space? The configuration space should remember $r$ pairwise disjoint faces of a simplex, because disjoint faces correspond to disjoint blocks of vertices. Using $K^r$ directly would allow two coordinates to lie in faces sharing vertices, and then an intersection of images would not encode a Tverberg partition of disjoint blocks. The test map therefore starts from a space where disjointness is built into the definition. [definition: Deleted Join] Let $K$ be a simplicial complex and let $r \ge 2$. The $r$-fold deleted join of $K$ is the subcomplex \begin{align*} K^{*r}_{\Delta} = \{\sigma_1 * \cdots * \sigma_r \in K^{*r} : \sigma_i \cap \sigma_j = \varnothing \text{ for } i \ne j\}. \end{align*} [/definition] A point of $K^{*r}_{\Delta}$ is a formal convex combination of points lying in $r$ disjoint faces, which is exactly the data needed to test common images. The next definition is needed because these $r$ faces are labelled only for bookkeeping, and the topology must remember that permuting the labels should not change the problem. [definition: Symmetric Group Action On The Deleted Join] Let $K$ be a simplicial complex and let $r \ge 2$. The symmetric group action on the deleted join is the map \begin{align*} S_r \times K^{*r}_{\Delta} \longrightarrow K^{*r}_{\Delta} \end{align*} defined by permuting the $r$ join factors: \begin{align*} \pi \cdot (x_1 * \cdots * x_r) = x_{\pi^{-1}(1)} * \cdots * x_{\pi^{-1}(r)}. \end{align*} [/definition] For each fixed $\pi \in S_r$, the associated self-map of $K^{*r}_{\Delta}$ is the corresponding factor-permutation map. The group action expresses that the labels on the $r$ parts are auxiliary. An obstruction to an equivariant map out of the deleted join will force a coincidence among the $r$ images. [definition: Test Representation] Let $r \ge 2$ and $d \ge 1$. The test representation for Tverberg problems is \begin{align*} W_r^{\oplus d} = \{(y_1, \dots, y_r) \in (\mathbb R^d)^r : y_1 + \cdots + y_r = 0\}, \end{align*} with $S_r$ acting by permuting the $r$ coordinates. [/definition] The diagonal has been removed by subtracting the average, so the origin in $W_r^{\oplus d}$ represents coincidence of the $r$ points. For the deleted-join model the join coefficients must also be recorded, so the actual test vector below uses $W_r^{\oplus(d+1)}$: one coordinate records the join weight and the remaining $d$ coordinates record the weighted image point. The next theorem is needed because it packages this observation into the standard configuration space-test map implication: if the desired intersection fails, an equivariant map to the test sphere must exist. [remark: Configuration Space-Test Map Method] Let $r \geq 2$ and $d \geq 1$ be integers. Let $K$ be a simplicial complex, let $|K|$ denote its geometric realization, and let $f: |K| \to \mathbb{R}^d$ be continuous. Suppose that for every collection of $r$ pairwise disjoint faces $\sigma_1,\dots,\sigma_r$ of $K$ one has \begin{align*} f(|\sigma_1|) \cap \cdots \cap f(|\sigma_r|) = \varnothing. \end{align*} Let \begin{align*} W_r := \left\{(a_1,\dots,a_r) \in \mathbb{R}^r : \sum_{j=1}^{r} a_j = 0\right\} \end{align*} with the natural coordinate-permutation action of $S_r$. Then there exists an $S_r$-equivariant continuous map \begin{align*} K^{*r}_{\Delta} \to S(W_r^{\oplus(d+1)}), \end{align*} where $K^{*r}_{\Delta}$ is the $r$-fold deleted join of $K$ and $S(W_r^{\oplus(d+1)})$ is the unit sphere in $W_r^{\oplus(d+1)}$. [/remark] The no-common-intersection hypothesis is exactly what makes the weighted test vector nonzero. The extra weight coordinate is essential: without it, a deleted-join point with a zero join coefficient would still appear to require a chosen point in the corresponding face, even though that point is not part of the join data. The hypothesis is also stronger than pairwise avoidance. For example, three subsets of the plane may meet pairwise while having empty triple intersection; the test map only detects the simultaneous equality forced by a zero vector, not pairwise intersections among some of the images. The principle therefore proves a conditional implication only. By itself it does not rule out counterexamples; it converts the geometric problem into the task of proving that the displayed equivariant map cannot exist. [example: Radon Through The Test Map] For $r=2$ and $K=\Delta^{d+1}$, write the vertices of $\Delta^{d+1}$ as $v_0,\dots,v_{d+1}$. A point of the two-fold deleted join has the form \begin{align*} \lambda_1 x_1 * \lambda_2 x_2, \end{align*} where $\lambda_1,\lambda_2\ge 0$, $\lambda_1+\lambda_2=1$, and $x_1,x_2$ lie in disjoint faces. Equivalently, each vertex $v_i$ may occur in the first factor, in the second factor, or in neither factor, but never in both. This gives the boundary of the crosspolytope with paired vertices $v_i^+$ and $v_i^-$, so the deleted join is homeomorphic to $S^{d+1}$; swapping the two join factors sends $v_i^+$ to $v_i^-$, which is the antipodal action in this sphere model. Assume that a continuous map $f:\Delta^{d+1}\to\mathbb R^d$ has no two disjoint faces with intersecting images. For a deleted-join point define \begin{align*} z_1=(\lambda_1,\lambda_1 f(x_1))\in\mathbb R^{d+1}. \end{align*} Also define \begin{align*} z_2=(\lambda_2,\lambda_2 f(x_2))\in\mathbb R^{d+1}. \end{align*} Subtracting the average gives the test vector \begin{align*} \Phi(\lambda_1x_1*\lambda_2x_2)=\left(z_1-\frac{z_1+z_2}{2},z_2-\frac{z_1+z_2}{2}\right). \end{align*} The same expression is \begin{align*} \Phi(\lambda_1x_1*\lambda_2x_2)=\left(\frac{z_1-z_2}{2},\frac{z_2-z_1}{2}\right)\in W_2^{\oplus(d+1)}. \end{align*} If $\Phi=0$, then both coordinates of the ordered pair are zero, so $z_1-z_2=0$ and hence $z_1=z_2$. Comparing first coordinates gives $\lambda_1=\lambda_2$, and together with $\lambda_1+\lambda_2=1$ this gives \begin{align*} \lambda_1=\lambda_2=\frac{1}{2}. \end{align*} Comparing the last $d$ coordinates of $z_1=z_2$ gives \begin{align*} \frac{1}{2}f(x_1)=\frac{1}{2}f(x_2). \end{align*} Multiplying by $2$ gives $f(x_1)=f(x_2)$, contradicting the assumption because $x_1$ and $x_2$ lie in disjoint faces. Thus $\Phi$ is never zero, and normalizing gives an antipodal map \begin{align*} S^{d+1}\longrightarrow S(W_2^{\oplus(d+1)})\cong S^d. \end{align*} The *Borsuk-Ulam theorem* forbids an antipodal map from $S^{d+1}$ to $S^d$. Therefore the assumed avoidance is impossible: some two disjoint faces of $\Delta^{d+1}$ have intersecting images, which is the topological Radon conclusion. [/example] The test-map proof of Radon is the prototype: construct the map that would exist if the desired intersection failed, then use an equivariant obstruction theorem to rule it out. ## Prime Powers and Topological Tverberg Theorems For which values of $r$ does the affine theorem remain true for continuous maps? The answer is governed by group actions: prime powers have enough equivariant obstruction theory, while non-prime-powers admit counterexamples in high dimensions. [definition: Topological Tverberg Property] Let $r \ge 2$ and $d \ge 1$. The pair $(r,d)$ has the topological Tverberg property if every continuous map \begin{align*} f: \Delta^{(r-1)(d+1)} \longrightarrow \mathbb R^d \end{align*} has $r$ pairwise disjoint faces $\sigma_1, \dots, \sigma_r$ such that \begin{align*} f(\sigma_1) \cap \cdots \cap f(\sigma_r) \ne \varnothing. \end{align*} [/definition] This property is the continuous analogue of Tverberg's theorem for the simplex with exactly $(r-1)(d+1)+1$ vertices. The next theorem is needed because it gives the positive range: prime powers are exactly the values of $r$ covered by the Borsuk-Ulam type obstruction developed in the course. [quotetheorem:6501] [citeproof:6501] The prime-power hypothesis is not a cosmetic feature of the proof. The obstruction used here lives in finite $p$-group equivariant topology, extending the index viewpoint of Chapter 6, and the argument depends on a transitive elementary abelian $p$-subgroup of $S_r$; such a subgroup exists for $r=p^k$ and not for a general composite $r$. The simplex dimension is also sharp in the same sense as affine Tverberg: if $\Delta^{(r-1)(d+1)-1}$ is used instead, the vertices of a $d$-simplex with $r-1$ labelled copies of each vertex give an affine map with no $r$ disjoint faces meeting, hence no topological theorem can hold at that lower dimension. The disjointness condition cannot be dropped either, since allowing repeated or overlapping faces would make the conclusion degenerate: every face intersects itself under any map. Finally, $d\ge 1$ excludes the zero-dimensional target, where the statement collapses to a counting assertion about maps to a point rather than the geometric Tverberg phenomenon. This theorem also does not say that non-prime-powers always fail in low dimensions. The known counterexamples require sufficiently high dimension; common formulations of the Frick-Mabillard-Wagner method give failures for non-prime-power $r$ in a high-dimensional range, often stated around $d\ge 3r$, with the original smallest $r=6$ example occurring in dimension $19$. Thus prime powers give a universal positive theorem, while non-prime-powers require separate high-dimensional constructions to show failure. The next theorem is needed because the failure of an equivariant obstruction is not by itself a geometric counterexample. A map from a deleted product to a sphere is only obstruction-theoretic data; the multiple Whitney trick says that, in a controlled PL and high-codimension setting, this data can be realised by removing all $r$-fold intersections. [remark: Mabillard-Wagner Multiple Whitney Trick External Input] Let $r \ge 2$, let $K$ be a finite simplicial complex of dimension $k$, and let $d$ satisfy \begin{align*} rd \ge (r+1)k+3. \end{align*} Write \begin{align*} K^{\times r}_{\Delta}=\{(x_1,\dots,x_r)\in K^r:x_i\in \sigma_i,\ \sigma_1,\dots,\sigma_r \text{ pairwise disjoint simplices of }K\}. \end{align*} If there exists an $S_r$-equivariant map \begin{align*} K^{\times r}_{\Delta}\longrightarrow S(W_r^{\oplus d}), \end{align*} then $K$ admits a PL map $g:K\to \mathbb R^d$ such that \begin{align*} g(\sigma_1)\cap\cdots\cap g(\sigma_r)=\varnothing \end{align*} for every $r$ pairwise disjoint simplices $\sigma_1,\dots,\sigma_r$ of $K$. [/remark] The course states this result as a geometric input rather than proving it. Its hypotheses are doing substantial work. The inequality $rd\ge (r+1)k+3$ is the codimension range in which the relevant Whitney disks can be chosen without creating uncontrolled new intersections; below that range, low-dimensional linking and intersection phenomena can obstruct the surgery. The PL and finite-complex assumptions give a combinatorial category where deleted products, general position, and Whitney moves are available. The equivariant-map hypothesis is not a conclusion about $K$ by itself; it is the obstruction-theoretic certificate that the algebraic $r$-fold intersection obstruction vanishes. The theorem also does not claim that every map can be repaired, only that some PL map $g$ with no global $r$-fold intersections exists under these hypotheses. The Mabillard-Wagner theorem explains how obstruction-theoretic data becomes geometric only in a controlled high-codimension PL range. To produce an actual counterexample to topological Tverberg, one still needs a source of equivariant maps for the relevant deleted products and a way to move from that high-codimension setting back to the Tverberg simplex. Ozaydin supplies the equivariant maps when $r$ is not a prime power, and the constraint method performs the dimension adjustment. The final theorem records the resulting failure of the topological Tverberg statement outside the prime-power range. [remark: Frick Counterexamples To Topological Tverberg External Input] If $r$ is not a prime power and $d$ lies in the standard high-dimensional counterexample range, then there exists a continuous map \begin{align*} f: \Delta^{(r-1)(d+1)} \longrightarrow \mathbb R^d \end{align*} with no $r$ pairwise disjoint faces whose images have a common point. [/remark] The counterexamples combine Ozaydin's existence of equivariant maps for non-prime-powers with the Mabillard-Wagner theorem, then use a constraint method to obtain maps at the Tverberg dimension. The condition that $r$ is not a prime power is essential to this construction: for prime powers the preceding theorem forces an $r$-fold point for every continuous map from the Tverberg simplex, so no such counterexample can exist. The high-dimensional condition is also a limitation of the machinery, and the precise numerical range depends on the formulation and improvements being invoked. It places the problem where the Mabillard-Wagner method applies after the constraint step; it does not settle the low-dimensional non-prime-power cases, many of which require separate arguments and may remain positive in small dimensions. Thus affine Tverberg remains true for every $r$, but topological Tverberg holds in full generality only in the prime-power range. [example: Why Non-Prime-Powers Are Different] Take $r=6$. Since \begin{align*} r-1=6-1=5, \end{align*} the affine Tverberg number is \begin{align*} (r-1)(d+1)+1=5(d+1)+1=5d+5+1=5d+6. \end{align*} Thus *Tverberg's theorem* says that every set of $5d+6$ points in $\mathbb R^d$ has a partition into six nonempty blocks whose convex hulls have a common point. The topological version uses the simplex \begin{align*} \Delta^{(r-1)(d+1)}=\Delta^{5(d+1)}=\Delta^{5d+5}, \end{align*} which has \begin{align*} (5d+5)+1=5d+6 \end{align*} vertices, matching the affine point count. The integer $6$ is not a prime power: its prime factorization is \begin{align*} 6=2\cdot 3, \end{align*} so it is neither $p^k$ for $p=2$ nor $p^k$ for $p=3$. Therefore the prime-power topological Tverberg theorem does not apply. The original smallest Frick counterexample for this value of $r$ occurs in dimension \begin{align*} d=19. \end{align*} For this dimension the Tverberg simplex is \begin{align*} \Delta^{5(d+1)}=\Delta^{5\cdot 20}=\Delta^{100}, \end{align*} and there is a continuous map \begin{align*} f:\Delta^{100}\longrightarrow \mathbb R^{19} \end{align*} with no six pairwise disjoint faces whose images share a common point. Thus the affine six-part intersection theorem still holds in every dimension, while the corresponding continuous statement fails at least in this high-dimensional non-prime-power case. [/example] This contrast is the main lesson of the chapter. Affine convexity supplies intersections by linear dependence and separation, while the topological theory supplies intersections exactly when equivariant obstructions prevent the deleted-join test map from landing in the sphere. After Tverberg-type results, the course shifts from intersection theorems to structural conditions on simplicial complexes and posets. Shellability and Cohen-Macaulayness explain when the combinatorial order of facets controls connectivity and homology in a way that fits the obstruction-theoretic themes developed earlier. # 9. Shellability, Cohen-Macaulay Complexes, and Posets Shellability is the point where the combinatorial ordering of facets begins to control topology. In Chapters 1 and 2, complexes were studied through links, joins, order complexes, homology, and connectivity; later chapters used those tools for equivariant obstructions. This chapter asks when a finite simplicial complex can be built one facet at a time so that every attachment is topologically transparent. The reward is a class of complexes whose homotopy type, homology, and enumerative data can often be read directly from an ordering. ## Building a Pure Complex One Facet at a Time The first problem is to decide what it should mean for a complex to be assembled without hidden topological accidents. If a new facet is attached along a scattered collection of faces, the topology can change in ways not visible from dimension alone. Shellability rules out this behaviour by requiring each new facet to meet the previous union along a controlled codimension-one part of its boundary. A shelling theory begins with complexes whose maximal faces all have the same dimension, since the attaching operation should have a fixed top-dimensional unit. This requirement is the first local regularity condition needed before a facet order can have a uniform meaning. [definition: Pure Simplicial Complex] A finite simplicial complex $K$ is pure of dimension $d$ if every facet of $K$ has dimension $d$. [/definition] Purity is a constraint on facets, not on all faces. It is strong enough to make every top-dimensional attachment comparable, while still allowing the lower-dimensional face poset to be complicated. The next example fixes the model case that any useful shelling definition should recognise. [example: Boundary Of A Simplex Is Pure] Let $K$ be the boundary complex of a $(d+1)$-simplex with vertex set $\{0,1,\dots,d+1\}$. The full simplex has vertex set of size $d+2$, so each facet of its boundary is obtained by removing one vertex: \begin{align*} F_i=\{0,1,\dots,d+1\}\setminus\{i\} \end{align*} for some $i\in\{0,1,\dots,d+1\}$. Since $F_i$ has $(d+2)-1=d+1$ vertices, its dimension is \begin{align*} \dim F_i=|F_i|-1=(d+1)-1=d. \end{align*} Thus every facet of $K$ has dimension $d$, so $K$ is pure of dimension $d$. This is the model pure complex built from $d$-simplices arranged as the boundary sphere of a simplex. [/example] The simplex boundary example suggests that the order of attachment matters as much as the list of facets. To formalise an orderly construction, we specify an order on the facets and ask every new facet to meet what has already been built in a pure boundary piece. [definition: Shelling Order] Let $K$ be a pure finite simplicial complex with facets $F_1,\dots,F_m$. The order $F_1,\dots,F_m$ is a shelling order if, for every $j>1$, the intersection $F_j \cap (F_1 \cup \cdots \cup F_{j-1})$ is a nonempty pure subcomplex of the boundary of $F_j$ of dimension $\dim F_j-1$. [/definition] The definition is geometric: it describes how each new simplex is glued to the partial complex. There is also a face-theoretic formulation used in many combinatorial proofs: for each $i<j$, there is some $k<j$ such that $F_i\cap F_j \subseteq F_k\cap F_j$ and $F_k\cap F_j$ is a codimension-one face of $F_j$. This turns the existence of a shelling order into the property of being shellable. [definition: Shellable Complex] A pure finite simplicial complex $K$ is shellable if its facets admit a shelling order. [/definition] Shellability is not a property of a single facet order until an order has been chosen. A complex may admit many shellings, and different shellings can expose different combinatorial statistics even though the underlying topology is fixed. Before introducing those statistics, it is useful to see the definition work in the basic sphere. [example: Shelling The Boundary Of A Simplex] Let $K$ be the boundary of a $(d+1)$-simplex, with facets \begin{align*} F_i=\{0,\dots,d+1\}\setminus\{i\} \end{align*} for $0\le i\le d+1$. Order the facets as $F_0,F_1,\dots,F_{d+1}$. Fix $j>0$ and let $0\le i<j$. Since $i\ne j$, the intersection of the new facet $F_j$ with the earlier facet $F_i$ is \begin{align*} F_j\cap F_i=\bigl(\{0,\dots,d+1\}\setminus\{j\}\bigr)\cap\bigl(\{0,\dots,d+1\}\setminus\{i\}\bigr). \end{align*} Removing both excluded vertices gives \begin{align*} F_j\cap F_i=\{0,\dots,d+1\}\setminus\{i,j\}. \end{align*} Because $F_j=\{0,\dots,d+1\}\setminus\{j\}$ and $i\in F_j$, this is the same face as \begin{align*} F_j\cap F_i=F_j\setminus\{i\}. \end{align*} Therefore the part of $F_j$ already present in the earlier union is \begin{align*} F_j\cap (F_0\cup\cdots\cup F_{j-1})=\bigcup_{i=0}^{j-1}(F_j\setminus\{i\}). \end{align*} Each face $F_j\setminus\{i\}$ has \begin{align*} |F_j\setminus\{i\}|=(d+1)-1=d \end{align*} vertices, so \begin{align*} \dim(F_j\setminus\{i\})=d-1. \end{align*} Thus these are codimension-one faces of the $d$-simplex $F_j$. The intersection is nonempty because $j>0$, and it is pure of dimension $d-1$ because it is generated by the $(d-1)$-faces $F_j\setminus\{0\},\dots,F_j\setminus\{j-1\}$. Hence every new facet meets the previous union in a nonempty pure $(d-1)$-dimensional subcomplex of its boundary, so $F_0,F_1,\dots,F_{d+1}$ is a shelling order of the boundary complex. [/example] This shelling introduces new faces in controlled batches. Once a shelling order is fixed, each facet has a smallest face that did not appear in the earlier union; recording it identifies the whole interval of faces born at that step. This motivates the restriction face. [definition: Restriction Face] Let $F_1,\dots,F_m$ be a shelling order of a pure finite simplicial complex $K$. For each $j$, the restriction face $R(F_j)$ is the unique minimal face of $F_j$ that is not contained in $F_1 \cup \cdots \cup F_{j-1}$, with $R(F_1)=\varnothing$. [/definition] The restriction face partitions the face set: a face $G$ is introduced at step $j$ exactly when $R(F_j) \subseteq G \subseteq F_j$. This interval decomposition converts a topological construction into enumerative data. We need a statistic that records these birth intervals by the size of their minimal new face, which leads to the shelling interpretation of the $h$-vector. [definition: H-Vector Of A Shelling] Let $K$ be a pure $(d-1)$-dimensional shellable complex with shelling order $F_1,\dots,F_m$. Its $h$-vector with respect to the shelling is $(h_0,\dots,h_d)$, where $h_i$ is the number of facets $F_j$ satisfying $|R(F_j)|=i$. [/definition] This definition depends on a chosen shelling at first sight, while the usual $h$-vector is defined from the $f$-vector of the complex. We need to resolve this tension: the shelling count must agree with the intrinsic enumerative invariant before shellings can be used reliably for enumeration. [quotetheorem:6504] [citeproof:6504] The hypotheses here are doing real work. Purity fixes a single value of $d$, so the usual $h$-vector relation compares face numbers against one common top dimension; for a disjoint union of an edge and an isolated vertex there is no single facet size from which these shelling intervals could produce one coherent $h$-vector in this form. Shellability is also essential, because without the interval partition by restriction faces there need not be a unique birth step for each face. The theorem does not say that every pure complex has a nonnegative $h$-vector; rather, it explains why shellable complexes do, and this enumerative control is the input for the topological consequences that follow. ## Homotopy Consequences Of Shellability The next question is what topological information the shelling order forces. Attaching a simplex along a contractible part of its boundary does not create a new sphere, while attaching it along the whole boundary creates one. Shellings reduce the homotopy type to this dichotomy at every step. The restriction face tells us whether a facet attachment merely fills in a ball or closes a sphere. If the new facet is attached along its entire boundary, a top-dimensional sphere appears; otherwise the attachment changes the complex without changing its homotopy type. [quotetheorem:6505] [citeproof:6505] Each hypothesis prevents a specific failure. Finiteness lets the induction run over a finite list of facets; for infinite locally finite shellings, additional topology is needed to control limiting behaviour. Purity is needed because otherwise attachments in different dimensions can create homology in more than one degree, as in a complex formed from a triangle together with a pendant edge not contained in any triangle. Shellability is the condition that makes every attaching intersection a ball or a sphere boundary; a pure complex obtained by gluing triangles in a cycle with a missing edge order obstruction can have lower-dimensional homology not accounted for by full-boundary facets. The theorem does not say every shellable complex is a sphere. It says the only possible homotopy in the top dimension is free and generated by the facets that close off an entire boundary. The boundary of a simplex is the smallest illustration of the full-boundary event. [example: Boundary Of A Simplex Gives One Sphere] For the shelling order $F_0,F_1,\dots,F_{d+1}$ of the boundary of the $(d+1)$-simplex, the attaching subcomplex for $F_j$ with $j>0$ is \begin{align*} F_j\cap(F_0\cup\cdots\cup F_{j-1})=\bigcup_{i=0}^{j-1}(F_j\setminus\{i\}). \end{align*} If $1\le j\le d$, then $d+1\in F_j$, so the boundary face $F_j\setminus\{d+1\}$ is a codimension-one face of $F_j$. It is not one of the faces $F_j\setminus\{0\},\dots,F_j\setminus\{j-1\}$, and it is not contained in any of them: for each $i<j$, the face $F_j\setminus\{d+1\}$ contains $i$, while $F_j\setminus\{i\}$ does not. Hence the attaching subcomplex is a proper nonempty part of $\partial F_j$ for every $1\le j\le d$. For the last facet, $F_{d+1}=\{0,1,\dots,d\}$, and its boundary is the union of its codimension-one faces: \begin{align*} \partial F_{d+1}=\bigcup_{i=0}^{d}(F_{d+1}\setminus\{i\}). \end{align*} The attaching subcomplex at the last step is \begin{align*} F_{d+1}\cap(F_0\cup\cdots\cup F_d)=\bigcup_{i=0}^{d}(F_{d+1}\setminus\{i\})=\partial F_{d+1}. \end{align*} Thus exactly one facet is attached along its whole boundary, namely $F_{d+1}$. By *[Shellable Complexes Are Wedges Of Spheres](/theorems/6505)*, the boundary complex is homotopy equivalent to a wedge with one $d$-sphere, so it is homotopy equivalent to $S^d$. This agrees with the usual geometric realization of the boundary of a simplex. [/example] The example shows how the top-dimensional sphere is born at the final full-boundary attachment. This motivates a homology theorem: since a wedge of $d$-spheres has reduced homology only in degree $d$, the same shelling analysis should give a precise vanishing statement. [quotetheorem:6506] [citeproof:6506] The field $k$ is arbitrary because the wedge decomposition has torsion-free cellular homology, so no coefficient-dependent phenomenon is being hidden. The dimension and purity hypotheses are again necessary: a nonpure complex such as a triangle with an extra isolated edge can have reduced homology in a degree below the largest facet dimension. Shellability is stronger than the conclusion; the theorem does not classify all complexes with vanishing lower homology, since many Cohen-Macaulay complexes are not known from a shelling. This homological conclusion is a central reason shellability appears throughout topological combinatorics, and it prepares the local link condition used in Cohen-Macaulayness. ## Shellable Posets And Order Complexes Many complexes in combinatorics are not presented by listing facets. They arise as order complexes of partially ordered sets, where faces are chains. The problem becomes: how can a poset carry enough order-theoretic structure to make its order complex shellable? The translation from posets to simplicial complexes sends comparable lists to simplices. This lets us use shellability for objects such as Boolean and partition lattices, but first the construction has to be made explicit. [definition: Order Complex] Let $P$ be a finite poset. The order complex $\Delta(P)$ is the simplicial complex whose vertices are the elements of $P$ and whose faces are the finite chains $x_0<x_1<\cdots<x_r$ in $P$. [/definition] Order complexes translate interval structure in a poset into links and subcomplexes. To obtain a pure complex, maximal chains should have a common length. This motivates the rank condition on the poset. [definition: Graded Poset] A finite poset $P$ is graded if there is a rank function $\rho:P\to \mathbb N$ such that $y$ covers $x$ implies $\rho(y)=\rho(x)+1$. [/definition] For a bounded graded poset, including both the minimum and maximum would add cone points to the order complex and erase the internal topology. The useful object is therefore obtained by deleting those two extremal elements before forming the order complex. This motivates the proper part. [definition: Proper Part Of A Bounded Poset] Let $P$ be a finite poset with minimum element $\hat 0$ and maximum element $\hat 1$. The proper part of $P$ is $\overline{P}=P\setminus\{\hat 0,\hat 1\}$. [/definition] The order complex $\Delta(\overline{P})$ is the object whose topology measures the internal structure of $P$. Directly ordering all maximal chains can be unwieldy, so we seek labels on cover relations that force the required shelling order. This motivates edge labellings. [definition: Edge Labelling] Let $P$ be a finite graded poset. An edge labelling of $P$ is a map $\lambda$ from the cover relations $x\lessdot y$ of $P$ to a totally ordered set $\Lambda$. [/definition] A labelling turns each maximal chain in an interval into a word. Lexicographic order can shell the order complex only if every interval has a preferred word that behaves well under restriction. This motivates the EL condition. [definition: EL-Labelling] Let $P$ be a finite graded poset. An edge labelling $\lambda$ is an EL-labelling if, in every interval $[x,y]$, there is a unique maximal chain whose label sequence is strictly increasing, and this increasing chain is lexicographically first among all maximal chains in $[x,y]$. [/definition] The EL condition is local on intervals, but its purpose is global: it should order all maximal chains in the proper part of the poset. We need a mechanism that turns interval-wise increasing chains into a shelling order for the whole order complex. [quotetheorem:6507] [citeproof:6507] Bounded gradedness ensures that all maximal chains in the proper part have the same length, so $\Delta(\overline{P})$ is pure and the shelling definition applies. If the poset is not graded, maximal chains can have different lengths, giving an order complex with facets of different dimensions. The EL condition is also essential: an arbitrary edge labelling can put several increasing chains in one interval, leaving no canonical earlier comparison chain for a descent. The theorem does not say every shellable poset order complex comes from an EL-labelling; EL-shellability is a checkable sufficient condition. This theorem is the main working tool for posets in the course, and the Boolean lattice gives the cleanest test case because its cover relations add one element at a time. [example: EL-Labelling Of The Boolean Lattice] Let $B_n$ be the Boolean lattice of subsets of $[n]=\{1,\dots,n\}$ ordered by inclusion. A cover relation is exactly a pair \begin{align*} S\lessdot S\cup\{i\} \end{align*} where $i\notin S$, because there is no subset strictly between $S$ and $S\cup\{i\}$. Label this cover relation by $i$. Fix an interval $[S,T]$ in $B_n$. Write \begin{align*} T\setminus S=\{a_1<a_2<\cdots<a_r\}. \end{align*} A maximal chain from $S$ to $T$ has the form \begin{align*} S=S_0\lessdot S_1\lessdot \cdots \lessdot S_r=T, \end{align*} and each step adds one element of $T\setminus S$, so there is a unique ordering $b_1,\dots,b_r$ of $T\setminus S$ such that \begin{align*} S_q=S\cup\{b_1,\dots,b_q\} \end{align*} for every $0\le q\le r$. The label word of this chain is therefore \begin{align*} (b_1,b_2,\dots,b_r). \end{align*} The label word is strictly increasing exactly when \begin{align*} b_1<b_2<\cdots<b_r. \end{align*} Since $\{b_1,\dots,b_r\}=T\setminus S=\{a_1,\dots,a_r\}$ and the $a_q$ are listed in increasing order, this forces \begin{align*} (b_1,\dots,b_r)=(a_1,\dots,a_r). \end{align*} Thus the unique increasing maximal chain is \begin{align*} S\lessdot S\cup\{a_1\}\lessdot S\cup\{a_1,a_2\}\lessdot\cdots\lessdot S\cup\{a_1,\dots,a_r\}=T. \end{align*} It is lexicographically first because any other ordering differs from $(a_1,\dots,a_r)$ at some first position $q$, where it has not chosen the smallest remaining element $a_q$ and hence has $b_q>a_q$. Therefore the labelling satisfies the EL condition on every interval of $B_n$. [/example] The example verifies the hypotheses of the EL theorem for an important family of lattices. To make the conclusion available for later arguments, we record the shellability of Boolean lattices as a named theorem. [quotetheorem:6508] [citeproof:6508] The condition $n\ge 1$ gives a bounded graded lattice with well-defined proper part; for very small $n$, the proper part may be empty, which is still shellable by the standard convention. The specific labels matter: if all covers were assigned the same label, every maximal chain in a nontrivial interval would be weakly indistinguishable and uniqueness of the increasing chain would fail. The theorem does not compute the homotopy type by itself, but it gives the shelling certificate needed to apply the homology results above. The Boolean lattice is the model case where labels record added elements. The partition lattice is more intricate because covers merge blocks rather than add single elements, so shellability requires a labelling that controls merger order. [quotetheorem:6509] [citeproof:6509] The theorem relies on the refinement order and on the specific least-element merger labels; a vague labelling that only records that two blocks were merged would not distinguish enough chains to force uniqueness. The bounded graded lattice structure is also necessary for the proper part to have facets of common dimension. The theorem does not give a convenient closed form for every shelling statistic of $\Pi_n$; its role here is to certify shellability and hence top-dimensional homology concentration. Some posets require an even more flexible labelling, because the correct interval order depends on the chain used to reach that interval. [definition: CL-Labelling] Let $P$ be a finite bounded graded poset and let $\Lambda$ be a totally ordered set. A rooted cover relation is a pair consisting of a cover relation $x\lessdot y$ and a maximal chain, called the root, from $\hat 0$ to $x$. A CL-labelling is a map from the set of rooted cover relations of $P$ to $\Lambda$ such that, in every rooted interval, there is a unique increasing maximal chain and it is lexicographically first among all maximal chains in that rooted interval. [/definition] CL-labellings generalise EL-labellings and still aim to produce shellings of order complexes. They are useful for recursive posets where the initial segment of a maximal chain changes the correct ordering inside a later interval. This motivates the parallel shellability theorem for CL-labellings. [quotetheorem:6510] [citeproof:6510] The rooted hypothesis is essential: in recursive examples, the same interval can require different preferred chains depending on the lower chain used to reach it, so an ordinary edge label cannot always encode the comparison facet. Bounded gradedness again supplies purity of the proper part; without it the codimension-one intersection condition need not even have a uniform dimension. The theorem does not imply that CL-labelled posets are EL-labelled, only that the more flexible rooted data still produce a shelling. The hierarchy is therefore: EL-labellings are easier to check, CL-labellings are more flexible, and both serve the same topological purpose. ## Cohen-Macaulay Complexes As A Topological Condition Shellability gives a strong combinatorial certificate, but many complexes have good homology without an evident shelling order. The next problem is to name the homological condition that shellability implies and that commutative algebra detects. This is the Cohen-Macaulay condition. The homology theorem for shellable complexes concerned the whole complex. A stronger and more stable condition asks for the same lower-degree vanishing in every link, since links describe the local topology around faces. [definition: Cohen-Macaulay Simplicial Complex Over A Field] Let $K$ be a finite simplicial complex and let $k$ be a field. The complex $K$ is Cohen-Macaulay over $k$ if, for every face $\sigma \in K$, including $\sigma=\varnothing$, the reduced homology of the link satisfies $\tilde H_i(\operatorname{lk}_K(\sigma);k)=0$ for all $i<\dim \operatorname{lk}_K(\sigma)$. [/definition] The definition asks every local piece of the complex to have homology concentrated in top degree. Taking $\sigma=\varnothing$ recovers the same vanishing condition for the whole complex, while nonempty faces impose local vanishing around each simplex. Shellable spheres and balls provide the geometric examples to keep in mind. [example: Spheres And Balls From Shellings] Let $K$ be a shellable triangulated $d$-sphere or $d$-ball, and let $\sigma\in K$ have dimension $r$, so $|\sigma|=r+1$. A facet of $\operatorname{lk}_K(\sigma)$ is obtained from a $d$-dimensional facet of $K$ containing $\sigma$ by deleting the vertices of $\sigma$. Such a remaining face has \begin{align*} (d+1)-(r+1)=d-r \end{align*} vertices, hence dimension \begin{align*} (d-r)-1=d-r-1. \end{align*} Thus every face link has the expected top dimension $d-r-1$. For a shellable triangulated sphere, the link of each face is again a shellable sphere or shellable ball; for a shellable triangulated ball, the same statement holds, with interior faces giving sphere links and boundary faces giving ball links. Therefore each link $L=\operatorname{lk}_K(\sigma)$ is a pure shellable complex. If $\dim L=\ell$, then *Homology Of A Shellable Pure Complex* gives \begin{align*} \tilde H_i(L;k)=0 \qquad \text{for every } i<\ell \end{align*} over any field $k$. Since this is exactly the required vanishing for every face link, shellable triangulated spheres and shellable triangulated balls are Cohen-Macaulay over every field. [/example] The example indicates the general mechanism: shellability passes to links, and the homology theorem can then be applied locally. This motivates the theorem that every pure shellable complex satisfies the Cohen-Macaulay link condition over each field. [quotetheorem:6511] [citeproof:6511] Purity is needed because the Cohen-Macaulay condition forces a uniform local dimension behaviour; a nonpure complex with a dangling lower-dimensional facet can have a link whose homology vanishing is measured against the wrong local dimension. Shellability is the certificate that links inherit shellings, and without it the local vanishing condition may fail even when the whole complex has simple homology. The theorem does not give a converse: Cohen-Macaulayness is homological, while shellability asks for a very particular combinatorial construction. This distinction matters because algebraic methods can prove Cohen-Macaulayness even when no shelling is known. The central algebraic test is Reisner's criterion. Here the algebraic object attached to $K$ is the Stanley-Reisner ring. If $V(K)$ is the vertex set and $S=k[x_v:v\in V(K)]$, let $I_K\subset S$ be the ideal generated by squarefree monomials $\prod_{v\in F}x_v$ for finite sets $F\subset V(K)$ that are not faces of $K$. Then \begin{align*} k[K]=S/I_K \end{align*} is the Stanley-Reisner ring, also called the face ring, of $K$ over $k$. The theorem below is the bridge between this algebraic object and the link-homology condition above. It is needed because the phrase "Cohen-Macaulay" now has two faces: one from commutative algebra for the face ring, and one from topology for links. Reisner's criterion says these viewpoints agree for finite simplicial complexes over a field. [remark: Reisner Criterion External Input] Let $K$ be a finite simplicial complex and let $k$ be a field. The Stanley-Reisner ring $k[K]$ is Cohen-Macaulay if and only if, for every face $\sigma\in K$ including $\sigma=\varnothing$, the reduced homology groups satisfy $\tilde H_i(\operatorname{lk}_K(\sigma);k)=0$ for all $i<\dim \operatorname{lk}_K(\sigma)$. [/remark] Reisner's criterion is stated here as a bridge theorem rather than proved in the course. Its proof belongs to combinatorial commutative algebra: it relates local cohomology of the Stanley-Reisner ring to reduced homology of links. The following explanation records why this algebraic statement belongs in a course organised around topology. [explanation: Why Cohen-Macaulayness Belongs In Topological Combinatorics] Cohen-Macaulayness packages a topological vanishing condition in a form that algebra can detect. For a pure complex, it says not only that the whole space has no lower-dimensional homology, but also that every link has the same kind of vanishing. This local requirement is what makes the condition stable under many constructions used in combinatorics. From the combinatorial side, shellings and EL-labellings provide concrete certificates. From the algebraic side, the Stanley-Reisner ring and Reisner's criterion provide structural tests. The course uses both languages because many examples arise first as posets or complexes, while their strongest consequences are often phrased as homological vanishing. [/explanation] This perspective returns us to the Boolean lattice. Its shellability was proved by an explicit EL-labelling, so it supplies a compact example where poset labels, shellability, and Cohen-Macaulayness all meet. [example: Boolean Lattice As A Cohen-Macaulay Poset] By *Boolean Lattices Are Shellable*, the Boolean lattice $B_n$ admits an EL-labelling, so $\Delta(\overline{B_n})$ is shellable. Applying *[Shellable Complexes Are Cohen-Macaulay](/theorems/6511)* to this shellable order complex shows that $\Delta(\overline{B_n})$ is Cohen-Macaulay over every field. Concretely, let \begin{align*} C:\quad S_1\subset S_2\subset \cdots \subset S_r \end{align*} be a chain in $\overline{B_n}=B_n\setminus\{\varnothing,[n]\}$. A simplex in $\operatorname{lk}_{\Delta(\overline{B_n})}(C)$ is a chain of subsets that can be inserted into $C$, so its vertices lie in the open Boolean intervals \begin{align*} (\varnothing,S_1),\quad (S_1,S_2),\quad \dots,\quad (S_r,[n]). \end{align*} For each interval $[A,B]$, the map \begin{align*} U\longmapsto U\setminus A \end{align*} is an order-preserving bijection from $[A,B]$ to the Boolean lattice on $B\setminus A$, because \begin{align*} A\subseteq U\subseteq B \quad\Longleftrightarrow\quad \varnothing\subseteq U\setminus A\subseteq B\setminus A. \end{align*} Thus every interval appearing in the link is again Boolean. The link is therefore built from order complexes of proper parts of Boolean intervals, and the Cohen-Macaulay conclusion says precisely that, for every field $k$, \begin{align*} \tilde H_i\bigl(\operatorname{lk}_{\Delta(\overline{B_n})}(C);k\bigr)=0 \qquad\text{for all } i<\dim \operatorname{lk}_{\Delta(\overline{B_n})}(C). \end{align*} So the Boolean lattice is Cohen-Macaulay as a poset: every chain has a link whose reduced homology is concentrated in top degree. [/example] The chapter has moved from a facet-by-facet construction to poset labellings and then to a homological condition on all links. This progression is typical in topological combinatorics: a combinatorial certificate gives a topological conclusion, and the topological conclusion is then recognised as an instance of a broader algebraic condition. The final chapter collects the recurring themes of the course into a broader landscape of applications and open directions. By now the method is familiar: encode combinatorics in a complex, extract a topological invariant, and interpret the resulting obstruction as a concrete combinatorial conclusion. # 10. Applications and Further Directions This final chapter gathers applications and further directions from the course, returning to graph coloring, nerves, convexity, and equivariant obstructions developed in the earlier chapters. The common pattern is now familiar: translate a combinatorial question into a statement about a simplicial complex, compute enough topology of that complex, and convert the resulting obstruction back into a graph-colouring, convexity, or intersection theorem. The chapter assumes the earlier material on simplicial complexes, connectivity, nerves, equivariant maps, and Borsuk--Ulam type obstructions, and it shows how those tools function beyond the central Kneser graph theorem. ## Graph Coloring Beyond Kneser Graphs The Kneser graph theorem is the model example: a graph coloring problem becomes the nonexistence of an equivariant map. A natural question is how much of this mechanism survives for arbitrary graphs. The answer is that one attaches a space to a graph whose topology constrains colorings, and different choices of space remember different kinds of graph-theoretic information. [remark: Neighborhood Complex Recall] Let $G$ be a finite simple loopless graph. The neighborhood complex $N(G)$ is the simplicial complex whose vertices are the vertices of $G$, and whose simplices are the finite sets $S \subset V(G)$ for which there exists a vertex $v \in V(G)$ adjacent to every vertex in $S$. [/remark] The neighborhood complex records common-neighbor structure, so it is tied directly to proper colorings: a coloring $G \to K_m$ induces a simplicial map $N(G) \to N(K_m)$. The target $N(K_m)$ has the homotopy type of a sphere of dimension $m-2$, which turns a coloring into a map to a sphere. This raises the central obstruction question for this section: if $N(G)$ is too highly connected, can such a map exist? [quotetheorem:6513] [citeproof:6513] This bound generalizes the topological lower bound used in Lovasz's proof of Kneser's conjecture. The hypothesis that $N(G)$ is $k$-connected is doing real work: mere nonemptiness of the neighborhood complex gives no obstruction beyond excluding isolated-vertex pathologies, and disconnected neighborhood complexes cannot force more than the first few chromatic lower bounds. For instance, bipartite graphs may have large common-neighbor structure locally, but their color classes give a genuine two-coloring, so any topological complex attached to coloring must fail to carry the connectivity needed for a three-color obstruction. Thus the theorem is not a universal chromatic formula; it is a test for whether the common-neighbor complex has enough global connectivity to prevent a low-color cover. It is often not sharp for an arbitrary graph, but it detects coloring obstructions invisible to clique number. The Petersen graph is the smallest familiar place where the Kneser graph calculation makes this obstruction concrete. [example: Petersen Graph As A Kneser Graph] The Petersen graph is $KG(5,2)$: its vertices are the $2$-element subsets of $\{1,2,3,4,5\}$, and two vertices are adjacent exactly when the corresponding subsets are disjoint. For instance, $\{1,2\}$ is adjacent to $\{3,4\}$ because $\{1,2\}\cap\{3,4\}=\varnothing$, while $\{1,2\}$ is not adjacent to $\{2,3\}$ because $\{1,2\}\cap\{2,3\}=\{2\}$. By *Lovasz's Kneser formula*, the chromatic number of a Kneser graph is \begin{align*} \chi(KG(n,k))=n-2k+2. \end{align*} Substituting $n=5$ and $k=2$ gives \begin{align*} \chi(KG(5,2))=5-2\cdot 2+2. \end{align*} Since $2\cdot 2=4$, this becomes \begin{align*} \chi(KG(5,2))=5-4+2. \end{align*} Since $5-4=1$, we get \begin{align*} \chi(KG(5,2))=1+2=3. \end{align*} Thus the Petersen graph is not $2$-colorable, but it is $3$-colorable. Topologically, a hypothetical $2$-coloring would be a graph homomorphism $KG(5,2)\to K_2$. The graph-complex construction used in Lovasz's proof turns such a homomorphism into an equivariant map to $S^0$. The Borsuk--Ulam obstruction for the Kneser complex rules out that equivariant map, so the topological contradiction is exactly the obstruction to a $2$-coloring. [/example] The Petersen example shows how much mileage one gets from a graph complex tailored to colorings. It also shows a limitation: common-neighbor information is only one way to encode coloring data. To capture parity phenomena and graph homomorphism functoriality more systematically, the next construction replaces common neighborhoods by a free involutive complex built from complete bipartite subgraphs. [remark: Box Complex Recall] Let $G$ be a finite simple loopless graph. In this chapter, the box complex $B(G)$ is the order complex of the poset of ordered pairs $(A,B)$ such that $A,B\subset V(G)$ are nonempty, disjoint, and every vertex of $A$ is adjacent to every vertex of $B$. The order relation is coordinatewise inclusion, and the involution $B(G)\to B(G)$ is induced by $(A,B)\mapsto (B,A)$. [/remark] Other standard box complexes differ by harmless choices about empty coordinates or barycentric subdivision, but this model is fixed for the notes. Its main role is functorial: a graph homomorphism $G \to H$ induces a $\mathbb Z/2\mathbb Z$-map $B(G) \to B(H)$. This motivates the following obstruction theorem, because a proper $m$-coloring is exactly a homomorphism to $K_m$, and $B(K_m)$ is $\mathbb Z/2\mathbb Z$-homotopy equivalent to $S^{m-2}$ with the antipodal action. The theorem isolates the reusable conclusion: if the required equivariant map to that sphere cannot exist, then the coloring cannot exist either. [quotetheorem:6514] [citeproof:6514] The theorem packages a familiar parity obstruction in topological form, but its hypotheses should be read carefully. The graph is assumed finite, simple, and loopless so that proper colorings are the same as graph homomorphisms to $K_m$, and so that the coordinate-swap action on the ordered-pair box complex is free. Allowing loops would break this comparison with loopless complete graphs, while allowing fixed ordered pairs would break the antipodal model for the target. The condition $m\ge 2$ is also structural: $B(K_m)$ is compared with the ordinary sphere $S^{m-2}$, so the statement is not a one-colour obstruction. For example, an edgeless graph has $\chi(G)=1$ and $B(G)=\varnothing$ in the present model, so trying to read a meaningful $S^{-1}$ obstruction from the theorem would be the wrong framework. Within those hypotheses, the theorem proves a lower bound only when the equivariant index of $B(G)$ is high enough; if $B(G)$ admits an equivariant map to $S^{m-2}$, the theorem says nothing about whether an $m$-coloring actually exists. Complete bipartite graphs illustrate the limitation in the opposite direction: they have many edges, but they are two-colorable, and their box complexes do not carry an obstruction to mapping toward $S^0$. Odd cycles are the first case where the topology detects the exact failure of two-colorability. [example: Odd Cycle Obstruction] Let $G=C_{2r+1}$ have cyclically ordered vertices $v_0,\dots,v_{2r}$, with indices read modulo $2r+1$. In the box-complex poset, the element \begin{align*} T_i=(\{v_i\},\{v_{i-1},v_{i+1}\}) \end{align*} is allowed because $v_i$ is adjacent in $C_{2r+1}$ to both $v_{i-1}$ and $v_{i+1}$. It contains exactly the two singleton ordered edge pairs \begin{align*} L_i=(\{v_i\},\{v_{i-1}\}) \quad\text{and}\quad R_i=(\{v_i\},\{v_{i+1}\}), \end{align*} since \begin{align*} \{v_i\}\subseteq \{v_i\}, \qquad \{v_{i-1}\}\subseteq \{v_{i-1},v_{i+1}\}, \qquad \{v_{i+1}\}\subseteq \{v_{i-1},v_{i+1}\}. \end{align*} Thus the order complex contains the two edges $L_i<T_i$ and $R_i<T_i$. The singleton ordered edge pairs alone are not comparable to one another, because neither $\{v_{i-1}\}\subseteq \{v_{i+1}\}$ nor $\{v_{i+1}\}\subseteq \{v_{i-1}\}$ holds. Now include the swapped elements \begin{align*} T_i'=(\{v_{i-1},v_{i+1}\},\{v_i\}), \end{align*} with lower faces \begin{align*} L_i'=(\{v_{i-1}\},\{v_i\}) \quad\text{and}\quad R_i'=(\{v_{i+1}\},\{v_i\}). \end{align*} As $i$ runs modulo $2r+1$, the endpoint $R_i=(\{v_i\},\{v_{i+1}\})$ is the same poset vertex as $L_{i+1}'=(\{v_i\},\{v_{i+1}\})$, and the endpoint $L_i=(\{v_i\},\{v_{i-1}\})$ is the same poset vertex as $R_{i-1}'=(\{v_i\},\{v_{i-1}\})$. Therefore the intervals \begin{align*} L_i<T_i>R_i \end{align*} and their coordinate-swapped partners glue end-to-end into a polygonal $1$-cycle. It has $2(2r+1)$ top vertices $T_i,T_i'$ and $2(2r+1)$ singleton ordered-edge vertices, so it is a subcomplex homeomorphic to $S^1$. The coordinate-swap involution sends \begin{align*} (A,B)\longmapsto (B,A), \end{align*} so it interchanges $T_i$ with $T_i'$ and sends each singleton ordered edge $(\{v_i\},\{v_{i+1}\})$ to $(\{v_{i+1}\},\{v_i\})$. No vertex of this cycle is fixed, because an ordered pair would be fixed only if $A=B$, while the defining pairs have disjoint nonempty coordinates. On this embedded circle the involution is the half-turn symmetry, hence there is no equivariant map from this circle to $S^0$. Since the circle is an invariant subcomplex of $B(C_{2r+1})$, an equivariant map $B(C_{2r+1})\to S^0$ would restrict to an equivariant map $S^1\to S^0$, which is impossible. A two-coloring of $C_{2r+1}$ would be a graph homomorphism $C_{2r+1}\to K_2$. By functoriality of the box complex, it would induce a $\mathbb Z/2\mathbb Z$-equivariant map \begin{align*} B(C_{2r+1})\longrightarrow B(K_2). \end{align*} The complex $B(K_2)$ consists of the two ordered pairs $(\{1\},\{2\})$ and $(\{2\},\{1\})$, exchanged by the involution, so $B(K_2)\cong S^0$ with the antipodal action. This would give the forbidden equivariant map $B(C_{2r+1})\to S^0$. Therefore $C_{2r+1}$ is not two-colorable, and $\chi(C_{2r+1})\ge 3$. [/example] The box complex treats graph homomorphisms functorially, but it compresses the whole homomorphism set into a single equivariant space. This compression loses information about how different homomorphisms sit next to one another: two graphs may have box complexes with the same relevant index while the actual set of colorings from a test graph behaves very differently. A richer question asks what the space of all homomorphisms from a fixed test graph into $G$ looks like. This leads to Hom complexes, which refine the obstruction by varying the source graph. [definition: Hom Complex] For finite graphs $T$ and $G$, the Hom complex $\operatorname{Hom}(T,G)$ is the polyhedral complex whose cells are functions \begin{align*} \eta:V(T)\to 2^{V(G)}\setminus\{\varnothing\} \end{align*} such that for every edge $tt'\in E(T)$ and every pair $a\in \eta(t)$, $a'\in \eta(t')$, the pair $aa'$ is an edge of $G$. [/definition] This construction turns graph homomorphism sets into spaces. The Babson--Kozlov program uses these spaces to connect graph coloring, test graphs, and equivariant topology. [remark: Babson Kozlov Direction] A graph $T$ is called a test graph when high connectivity of $\operatorname{Hom}(T,G)$ forces strong lower bounds on $\chi(G)$. Odd cycles are central examples in the Babson--Kozlov theory. This gives a conceptual extension of the Kneser graph story: instead of a single obstruction complex, one studies a family of Hom complexes indexed by test graphs. [/remark] ## Convexity Through Nerves Convexity theorems often assert that a global intersection or representation property follows from checking small subfamilies. The topological question is why local intersection data should control the whole family. The nerve construction answers this by replacing a family of convex sets with a simplicial complex that remembers which subfamilies intersect. [definition: Nerve Of A Family] Let $\mathcal F=\{C_i\}_{i\in I}$ be a finite family of sets. The nerve $\mathcal N(\mathcal F)$ is the simplicial complex on vertex set $I$ whose simplices are the finite subsets $J\subset I$ such that \begin{align*} \bigcap_{j\in J} C_j \ne \varnothing. \end{align*} [/definition] The nerve is useful because convex sets and their finite intersections are contractible whenever they are nonempty. This means that, for convex families, the nerve should not merely record intersection data; it should model the topology of the union. The next theorem is the bridge that lets us convert a geometric covering problem into a homotopy calculation. [quotetheorem:6515] [citeproof:6515] The contractible-intersection hypothesis is essential, and the theorem does not say that every cover is determined by its nerve. If a cover has nonempty intersections with holes, the nerve remembers only which intersections occur, not the topology inside them, so it can give the wrong homotopy type for the union. A concrete finite example is obtained by covering an annulus $A\subset\mathbb R^2$ by the single set $C_1=A$. The nerve has one vertex and is contractible, while $C_1$ deformation retracts onto a circle. A two-set variant keeps the same failure visible in intersections: let $C_1$ and $C_2$ both be the same annulus. Then the nerve is an interval, but the union and the nonempty intersection $C_1\cap C_2$ are annuli, so the good-cover hypothesis fails exactly where the topology of the hole is hidden from the nerve. Convexity rules this out because every nonempty finite intersection of convex sets is convex and hence contractible. There is also a dimensional limitation. The nerve theorem identifies the homotopy type of the union under good-cover hypotheses; it does not by itself prove [Helly's theorem](/theorems/4087). Helly needs an additional fact: nerves of finite convex families in $\mathbb R^d$ are $d$-Leray, meaning that induced subcomplexes have no reduced homology in dimensions at least $d$. The next theorem combines the nerve viewpoint with that Leray input. The main combinatorial consequence is Helly's theorem. The nerve theorem makes the strategy possible: if a minimal family has empty total intersection while every proper subfamily intersects, its nerve is the boundary of a simplex. The dimension of that boundary is then tested against the $d$-Leray property of nerves of convex sets in $\mathbb R^d$, rather than against the topology of an arbitrary subset of Euclidean space. The theorem now asks whether this forbidden boundary nerve can occur when all small subfamilies intersect. This is the precise point at which the convexity hypothesis and the ambient dimension enter the argument. A minimal counterexample would force the nerve to look like the boundary of a simplex; the $d$-Leray property says that such a boundary cannot appear in dimension at least $d$ for a finite convex family in $\mathbb R^d$. Helly's theorem is the resulting translation back from the forbidden nerve to the original intersection problem. [quotetheorem:4087] [citeproof:4087] The planar case is the most geometric version of the argument. It shows the role of dimension without the notation of the general proof: the nerve forced by a minimal counterexample would have homology in a dimension forbidden by the $2$-Leray property of planar convex nerves. [example: Planar Helly Via The Nerve] In $\mathbb R^2$, the planar Helly statement is that a finite family $\mathcal F$ of convex sets has nonempty total intersection once every three members of $\mathcal F$ have nonempty intersection. Suppose, toward a contradiction, that $\bigcap_{C\in\mathcal F}C=\varnothing$, and choose a minimal subfamily $C_1,\dots,C_m$ with empty intersection. Minimality means that every proper subfamily intersects, so the nerve on these $m$ sets contains every proper face of the simplex on vertices $1,\dots,m$, but it does not contain the full face $\{1,\dots,m\}$. Hence the nerve is exactly the boundary of an $(m-1)$-simplex. The boundary of an $(m-1)$-simplex is homeomorphic to $S^{m-2}$. If $m\ge 4$, then \begin{align*} m\ge 4 \quad\Longrightarrow\quad m-2\ge 2, \end{align*} so this nerve has nonzero reduced homology in degree $m-2\ge 2$. But the planar convex-nerve input says that nerves of finite convex families in $\mathbb R^2$ are $2$-Leray: no induced subfamily nerve can have nonzero reduced homology in dimension at least $2$. Therefore $m\ge 4$ is impossible. Thus a minimal counterexample would have $m\le 3$. Since every three members of $\mathcal F$ intersect, the case $m=3$ cannot have empty intersection; and in a larger family the cases $m=1$ or $m=2$ would force some triple containing that empty subfamily to have empty intersection. Hence no minimal counterexample exists. The nerve calculation shows exactly where planarity enters: the forbidden boundary would need homology in dimension at least $2$, which planar convex nerves cannot carry. [/example] Helly's theorem concerns intersections of convex sets. A second convexity theorem in the course asks for a colourful selection: choose one point from each colour class while preserving a convex-hull condition. The topological content is no longer a nerve of intersections, but the same theme remains: local convex data forces a global combinatorial choice. The finite-set formulation below avoids compactness issues and is the version used for combinatorial applications; the same statement for compact colour classes follows by the usual finite approximation argument. [remark: Colorful Caratheodory Theorem External Input] Let $A_1,\dots,A_{d+1}$ be finite subsets of $\mathbb R^d$. If $0\in \operatorname{conv}(A_i)$ for every $i$, then there exist points $a_i\in A_i$ such that \begin{align*} 0\in \operatorname{conv}\{a_1,\dots,a_{d+1}\}. \end{align*} [/remark] This theorem is included as a guiding result for the later direction of the subject. Its proof belongs with the course's later material on colourful and Tverberg-type theorems, where colourful choices are encoded as faces of a join complex and a degree or fixed-point obstruction forces a simplex whose convex hull contains the origin. It is stated here to show how the nerve method broadens into selection theorems, not because the proof is needed for Helly's theorem. The assumptions are close to sharp, but the conclusion should not be overread. The theorem promises one colourful simplex containing $0$; it does not say that most colourful choices work, nor that a choice is unique. The condition $0\in\operatorname{conv}(A_i)$ is required separately for each colour class: knowing only that the union surrounds the origin is not enough. For a concrete failure, take $A_1=\{(1,0)\}$, $A_2=\{(0,1)\}$, and $A_3=\{(-2,1),(1,-2)\}$ in $\mathbb R^2$. The origin lies in the convex hull of $A_1\cup A_2\cup A_3$, but neither triangle obtained by choosing one point from each colour contains $0$. The number $d+1$ matches the Caratheodory scale of the conclusion, but the theorem is not a statement that fewer colour classes can never have the origin in a lower-dimensional colourful hull; such lower-dimensional containments can happen when the selected points are arranged on an affine subspace through $0$. This result points toward Tverberg and colourful Helly theorems, where the same question is asked with partitions, intersections, or transversals replacing a single colourful simplex. [example: Three Colours In The Plane] Let $A_1,A_2,A_3\subset\mathbb R^2$ be finite sets, and suppose $0\in\operatorname{conv}(A_i)$ for each $i=1,2,3$. Since the ambient dimension is $2$, there are $2+1=3$ colour classes, so *[Colorful Caratheodory Theorem](/theorems/6516)* gives points $a_1\in A_1$, $a_2\in A_2$, and $a_3\in A_3$ such that \begin{align*} 0\in\operatorname{conv}\{a_1,a_2,a_3\}. \end{align*} By the definition of convex hull, this means there are real numbers $\lambda_1,\lambda_2,\lambda_3$ with each $\lambda_i\ge 0$, \begin{align*} \lambda_1+\lambda_2+\lambda_3=1, \end{align*} and \begin{align*} \lambda_1a_1+\lambda_2a_2+\lambda_3a_3=0. \end{align*} Thus the origin is a convex combination of the three chosen points, so it lies in the triangle with vertices $a_1,a_2,a_3$. The content of the theorem is the simultaneous choice: although each set $A_i$ may contain many points and may surround $0$ in a different way, one can choose a single representative from each colour so that the mixed triangle still contains $0$. [/example] ## Limits And Open Directions In Equivariant Combinatorics Topological methods are powerful because they turn nonexistence into an obstruction. The limitation is that an obstruction only sees the structure encoded by the chosen space and group action. The final question is therefore methodological: when does topology explain a combinatorial theorem, and when does it merely provide a lower bound that may be far from the true answer? [explanation: What The Obstruction Sees] A graph complex such as $N(G)$, $B(G)$, or $\operatorname{Hom}(T,G)$ forgets many features of $G$ while retaining selected homotopy or equivariant information. If this retained information is strong, it gives chromatic lower bounds that survive graph homomorphisms. If it is weak, two graphs with different coloring behaviour may have complexes with the same relevant index. This is not a defect of the method; it is the price of functoriality. The same abstraction that makes Borsuk--Ulam applicable also determines which combinatorial distinctions are visible. Much of modern topological combinatorics is the search for constructions whose topology is neither too coarse nor too hard to compute. [/explanation] This perspective explains why equivariant combinatorics developed beyond the original Kneser graph proof. Different problems require different configuration spaces, different symmetry groups, and different obstruction theories. Topological Tverberg-type theorems are a good test case because their truth depends on arithmetic information in the symmetry group. [remark: Beyond The Prime Power Barrier] Topological Tverberg-type theorems show both the strength and the boundary of equivariant methods. For prime powers, equivariant obstruction theory gives powerful intersection results. For non-prime powers, known counterexamples show that the same statement fails in full generality, so the topology is detecting a real arithmetic restriction rather than a proof artifact. [/remark] The prime-power phenomenon also explains why the course repeatedly pairs topology with explicit combinatorial models. A theorem may be powered by obstruction theory, but the obstruction has to be computed from a concrete complex. This makes homology computations, shellings, discrete Morse matchings, and deleted-join constructions part of the method rather than auxiliary material. [remark: Computational And Structural Questions] Even when the relevant theorem is conceptually topological, the useful work may be combinatorial: compute a homology group, estimate connectivity, construct a shelling, or identify a discrete Morse matching. The exercises attached to this chapter reflect this balance. They revisit independence complexes, Tucker's lemma, ham sandwich arguments, Kneser graph bounds, deleted joins, and shellings as a compact review of the course's main techniques. [/remark] The course ends with a flexible template. Choose a combinatorial problem, build a configuration space whose points encode possible witnesses, identify the symmetry coming from forbidden coincidences, and prove that an equivariant map cannot exist. The art is in choosing the space so that its topology is computable and its obstruction translates back into the desired combinatorial conclusion. ## References - Anders Bjorner, "Topological Methods," in *Handbook of Combinatorics*, Elsevier, 1995. - Mark de Longueville, *A Course in Topological Combinatorics*, Springer, 2013. - Dmitry Kozlov, *Combinatorial Algebraic Topology*, Springer, 2008. - Jiri Matousek, *Using the Borsuk-Ulam Theorem*, Springer, 2003. - Gunter M. Ziegler, *Lectures on Polytopes*, Springer, 1995.