Modern Graph Theory — Homework 12

Loading…

Assignments: June 2nd, 2026

Problem 1.

Prove: Every Sperner-colored simplicial subdivision contains an odd number of rainbow cells.

Proof.

Let

\Delta=\operatorname{conv}(v_0,v_1,\ldots,v_d),

where

v_i has color i, and let \mathcal{T} be a Sperner-colored simplicial subdivision of \Delta. We use induction on d. The case d=0 is immediate. For d=1, the subdivision is an interval whose endpoints have colors 0 and 1. Each rainbow edge is a place where the color changes. Since the colors at the two ends are different, the number of such changes is odd. Assume now that d\geq 2 and that the result holds in dimension d-1. Let F be the facet of \Delta opposite v_d. The restriction of \mathcal{T} to F is a Sperner-colored subdivision of a (d-1)-simplex with colors 0,1,\ldots,d-1. By induction, it contains an odd number of rainbow (d-1)-cells. Define a graph \Gamma whose vertices are the d-cells of \mathcal{T}, together with one extra vertex *. For every (d-1)-cell with color set

{0,1,\ldots,d-1},

add an edge to \Gamma. If the cell is shared by two d-cells, join the corresponding vertices. If it is a boundary cell, join its unique containing d-cell to *. Every boundary cell counted above lies in F. Indeed, if it lies in the facet of \Delta opposite v_j, then the Sperner condition allows only colors from \{0,1,\ldots,d\}\setminus\{j\}. Since the cell uses all the colors 0,1,\ldots,d-1, we must have j=d. Therefore

\deg_{\Gamma}(*) \equiv 1 \pmod 2

by the induction hypothesis. Let T be a d-cell of \mathcal{T}. Its degree in \Gamma is the number of its facets with color set \{0,1,\ldots,d-1\}. If T is rainbow, exactly one facet is counted, namely the one obtained by deleting the vertex of color d. Thus \deg_{\Gamma}(T)=1. If T uses every color 0,1,\ldots,d-1 but does not use color d, then exactly one of these colors is repeated among the d+1 vertices of T. Deleting either copy of the repeated color gives a counted facet, so \deg_{\Gamma}(T)=2. In all remaining cases, T misses at least one color from 0,1,\ldots,d-1, so no facet is counted and \deg_{\Gamma}(T)=0. Thus the odd-degree vertices of \Gamma, other than *, are exactly the rainbow d-cells. By the handshaking lemma, \Gamma has an even number of odd-degree vertices. Since * has odd degree, the number of rainbow d-cells is odd. ∎

Download the original write-up here.