pith. sign in

arxiv: 2605.20184 · v3 · pith:ZJ4RP26Anew · submitted 2026-05-19 · 🧮 math.CO

Hypercube geodesics with few colour changes

Lawrence Hollom This is my paper

Pith reviewed 2026-06-30 18:05 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypercube2-edge-coloringgeodesicscolor changesantipodal pathsprobabilistic method
1
0 comments X

The pith

Any 2-edge-coloring of the n-dimensional hypercube admits a geodesic from some vertex to its antipode with at most (π/2 + o(1))√n color changes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper improves the upper bound on the worst-case number of color changes along an antipodal geodesic in a 2-edge-colored hypercube. Previous results gave a linear bound in n; the new result shows the number is at most roughly 1.57 times the square root of n. The proof proceeds by averaging the number of color changes over all possible starting vertices, showing the expectation is small regardless of how the edges are colored. This matters for understanding the structure of colored hypercubes and moves closer to resolving whether a single color change always suffices.

Core claim

We improve this bound and answer a question of Leader and Long by finding a geodesic path with at most (π/2 + o(1))√n colour changes. In fact, we show that this is the expected number of colour changes for a uniformly random start vertex. This is optimal (up to the constant) when the start vertex is chosen uniformly at random.

What carries the argument

The averaging argument over a uniformly random starting vertex that bounds the expected colour changes independently of the edge colouring.

If this is right

  • Improves the best known upper bound from (5/16 + o(1))n to (π/2 + o(1))√n.
  • Shows the bound is asymptotically tight up to the multiplicative constant for random starting vertices.
  • Provides a positive resolution to the question posed by Leader and Long.
  • Narrows the gap toward Norine's conjecture that the maximum is 1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The random-vertex averaging could be derandomized to produce an explicit vertex achieving the bound.
  • The constant π/2 likely arises from an integral over transition probabilities in the analysis of successive edge colors.

Load-bearing premise

The averaging argument over random starting vertices produces an expectation bounded by (π/2 + o(1))√n independently of the particular 2-coloring.

What would settle it

A specific 2-edge-coloring of the hypercube in which the average over vertices v of the number of colour changes on geodesics from v to its antipode exceeds (π/2 + ε)√n for some fixed ε > 0.

Figures

Figures reproduced from arXiv: 2605.20184 by Lawrence Hollom.

Figure 1
Figure 1. Figure 1: A pictorial representation of the functions [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
read the original abstract

What is the maximum, over all 2-colourings of the edges of the $n$-dimensional hypercube $Q_n$, of the minimal number of times a path between a vertex $v$ and its antipode $\bar{v}$ changes colour? A conjecture of Norine, in a form due to Feder and Subi, states that this maximum should be 1. The previous best-known upper bound on the number of colour changes was $(\tfrac{5}{16} + o(1))n$ due to Kirchweger, Peitl, Subercaseaux, and Szeider. We improve this bound and answer a question of Leader and Long by finding a geodesic path with at most $(\tfrac{\pi}{2} + o(1))\sqrt{n}$ colour changes. In fact, we show that this is the expected number of colour changes for a uniformly random start vertex. This is optimal (up to the constant) when the start vertex is chosen uniformly at random.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript studies the maximum, over all 2-edge-colorings of the hypercube Q_n, of the minimum number of color changes along any geodesic from a vertex v to its antipode. It proves that when v is chosen uniformly at random, the expected value of this minimum is at most (π/2 + o(1)) √n for any coloring, and that this is asymptotically tight. This answers a question posed by Leader and Long.

Significance. If the averaging argument holds, the result gives an optimal (up to constant) sublinear bound on the expected minimum color changes for random starting vertices. This improves the prior linear bound in the random-start setting and provides a geometric/averaging technique that may be of independent interest for hypercube path problems.

major comments (1)
  1. [Abstract] Abstract: The manuscript opens by defining the quantity whose maximum over colorings is conjectured (Norine/Feder-Subi) to be 1 and whose prior upper bound is (5/16 + o(1))n; it then states that the new work improves this bound to (π/2 + o(1))√n. However, the proved statement is only that E_v[min color changes] ≤ (π/2 + o(1))√n for uniform random v. Because min_v ≤ E_v always holds but the original quantity is the value at a fixed v, the result does not improve the upper bound on the quantity defined in the first paragraph (or on the fixed-v version of the Leader-Long question).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to clarify the distinction between the worst-case and average-case quantities in the abstract. We address the comment below and will make the corresponding revision.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The manuscript opens by defining the quantity whose maximum over colorings is conjectured (Norine/Feder-Subi) to be 1 and whose prior upper bound is (5/16 + o(1))n; it then states that the new work improves this bound to (π/2 + o(1))√n. However, the proved statement is only that E_v[min color changes] ≤ (π/2 + o(1))√n for uniform random v. Because min_v ≤ E_v always holds but the original quantity is the value at a fixed v, the result does not improve the upper bound on the quantity defined in the first paragraph (or on the fixed-v version of the Leader-Long question).

    Authors: We agree that the abstract phrasing could be read as claiming an improvement on the worst-case (max over colorings of min over paths for fixed v) quantity, which would be incorrect. Our main theorem establishes only the bound on the expectation E_v[min color changes] ≤ (π/2 + o(1))√n for any 2-edge-coloring. This is the precise setting of the Leader-Long question referenced in the referee summary, and the result is asymptotically tight in that random-start model. The earlier (5/16 + o(1))n bound applied to the worst-case v; our contribution is the sublinear average-case bound together with the geometric averaging technique. We will revise the abstract to state explicitly that the new bound holds in expectation over uniform random v, that this answers the Leader-Long question, and that we make no claim about the fixed-v worst-case quantity or the Norine/Feder-Subi conjecture. revision: yes

Circularity Check

0 steps flagged

No circularity; bound obtained via averaging and hypercube geometry

full rationale

The derivation relies on an explicit averaging argument over uniformly random vertices v, showing that for any 2-edge-coloring the expected minimum color changes along a geodesic from v to its antipode is at most (π/2 + o(1))√n. This expectation is computed directly from the hypercube's coordinate structure and does not reduce to a fitted parameter, self-definition, or self-citation chain. The optimality statement is restricted to the random-start distribution and follows from the same averaging, without importing uniqueness theorems or renaming prior empirical patterns. The central claim therefore remains independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of the hypercube graph and the notion of a geodesic; no free parameters, ad-hoc axioms, or invented entities are introduced or fitted in the abstract.

axioms (2)
  • standard math The n-dimensional hypercube Q_n is the graph with vertex set {0,1}^n and edges between vertices of Hamming distance 1.
    Standard definition invoked by the problem statement.
  • standard math The antipode of a vertex v is the unique vertex at Hamming distance n obtained by flipping all coordinates.
    Standard definition used throughout the abstract.

pith-pipeline@v0.9.1-grok · 5691 in / 1604 out tokens · 45956 ms · 2026-06-30T18:05:18.422389+00:00 · methodology

Review history (3 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 3 canonical work pages

  1. [1]

    N. Alon, R. Radoičić, B. Sudakov, and J. Vondrák. A Ramsey-type result for the hypercube. Journal of Graph Theory, 53(3):196–208, 2006

    2006

  2. [2]

    A collection of open problems in celebration of

    R. Baber, N. Behague, A. Calbet, D. Ellis, J. Erde, R. Gray, M.-R. Ivan, B. Janzer, R. John- son, L. Milićević, J. Talbot, T. S. Tan, and B. Wickes. A collection of open problems in celebration of Imre Leader’s 60th birthday.arXiv preprint arXiv:2310.18163, 2023

    work page arXiv 2023

  3. [3]

    Duckworth, P

    W. Duckworth, P. E. Dunne, A. M. Gibbons, and M. Zito. Leafy spanning trees in hyper- cubes.Applied Mathematics Letters, 14(7):801–804, 2001

    2001

  4. [4]

    V. Dvořák. A note on Norine’s antipodal-colouring conjecture.The Electronic Journal of Combinatorics, 27, article P2.26, 2020

    2020

  5. [5]

    Onhypercubelabellingsandantipodalmonochromaticpaths.Discrete Applied Mathematics, 161(10-11):1421–1426, 2013

    T.FederandC.Subi. Onhypercubelabellingsandantipodalmonochromaticpaths.Discrete Applied Mathematics, 161(10-11):1421–1426, 2013

    2013

  6. [6]

    Frankston and D

    K. Frankston and D. Scheinerman. Proving Norine’s conjecture holds forn= 7via SAT solvers.arXiv preprint arXiv:2408.02474, 2024

    work page arXiv 2024

  7. [7]

    arXiv preprint arXiv:2511.08386 , year =

    M. Kirchweger, T. Peitl, B. Subercaseaux, and S. Szeider. From the finite to the infinite: sharper asymptotic bounds on Norin’s conjecture via SAT.arXiv preprint arXiv:2511.08386, 2025

    work page arXiv 2025

  8. [8]

    Leader and E

    I. Leader and E. Long. Long geodesics in subgraphs of the cube.Discrete Mathematics, 326:29–33, 2014

    2014

  9. [9]

    E. Long. Long paths and cycles in subgraphs of the cube.Combinatorica, 33(4):395–428, 2013

    2013

  10. [10]

    S. Norine. Edge-antipodal colorings of cubes. Open Problem Garden.http:// www.openproblemgarden.org/op/edge_antipodal_colorings_of_cubes, 2008. Accessed: 2026-05-08

    2008

  11. [11]

    D. B. West and J. I. Wise. Antipodal edge-colorings of hypercubes.Discussiones Mathe- maticae Graph Theory, 39(1):271–284, 2018

    2018

  12. [12]

    Zulkoski, C

    E. Zulkoski, C. Bright, A. Heinle, I. Kotsireas, K. Czarnecki, and V. Ganesh. Combining SAT solvers with computer algebra systems to verify combinatorial conjectures.Journal of Automated Reasoning, 58(3):313–339, 2017. 8

    2017