Chapter 37: Topological Combinatorics

How can topology prove that a graph needs many colors?

A proper coloring assigns colors to graph vertices so that adjacent vertices receive different colors. To prove that too few colors are impossible, we can sometimes turn a proposed coloring into a map between spaces and then show that no map with the required properties can exist. The discrete assignment would violate a topological obstruction.

The space must encode the right combinatorial information. An abstract simplicial complex $K$ is a family of subsets of a finite vertex set, closed under taking subsets. A face with $r+1$ vertices has dimension $r$. Its geometric realization $|K|$ replaces vertices, edges, and higher faces by points, segments, triangles, and higher simplices glued along their common faces. A triangle boundary is a circle; adding its two-dimensional face fills a disk. The same three edges therefore support different topology depending on whether the triangle face is present.

For a finite simple graph $G$ with at least one edge, its neighborhood complex $N(G)$ consists of vertex subsets having a common neighbor. A singleton belongs precisely when its vertex is not isolated. This is different from the clique complex, whose faces are pairwise adjacent vertex sets. We use the following established coloring theorem as an explicit external topological ingredient: if $|N(G)|$ is $q$-connected, then $\chi(G)\ge q+3$. Here $0$-connected means path-connected, $1$-connected additionally means every loop contracts, and $(-1)$-connected means nonempty. Higher connectivity requires all maps from spheres of dimensions at most $q$ to be null-homotopic. The proof uses antipodal symmetry and the Borsuk–Ulam theorem; Section 37.6 explains the mechanism and identifies the omitted deep steps.

A second, directly calculable obstruction supplies this chapter's investigation. Work over the field $\mathbb F_2$, where $1+1=0$. Let $C_r(K)$ be the vector space with one basis vector per $r$-face. The boundary of a face is the sum of its codimension-one faces. Each face of codimension two appears twice under another boundary, giving $\partial_{r-1}\partial_r=0$. Define

$$ H_r(K;\mathbb F_2)=\ker\partial_r/\operatorname{im}\partial_{r+1},\qquad \beta_r=\dim H_r. $$

A cycle belongs to the kernel; a boundary belongs to the image. A cycle represents a nonzero homology class when it cannot be filled by a chain one dimension higher. For a six-edge circle with no triangles, the sum of all six edges is such a class. Adding a cone point fills that cycle and makes the entire complex contractible.

We will use one basic algebraic-topology theorem: continuous maps induce homology maps, compatible with composition and identities. Hence a continuous retraction $r:X\to A$ fixing a subspace $A$ would satisfy $r_{\ast}i_{\ast}=\operatorname{id}_{H_r(A)}$, where $i:A\to X$ is inclusion. If $H_1(X)=0$ but $H_1(A)\ne0$, this is impossible. This is the precise obstruction the final investigation will trace.

The necessary foundation consists of these complex and homology definitions, the finite boundary calculation, and functoriality. All numbered sections are optional extensions. Elementary topology is helpful for homotopy language, but the final chain computations require only finite subsets and linear algebra over $\mathbb F_2$.

37.1 Simplicial complexes

Optional extension; not required to complete the chapter foundation.

A face of an abstract simplicial complex is a vertex subset in the complex. We include the empty face, of dimension $-1$. A facet is an inclusion-maximal face. The complex is pure if all facets have the same dimension. Its $r$-skeleton consists of faces of dimension at most $r$. Specifying facets determines all faces by closure under subsets; failing to include subfaces would violate the definition.

The realization can be defined concretely in $\mathbb R^V$: take vectors with nonnegative coordinates summing to one whose support is a face. Each face gives a coordinate simplex. This construction separates abstract containment from a particular drawing; crossings in a planar sketch do not create new vertices or faces unless the complex declares them.

Solved example. On vertices $a,b,c$, the boundary complex has facets $\{a,b\},\{b,c\},\{a,c\}$. It has three vertices, three edges, and no two-face. Its realization is a circle. The full simplex instead has the single facet $\{a,b,c\}$ and includes that face along with every subset. It has the same one-skeleton but realizes a disk. The face counts are respectively $(f_0,f_1,f_2)=(3,3,0)$ and $(3,3,1)$.

For a graph, the clique complex includes every complete vertex subset. Thus the clique complex of $K_3$ is the filled triangle. But $N(K_3)$ is the triangle boundary: every proper subset has a common neighbor, while all three vertices do not, since the graph has no loops. This small distinction is central to topological graph coloring.

The link of a face $\sigma$ is $\operatorname{lk}_K\sigma=\{\tau\in K:\tau\cap\sigma=\varnothing,\ \tau\cup\sigma\in K\}$. It describes directions near that face. In the triangle boundary, the link of $a$ consists of two isolated vertices $b,c$, with no edge between them. In the filled triangle, the same link is the edge $\{b,c\}$ and its subfaces.

Exercise. Is the family with facets $\{a,b,c\}$ and $\{c,d\}$ pure? List its maximal dimensions. Hint: one facet has three vertices and the other has two. Solution: the dimensions are two and one, so it is not pure. Its triangle and pendant edge must both include all their subfaces. The edge $\{c,d\}$ is a facet even though it has smaller dimension.

37.2 Homology and basic algebraic topology

Optional extension; not required to complete the chapter foundation.

For finite complexes, homology becomes a boundary-matrix calculation. Over $\mathbb F_2$ orientation signs disappear, but boundaries must still be composed correctly. The ordinary boundary $\partial_0$ is zero. Reduced homology instead adds the augmentation $C_0\to\mathbb F_2$ sending every vertex to one, so a nonempty connected complex has reduced $H_0=0$.

If $f_r$ is the number of $r$-faces, then

$$ \beta_r=f_r-\operatorname{rank}\partial_r-\operatorname{rank}\partial_{r+1}. $$

The formula uses $\operatorname{im}\partial_{r+1}\subseteq\ker\partial_r$. It measures holes modulo fillings; simply counting cycles in a graph can overcount when triangle faces are present.

Homotopy equivalence is stronger than agreement of Betti numbers. Contractible means homotopy equivalent to a point. A cone is contractible by moving each point linearly toward its apex. Homology detects this contraction, but vanishing reduced homology alone does not prove an arbitrary complex contractible. Likewise, $H_1=0$ alone does not prove that the fundamental group is trivial.

Euler characteristic is $\chi(K)=\sum_{r\ge0}(-1)^rf_r$. Euler–Poincaré gives $\chi(K)=\sum_{r\ge0}(-1)^r\beta_r$. It follows by substituting the rank formula and canceling consecutive boundary ranks. The triangle boundary has characteristic zero; the filled triangle has characteristic one, agreeing with the computed homology.

Exercise. Compute the Betti numbers of two disjoint edges. Hint: the two boundary columns involve disjoint vertex pairs. Solution: $f_0=4,f_1=2$ and $\operatorname{rank}\partial_1=2$. Hence $\beta_0=2,\beta_1=0$ and $\chi=2$. Reduced $\beta_0$ is one, recording the one extra connected component beyond the first.

37.3 Order complexes of posets

Optional extension; not required to complete the chapter foundation.

For a finite poset $\mathcal P$, its order complex $\Delta(\mathcal P)$ has the elements of $\mathcal P$ as vertices and its finite chains as faces. A chain of $r+1$ elements gives an $r$-face. Edges represent all comparable pairs, not merely covers. A Hasse diagram shows covers only, so it is not automatically the one-skeleton of the order complex.

Let $B_3$ be the Boolean lattice of subsets of $\{1,2,3\}$, and remove its minimum and maximum. The proper part $\overline B_3$ has three singletons and three two-element subsets. Its maximal chains are the six containments $\{i\}\subset\{i,j\}$. There are no three-element chains in this proper part, so its order complex is one-dimensional.

Solved example and diagram. Its six edges form the cycle

$$ \{1\},\ \{1,2\},\ \{2\},\ \{2,3\},\ \{3\},\ \{1,3\},\ \{1\}. $$

The diagram shows the same incidences twice: as a ranked poset on the left and as the order-complex circle on the right. Every left connector is one containment and every right edge is the corresponding two-element chain. Crossings between left connectors do not add relations. The right-hand hexagon has no filled interior face.

This is the barycentric subdivision of a triangle boundary. For any finite complex $K$, take the poset of its nonempty faces ordered by inclusion; its order complex subdivides $K$ and has a homeomorphic realization. Map the vertex representing a face to that face's barycenter, then extend linearly on chains. In this example the three singleton vertices stay at triangle corners and the three pair vertices go to edge midpoints.

If the full set $\{1,2,3\}$ is retained in the poset, it is a maximum comparable with every element. Every chain can be extended by it, so the order complex is a cone, with seven vertices, twelve edges, and six triangles. Removing or retaining the maximum changes the topology. Retaining a minimum likewise creates a cone.

Exercise. Determine the order complex of a three-element chain $a\lt b\lt c$. Hint: include the comparable pair $a,c$ even though it is not a cover. Solution: all subsets of $\{a,b,c\}$ are chains. The order complex is a filled triangle with three edges, including $ac$. The Hasse diagram has only two cover connectors and would miss this face data.

37.4 Sperner's lemma and KKM theorem

Optional extension; not required to complete the chapter foundation.

In a triangulated $d$-simplex with original vertices labeled $0,\ldots,d$, a Sperner labeling assigns each triangulation vertex a label of an original vertex in the smallest original face containing it. Thus a vertex on a boundary face may use only labels from that face. Sperner's lemma says that a fully labeled small $d$-simplex exists; more strongly, their number is odd.

In dimension two, count incidences of small triangles with edges labeled $0,1$. Boundary edges of this type occur only on the original $0,1$ side. Reading its labels from endpoint zero to endpoint one gives an odd number of transitions between zero and one. Interior edges are counted twice. A triangle with all three labels contributes one distinguished edge, a triangle using both zero and one but not two contributes two, and all other triangles contribute zero. Reducing the count modulo two proves that the fully labeled triangles are odd in number. The general parity proof proceeds inductively through facets.

Solved example. Subdivide a triangle by its three edge midpoints into four triangles. Label the original corners $0,1,2$ and the midpoints on sides $01,12,20$ by $0,1,2$, respectively. Every label satisfies the boundary rule. The central triangle has labels $0,1,2$. The three corner triangles have labels $(0,0,2),(1,1,0),(2,2,1)$ and are not fully labeled. Exactly one is fully labeled, verifying the parity statement on this specified triangulation.

The KKM theorem uses the standard simplex with barycentric coordinates $\lambda_0,\ldots,\lambda_d$. Let $F_0,\ldots,F_d$ be closed subsets of the simplex. Assume that every face indexed by a nonempty set $J$ is covered by $\bigcup_{j\in J}F_j$. Then $\bigcap_iF_i\ne\varnothing$.

To prove it from Sperner, triangulate with mesh tending to zero. At each vertex choose an index from the face containing it whose set contains the vertex, possible by the covering hypothesis. Each triangulation has a fully labeled simplex. Compactness gives a subsequence of these shrinking simplices converging to one point; the chosen vertex of each label also converges to that point. Closedness places it in every $F_i$. Arbitrary labels without the face restriction would not provide this proof.

Solved KKM instance. Take $F_i=\{\lambda:\lambda_i\ge\lambda_j\text{ for every }j\}$. These sets are closed. On a face indexed by $J$, some largest coordinate belongs to $J$, so that face is covered by the appropriate $F_i$. Their total intersection consists of the barycenter, where all coordinates equal $1/(d+1)$.

Exercise. In a triangle, do $F_i=\{\lambda_i\ge1/3\}$ satisfy the KKM condition? Hint: a face's nonzero coordinates sum to one. Solution: on a vertex or edge, a coordinate indexed by that face is at least one or one half, respectively; in the full triangle some coordinate is at least one third. Thus the condition holds. Their common intersection is the barycenter, since three coordinates each at least one third and summing to one must all equal one third.

37.5 Borsuk–Ulam theorem

Optional extension; not required to complete the chapter foundation.

Let $S^d=\{x\in\mathbb R^{d+1}:\|x\|=1\}$. The antipodal involution sends $x$ to $-x$. Borsuk–Ulam states that every continuous map $f:S^d\to\mathbb R^d$ has some antipodal pair with equal images: $f(x)=f(-x)$. Equivalently, every continuous odd map $g:S^d\to\mathbb R^d$, satisfying $g(-x)=-g(x)$, has a zero.

The equivalence follows by applying the odd statement to $g(x)=f(x)-f(-x)$; conversely, equal antipodal values of an odd map imply both are zero. A further formulation says there is no continuous odd map $S^d\to S^{d-1}$ for $d\ge1$. A nonvanishing odd map to $\mathbb R^d$ could be normalized to produce such a forbidden map.

Solved example. On $S^2$, take $f(x,y,z)=(x,y)$. At the antipodal poles $(0,0,1)$ and $(0,0,-1)$ both images are $(0,0)$. The map is odd, and these are precisely its zeros. By contrast, the identity embedding $S^1\to\mathbb R^2$ has no equal antipodal images: its target dimension exceeds the theorem's permitted dimension.

For $d=1$, the theorem has an elementary proof. The scalar function $g(x)=f(x)-f(-x)$ changes sign between the endpoints of any semicircle; the intermediate value theorem supplies a zero. If either endpoint is already zero, no further argument is needed.

Proof sketch; omitted prerequisites. For $d\ge2$, an odd map $S^d\to S^{d-1}$ would restrict on the equator to an odd self-map of $S^{d-1}$. Such a map has odd degree, a nonzero integer. But it extends over a hemisphere, so its degree must be zero. The degree theory and odd-degree lemma are omitted. For $d=1$, connectedness of $S^1$ alone rules out an odd continuous map to the two-point space $S^0$.

The obstruction is equivariant: maps must respect the involution. Ordinary continuous maps from one sphere to another always exist, for example constant maps. Forgetting the symmetry would erase the contradiction used in coloring arguments.

Exercise. Explain why $g:S^2\to\mathbb R$, $g(x,y,z)=z$, has antipodal equal values on the equator. Hint: both values must be zero for an odd scalar map. Solution: every point with $z=0$ maps to zero, as does its antipode. This example has an entire equatorial zero set; the theorem guarantees existence, not uniqueness or a prescribed number of pairs.

37.6 Lovász's proof of the Kneser conjecture

Optional extension; not required to complete the chapter foundation.

For integers $n\ge2k$ and $k\ge1$, the Kneser graph $KG(n,k)$ has the $k$-element subsets of $[n]$ as vertices, with an edge between disjoint sets. A color class is therefore a pairwise intersecting family. The established Lovász–Kneser theorem is

$$ \chi(KG(n,k))=n-2k+2. $$

The historical Kneser conjecture was proved in 1978; it is not an open assumption. The original source is Lovász, Kneser's conjecture, chromatic number, and homotopy90022-5).

The upper bound has an elementary coloring. Put $r=n-2k+1$. If a $k$-set contains an element of $[r]$, color it by its least such element. All sets in one of these colors intersect at that element. Give every remaining set color $r+1$. Remaining sets lie in a ground set of size $2k-1$, so two of them cannot be disjoint. This produces $r+1=n-2k+2$ colors, including the endpoint case $n=2k$.

The lower bound is where topology enters. Lovász proves that the neighborhood complex of $KG(n,k)$ is $(n-2k-1)$-connected. Applying the coloring obstruction gives $\chi\ge(n-2k-1)+3=n-2k+2$. At $n=2k$, the connectivity assertion means only nonemptiness, giving the correct lower bound two.

Proof sketch; omitted prerequisites. A proper coloring is a graph homomorphism to a complete graph and induces maps on associated complexes. An auxiliary construction with a free involution converts the relevant connectivity into an antipodal obstruction. Borsuk–Ulam prevents the equivariant map that too few colors would require. The full construction and the Kneser neighborhood-connectivity computation are omitted deep lemmas; connectivity is not inferred merely from vanishing low-dimensional homology. For further primary development of the associated complexes, see Matoušek and Ziegler, Topological lower bounds for the chromatic number: A hierarchy.

Solved example. In $KG(5,2)$ there are ten vertices and fifteen edges: each two-set is adjacent to the three two-sets in its three-element complement. Color sets containing $1$ by color one; the remaining sets containing $2$ by color two; and $34,35,45$ by color three. Each class is intersecting. The cycle

$$ 12,\ 34,\ 15,\ 23,\ 45,\ 12 $$

has five edges, since consecutive sets are disjoint. Its odd length rules out two colors, proving the answer three on this small graph independently. Lovász's general theorem also gives $5-4+2=3$. The clique number here is only two: three disjoint two-sets would require six ground elements. Thus clique size alone misses the chromatic lower bound.

Exercise. Give the theorem's chromatic number for $KG(7,3)$ and explain the last color class in the elementary construction. Hint: the first two ground elements get their own possible colors. Solution: the number is $7-6+2=3$. Sets avoiding $1,2$ are three-subsets of a five-element set, so any two intersect. They can all receive the third color.

37.7 Nerve theorem and topological Helly theorems

Optional extension; not required to complete the chapter foundation.

For a finite family of sets $\mathcal U=\{U_i\}$, its nerve has a face indexed by $J$ exactly when $\bigcap_{j\in J}U_j\ne\varnothing$. It records simultaneous intersections, not just pairwise ones. A good open cover has all nonempty finite intersections contractible. For a finite good open cover in Euclidean space, the nerve theorem gives a homotopy equivalence between the nerve realization and the union. Openness and the good-intersection condition supply a clean version with explicit hypotheses; other closed-cover versions require their own conditions. A primary treatment of these distinctions is Bauer, Kerber, Roll, and Rolle, A Unified View on the Functorial Nerve Theorem and its Variations.

Solved example. Place centers at $(0,0),(\sqrt3,0),(\sqrt3/2,3/2)$, forming an equilateral triangle of side $\sqrt3$, and take open disks of radius $9/10$. Every pair overlaps, because half the center separation is $\sqrt3/2\lt9/10$. The circumcenter is $c=(\sqrt3/2,1/2)$, at distance one from each center $p_i$. For any point $z$,

$$ \sum_{i=1}^3\|z-p_i\|^2=3\|z-c\|^2+3\ge3. $$

Membership in all three disks would make that sum strictly less than $3(9/10)^2=243/100$, impossible. Thus the nerve is the three-edge boundary of a triangle, with $H_1$ of dimension one. Since every nonempty intersection is convex and hence contractible, the nerve theorem identifies the union's homotopy type with a circle. Pairwise overlap does not imply triple overlap.

There is a topological Helly principle in this setting. A finite family of open subsets of $\mathbb R^d$ whose every nonempty finite intersection is contractible has Helly number at most $d+1$: if every subfamily of at most $d+1$ intersects, so does the whole family. To see the obstruction, take an inclusion-minimal empty subfamily with $r$ members. Its nerve is the boundary of an $(r-1)$-simplex, a sphere of dimension $r-2$. The nerve theorem identifies this with the union's homotopy type. But an open subset of $\mathbb R^d$ has no homology in dimensions at least $d$. Therefore $r-2\lt d$ and $r\le d+1$.

This proof uses the ambient homology-vanishing theorem as an omitted topology ingredient. In general, saying that each individual set is contractible is insufficient: all nonempty intersections must satisfy the condition. Convex open sets provide a familiar sufficient condition, recovering a version of geometric Helly through topology.

Exercise. What changes if the three disks in the example have radius greater than one? Hint: test the circumcenter. Solution: it belongs to all three open disks, so the nerve is a filled triangle. All intersections remain convex; the nerve theorem now gives a contractible union. At radius exactly one, the circumcenter lies on the excluded boundaries, so the strict open-disk distinction matters.

37.8 Discrete Morse theory

Optional extension; not required to complete the chapter foundation.

Discrete Morse theory compresses a complex while tracking its topology. One combinatorial formulation uses a matching on cover pairs $(\sigma,\tau)$ in the poset of nonempty faces, with $\sigma$ a codimension-one face of $\tau$. Each face participates in at most one pair. Orient matched cover edges upward and all other cover edges downward; require the directed graph to have no directed cycle. Unmatched faces are critical.

Forman's theorem gives a homotopy-equivalent cell complex with one cell for each critical face. In particular, the number of critical $r$-faces is at least $\beta_r$ over any field. This is an established theorem; see Forman, Morse Theory for Cell Complexes (1998). A matching without acyclicity is not sufficient.

Solved example. Label the six-cycle vertices $a_0,\ldots,a_5$ and edges $e_i=\{a_i,a_{i+1}\}$, with subscripts modulo six. Match $a_i$ with $e_{i-1}$ for $i=1,\ldots,5$. These use the five edges of a spanning path. The critical faces are $a_0$ and the closing edge $e_5$.

The directed alternating path from $a_i$ goes upward to $e_{i-1}$ and downward to $a_{i-1}$, reducing the index. The closing edge is unmatched and points downward to its endpoints, with no arrow leading into it from a vertex. Therefore there is no directed cycle. The resulting critical counts are one vertex and one edge, compatible with $\beta_0=\beta_1=1$ and with a circle's cell structure.

An elementary collapse is more specific: remove a maximal simplex together with a free codimension-one face that belongs to no other maximal simplex. This preserves homotopy type. A filled triangle can collapse by removing the pair $(ac,abc)$, then $(c,bc)$, then $(b,ab)$, leaving $a$. The six-cycle has no free vertex on an edge, so that same literal collapse strategy cannot remove its essential loop. Its acyclic matching instead records one critical edge.

Exercise. Why does matching every $a_i$ to $e_i$ in the six-cycle fail? Hint: follow the upward matched edge, then the downward unmatched incidence. Solution: it gives $a_0\to e_0\to a_1\to e_1\to\cdots\to a_0$, a directed cycle. The invalid matching would claim no critical cells despite nonzero homology, revealing the importance of acyclicity.

37.9 Topological methods in graph coloring

Optional extension; not required to complete the chapter foundation.

A proper $m$-coloring is a graph homomorphism $G\to K_m$. If a subset has a common neighbor in $G$, its image has the image of that neighbor as a common neighbor in $K_m$. Therefore coloring induces a simplicial map $N(G)\to N(K_m)$. The latter consists of all proper subsets of the $m$ vertices, so its realization is $S^{m-2}$ for $m\ge2$.

The existence of an ordinary map to that sphere is not itself a contradiction: constant maps exist. The coloring bound needs the additional equivariant structure carried by a suitable graph complex, together with connectivity. It is essential not to replace Lovász's theorem by the false claim that a nonzero homology class automatically rules out every map to a lower-dimensional space.

Solved example. For $C_4$ with vertices $0,1,2,3$, its neighborhood complex has maximal faces $\{0,2\}$ and $\{1,3\}$. It is two disjoint edges, not the four-cycle itself. Its connectivity is $-1$, so the bound gives only $\chi\ge2$, which is attained by alternating colors. For $C_5$, the neighborhood complex is the connected five-cycle computed in the opening card, giving $\chi\ge3$. This comparison isolates the relevant connectivity difference.

More generally, for $C_n$ with $n\ge5$, neighborhood edges join vertices two steps apart modulo $n$. If $n$ is odd this graph is one cycle; if $n$ is even it is two cycles. Thus the neighborhood complex is connected precisely in the odd case. The case $n=4$ has coincident descriptions of some edges and yields two edges rather than two simple cycles, so it must be treated separately.

Ordinary connectivity and equivariant indices provide related but distinct bounds. An index of a free involutive space measures the smallest antipodal sphere admitting an equivariant map from it, when such a sphere exists. A coloring can bound an appropriate index from above; topological information bounds it from below. The exact graph-complex choice and normalization must be specified before using a numerical index. For primary comparisons of these constructions, see Csorba, Lange, Schurr, and Wassmer, Box complexes, neighborhood complexes, and the chromatic number.

Exercise. Compute the neighborhood complex of $K_3$ and use the connectivity bound. Hint: a common neighbor must lie outside the chosen subset. Solution: all one- and two-element subsets are faces, but the triple is not. The complex is a connected circle, giving $\chi(K_3)\ge3$. The three singleton colors show equality. Its clique complex is instead the filled triangle, illustrating again that these complexes are not interchangeable.

37.10 Topological and algebraic invariants of combinatorial complexes

Optional extension; not required to complete the chapter foundation.

Face counts, Euler characteristic, homology, fundamental groups, and face rings preserve different information. Face counts depend on the triangulation; homology and Euler characteristic depend only on homotopy type. Subdivision can increase face counts without changing the underlying space. Betti numbers depend on the coefficient field when integral homology has torsion, so the field must be stated.

For the proper Boolean interval, the order-complex Euler characteristic also connects to the Möbius function. If $\mathcal P$ has minimum $\hat0$ and maximum $\hat1$, then

$$ \widetilde\chi\bigl(\Delta((\hat0,\hat1))\bigr)=\mu(\hat0,\hat1). $$

The identity follows by expanding the Möbius recursion as an alternating sum over chains. For $B_3$, $\mu(\varnothing,\{1,2,3\})=(-1)^3=-1$. The six-cycle has ordinary characteristic $6-6=0$, hence reduced characteristic $-1$, agreeing with the identity. Adding the maximum makes a cone with ordinary characteristic one and reduced characteristic zero.

The Stanley–Reisner ring over a field $\mathbb k$ is

$$ \mathbb k[K]=\mathbb k[x_v:v\in V]/I_K, $$

where $I_K$ is generated by squarefree monomials whose vertex supports are nonfaces. It remembers the abstract face structure algebraically. For the triangle boundary, the only minimal nonface is $\{a,b,c\}$, so $I_K=(x_ax_bx_c)$. For the filled triangle, $I_K=0$. The boundary ring's Hilbert series is

$$ \frac{1-z^3}{(1-z)^3}=\frac{1+z+z^2}{(1-z)^2}, $$

since multiplication by the nonzero monomial $x_ax_bx_c$ gives an injective degree-three shift in the polynomial ring. The filled triangle has series $1/(1-z)^3$. This algebraic contrast records the missing face that creates the topological loop.

For the six-cycle, there are no triangle faces, and monomials have support in a vertex or edge. Counting by exact support gives

$$ \operatorname{Hilb}_{\mathbb k[K]}(z)=1+6\frac z{1-z}+6\frac{z^2}{(1-z)^2} =\frac{1+4z+z^2}{(1-z)^2}. $$

Its ring differs from the triangle boundary ring despite homeomorphic realizations. The numerator is a combinatorial $h$-polynomial of the complex, not the Ehrhart $h^{\ast}$-polynomial of a lattice polytope. Topological equivalence does not identify all these algebraic data.

Exercise. Compare the Euler characteristics and Betti numbers of a circle and the disjoint union of a point with a figure-eight, where the figure-eight consists of two circles joined at one vertex. Hint: count connected components and independent loops. Solution: the circle has $(\beta_0,\beta_1)=(1,1)$, whereas the disjoint union has $(\beta_0,\beta_1)=(2,2)$. Both have Euler characteristic zero. Thus equal Euler characteristic does not determine the Betti numbers or connectedness.

Build an order complex and trace a topological obstruction

The investigation constructs the order complex of a Boolean interval, computes its homology, and proves a precise no-retraction statement. It also asks how graph-coloring obstructions use a different associated complex and additional hypotheses. The goal is to distinguish a verified boundary calculation from a broad topological claim unsupported by it.

Worked solution: chains and boundary matrix. Use the cyclic vertex order

$$ a_0=\{1\},\ a_1=\{1,2\},\ a_2=\{2\},\ a_3=\{2,3\},\ a_4=\{3\},\ a_5=\{1,3\}. $$

There are six one-element chains and six two-element chains, one for each cyclic edge. No chain has three elements. Thus $f_0=f_1=6$ and $f_2=0$. With columns $e_i=\{a_i,a_{i+1}\}$ and row order $a_0,\ldots,a_5$, the matrix is

$$ \partial_1=\begin{pmatrix} 1&0&0&0&0&1\\ 1&1&0&0&0&0\\ 0&1&1&0&0&0\\ 0&0&1&1&0&0\\ 0&0&0&1&1&0\\ 0&0&0&0&1&1 \end{pmatrix}. $$

Every column has two ones, so the row sum is zero and the rank is at most five. The first five columns are independent: in a linear combination equaling zero, the row at the path's last vertex forces the last coefficient to vanish, and proceeding backward forces all five to vanish. Hence the rank is five. The kernel is generated by the all-ones edge vector; with no two-faces it is not a boundary. Therefore $H_0\cong\mathbb F_2$, $H_1\cong\mathbb F_2$, and all higher groups vanish. Reduced $H_0=0$ and reduced $H_1\cong\mathbb F_2$. Both face and Betti calculations give Euler characteristic zero.

Worked solution: coning and obstruction. Write $u$ for the maximum subset. Adding it permits a face $\sigma\cup\{u\}$ for every old face $\sigma$, so $D=u*K$ is the cone. It has seven vertices, the six old edges plus six apex edges, and six triangles, one over each old edge. Thus its characteristic is $7-12+6=1$. Linear contraction toward $u$ proves contractibility, so $H_1(D)=0$.

If a retraction $r:|D|\to|K|$ existed, then $r\circ i$ would be the identity on $|K|$. On first homology,

$$ r_{\ast}\circ i_{\ast}=\operatorname{id}_{H_1(K)}. $$

But $i_{\ast}$ maps to the zero vector space $H_1(D)$, so the composition is zero. It cannot equal the identity on the nonzero space $H_1(K)\cong\mathbb F_2$. This proves the no-retraction conclusion. Equivalently, the sum of the six apex triangles has boundary equal to the old cycle: apex edges each occur twice and cancel, while old edges occur once. The class becomes a boundary inside $D$, which a retraction cannot undo while fixing its boundary subspace.

Worked solution: exploration and invariants. Exact row reduction for $D$ gives $\operatorname{rank}\partial_1=6$ and $\operatorname{rank}\partial_2=6$. Consequently $\beta_1=12-6-6=0$ and $\beta_2=6-6=0$, agreeing with the cone contraction. The six-cycle's reduced characteristic is $-1$, equal to the Boolean interval's Möbius value. Its face-ring Hilbert numerator is $1+4z+z^2$, whereas the three-edge circle's is $1+z+z^2$; subdivision preserves topology while changing algebraic face data.

The order complex's one-skeleton is an even six-cycle and is two-colorable by alternating the singleton and two-element-subset vertices. Its first homology is nonzero, so nonzero $H_1$ does not force three colors. For a coloring bound, construct the original graph's neighborhood complex and verify its connectivity; for stronger bounds, the requisite equivariant structure and higher connectivity must also be justified.

Application and optional extension. In coverage modeling, sensor regions form a cover and their simultaneous intersections form a nerve. For a finite good open cover, the nerve theorem allows homology calculations to detect holes in the covered union. Pairwise proximity alone gives only a graph and can miss whether triangles are filled by common triple intersections. A detected loop is evidence about the modeled cover under those hypotheses; it does not automatically prove coverage of an external target region or robustness to measurement error.

For $\overline B_4$, vertices correspond to the fourteen nonempty proper subsets of a four-element set. Two-element chains number thirty-six and three-element chains number twenty-four. Its order complex subdivides a tetrahedron boundary, hence is a two-sphere. Thus $\beta_0=1,\beta_1=0,\beta_2=1$ and characteristic $14-36+24=2$. The subdivision argument proves the sphere identification; independent chain enumeration and boundary ranks provide a finite consistency check.