A Chain-Level Borsuk--Ulam Obstruction Proof of Norine's Antipodal-Coloring Conjecture

Technical Summary: A Chain-Level Borsuk–Ulam Obstruction Proof of Norine's Antipodal-Coloring Conjecture

Problem Statement
The paper addresses a conjecture posed by Norine in 2008 regarding the edge-coloring of the $n$-dimensional hypercube, denoted $Q_n$ for $n \ge 2$. The vertices of $Q_n$ are elements of $\{0, 1\}^n$, with adjacency defined by a Hamming distance of 1. The antipodal map $A_n$ sends a vertex $x$ to its complement $1-x$. An edge-coloring of $Q_n$ with two colors (red and blue) is termed antipodal if every pair of antipodal edges (edges $xy$ and $A_n(x)A_n(y)$) receive opposite colors.

Norine's conjecture asserts that every such antipodal red–blue edge-coloring must contain a monochromatic path connecting some vertex $x$ to its antipode $A_n(x)$. Prior to this work, the conjecture had been verified for dimensions $n \le 8$ using computational methods, SAT solvers, and case-by-case proofs, but a general proof for all $n$ remained open.

Methodology
The authors employ a topological combinatorics approach, specifically utilizing algebraic chain-level obstructions derived from the Borsuk–Ulam theorem. The proof strategy proceeds through the following stages:

1. Reduction to Rook Labeling:
   The problem is first reduced from the existence of a monochromatic antipodal path to the non-existence of a specific combinatorial object: a "rook labeling." A rook labeling is a map $q: V(Q_K) \to \Omega_K$ (where $\Omega_K = \{(a,b) \in [K]^2 : a \neq b\}$) satisfying an antipodal symmetry condition $q(A_K x) = \tau(q(x))$ (swapping coordinates) and a "rook" adjacency condition (adjacent vertices share a coordinate). The authors prove that if a counterexample to Norine's conjecture existed in $Q_n$, one could construct such a labeling for sufficiently large $K$.

2. Algebraic Chain Construction:
   Assuming a rook labeling exists, the authors construct a chain map between two specific chain complexes over the field $\mathbb{F}_2$:

   • Source: The cellular chain complex of the boundary of the $K$-dimensional cube, $\partial_{\text{top}} I_K$, which is homeomorphic to the sphere $S^{K-1}$.
   • Target: A subdivision-invariant polyhedral chain complex on the sphere $S(W_K) \cong S^{K-2}$, where $W_K$ is the hyperplane $\sum z_i = 0$ in $\mathbb{R}^K$.

   The construction involves three main steps:

   • Freudenthal Subdivision: The cubical cellular chains are mapped to simplicial chains via the Freudenthal triangulation. The sum of maximal simplices in a cubical face cancels internal facets modulo 2, preserving the chain structure.
   • Rook Galleries and Roots: Vertices of the simplices are labeled by the rook labeling. These labels are converted to "roots" in $W_K$ (vectors of the form $e_a - e_b$). A sequence of labels along a simplex forms a "rook gallery."
   • Radial Polyhedral Chains: A linear map $\rho$ is defined that sends a simplex to a spherical polyhedral chain (a "radial chain") determined by the positive cone of its root vectors. If the roots are linearly dependent or their convex hull contains the origin, the chain is defined as zero.

3. The Obstruction:
   The composite map $\Theta = \rho \circ F$ is shown to be an antipodally equivariant, augmentation-preserving chain map from a complex representing $S^{K-1}$ to a complex representing $S^{K-2}$. The authors then invoke a purely algebraic obstruction (Lemma 3.1), a chain-level version of the Borsuk–Ulam theorem. This lemma states that no such equivariant chain map can exist if the target complex has no chains above dimension $K-2$ and satisfies specific kernel-image equalities for the antipodal norm operator.

Key Contributions and Results

• Proof of Norine's Conjecture: The paper provides the first general proof that for all $n \ge 2$, every antipodal red–blue edge-coloring of $Q_n$ contains a monochromatic path between a vertex and its antipode (Theorem 1.1).
• Algebraic Borsuk–Ulam Obstruction: The authors develop a specific algebraic obstruction (Lemma 3.1) that rules out equivariant chain maps between spheres of different dimensions without relying on continuous maps. This allows the contradiction to be derived directly from the discrete combinatorial structure (the monochromatic component structure) rather than via a continuous approximation.
• Polyhedral Chain Complex: The paper constructs a subdivision-invariant polyhedral chain complex on the sphere $S(W_K)$ and proves the necessary algebraic properties (specifically the kernel-image identity for the antipodal norm operator) to apply the obstruction.
• Rook Gallery Rank Bound: A key combinatorial lemma (Lemma 5.1) establishes that if the roots of a rook gallery contain the origin in their convex hull, their linear rank is at most $m-2$ (where $m$ is the number of roots). This ensures the boundary operator behaves correctly under the radial map, causing the "bad" simplices to vanish.

Significance
The paper claims to settle a problem that had remained open since 2008, extending previous results which were limited to low dimensions ($n \le 8$). The significance lies in:

1. Dimensional Generality: It confirms that the phenomenon of monochromatic antipodal connectivity persists throughout the entire sequence of hypercubes, removing the confinement to specific dimensions.
2. Methodological Advancement: It explicitly connects the discrete cube problem to a topological picture using a "purely algebraic chain-level Borsuk–Ulam obstruction." Unlike previous topological combinatorics proofs that often rely on continuous maps or fixed-point theorems, this proof extracts the obstruction directly from the chain complex structure of the discrete object.
3. Refinement of Topological Methods: The work demonstrates how to handle discrete structures (cubical boundaries) by mapping them to polyhedral chains on lower-dimensional spheres, bridging the gap between discrete coloring problems and continuous topological obstructions.

The authors note that while the main conjecture is resolved, stronger versions remain open, such as whether the monochromatic path can always be chosen to be a geodesic, or whether bounds on color changes in arbitrary (non-antipodal) colorings can be improved.