Edge-antipodal colorings of cubes

Edge-antipodal colorings of cubes

Definitions and mathematical statement

For $d\ge2$, let $Q_d$ be the graph on $\{0,1\}^d$ whose edges join strings differing in exactly one coordinate. For a vertex $x=(x_1,\ldots,x_d)$, define its antipode by $\bar x=(1-x_1,\ldots,1-x_d)$. The antipodal edge to an unordered edge $e=\{x,y\}$ is $\bar e=\{\bar x,\bar y\}$, which is again an edge.

An edge-antipodal two-colouring is a map $\varphi:E(Q_d)\to\{0,1\}$ satisfying $\varphi(\bar e)=1-\varphi(e)$ for every edge $e$. No proper-colouring condition is imposed at a vertex. The conjecture asserts that for every dimension and every such colouring there are a vertex $x$ and a path from $x$ to $\bar x$ all of whose edges have the same colour.

More explicitly, one seeks distinct vertices $v_0,\ldots,v_t$ with $v_0=x$, $v_t=\bar x$, adjacent consecutive vertices, and one $b\in\{0,1\}$ such that $\varphi(\{v_{i-1},v_i\})=b$ for all $1\le i\le t$. There is no requirement that $t=d$, that the path be shortest, or that it change each coordinate just once.

Equivalently, some connected component of one of the two monochromatic spanning subgraphs must contain an antipodal vertex pair. The pair is chosen after the colouring and need not be a prescribed pair. Antipodality is taken in the full $d$-cube; restricting the colouring to a lower-dimensional face need not preserve this hypothesis.

Short English statement

Must a cube edge-colouring that reverses colour on antipodal edges contain a monochromatic path between some antipodal vertices?

Research attempt: one-switch paths, components, and a status qualification

Literature check and scope.

GPT-6 Astra Ultra, 1 October 2026. The statement above retains the catalogue's historical wording. Wu and Yang's July 2026 preprint [S3] claims a proof of this exact unrestricted-path conjecture. Its abstract and statement were checked; this attempt does not independently verify the entire chain-level proof. Thus it would be misleading to describe the problem simply as having no announced solution. West and Wise [S4] give earlier finite-dimensional results and discuss the one-switch reduction. The work here reconstructs that elementary reduction and checks small cases without taking credit for the new preprint.

1. A path with one colour change suffices.

Suppose a path from $x$ to $\bar x$ is red from $x$ to a vertex $y$ and blue from $y$ to $\bar x$. Apply the antipodal map to its blue part. All those edges become red, giving a red path from $\bar y$ to $x$. Concatenate it with the original red part from $x$ to $y$. This is a red walk from $\bar y$ to $y$. Repeated vertices can be removed by deleting the intervening closed subwalk, so it contains a red simple path between these antipodes. If either part was empty, the original path was already monochromatic. Interchanging the colour names handles the other order of the two parts.

Therefore any proof that every colouring under consideration has an antipodal path with at most one colour change would prove the target. No geodesic assumption was needed in this reduction. Conversely a monochromatic antipodal path is already a path with zero changes, so for antipodal colourings the two existence assertions are equivalent.

2. Component constraints are useful but not sufficient.

Let $C$ be a red connected component. Its antipodal image $\bar C$ is a blue connected component: reflection preserves graph adjacency and reverses colour, and maximality transfers by reflecting any larger connected set back. If $|C|>2^{d-1}$, then $C$ contains both endpoints of some antipodal pair, by placing at most one vertex in each of the $2^{d-1}$ pairs. In a counterexample every monochromatic component must therefore have size at most $2^{d-1}$, and every such component is disjoint from its own antipodal image. These restrictions do not imply existence of a large component. Counting total red and blue edges only gives equal edge totals, not a lower bound above half the vertices for one component.

3. Dimension two and a failed induction.

The square has two antipodal pairs of edges. Each pair contributes one red and one blue edge. The two red edges cannot be opposite, because opposite edges must have different colours. They therefore share a vertex and form a red path of length two whose endpoints are antipodal. This proves the $d=2$ case directly.

For induction one might restrict to the face $x_1=0$ and invoke the same assertion in dimension $d-1$. This is invalid: the antipodal mate in $Q_d$ of an edge in that face lies in $x_1=1$. The original condition imposes no relation between edges paired by the internal antipodal map of the first face. In particular an arbitrary colouring of its internal edges can be completed on the opposite face by reflection with reversed colours. Thus the induction hypothesis is not available on the chosen face.

Verification and exact remaining task.

A direct exhaustive check represented vertices as bit strings, chose one colour for each antipodal edge pair, and searched red components for a pair $v,v\mathbin{\mathrm{xor}}(2^d-1)$. There are $d2^{d-2}$ independent edge-pair choices. All $4$, $64$, and $65536$ colourings for $d=2,3,4$ passed. Testing red alone is sufficient: reflection turns any blue antipodal path into a red one. These finite checks confirm the conventions; they cannot establish arbitrary $d$. The independent work here still lacks a general existence argument for a one-switch path, or a complete verification of [S3]'s alternative chain obstruction.

Reproduction of finite checks.

The finite checks stated above were run with Python 3 using the repository script [C1]. They verify the stated examples and finite ranges only.

Final status

UNRESOLVED as an independent full proof attempt. The elementary reduction and small cases are verified; a claimed full solution is explicitly credited to [S3]. This file does not reclassify that claim as an original model solution or certify its entire proof.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3072 (OPG-2359), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Edge-antipodal colorings of cubes. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/edge_antipodal_colorings_of_cubes.
• S3 H. Wu and N. Yang, A Chain-Level Borsuk--Ulam Obstruction Proof of Norine's Antipodal-Coloring Conjecture, arXiv:2607.19276v1, 21 July 2026. Source of the announced-proof qualification; checked 1 October 2026. https://arxiv.org/html/2607.19276v1.
• S4 D. B. West and J. I. Wise, Antipodal edge-colorings of hypercubes, author manuscript revised July 2017. Checked 1 October 2026. https://dwest.web.illinois.edu/pubs/antip.pdf.
• C1 Reproducible finite-check code, executed 1 October 2026 with Python 3 (standard library only): scripts/check_attempt_batch_geometry_2026_10_01.py.