Pith. sign in

REVIEW 1 major objections 3 cited by

Hypercube geodesics with few colour changes

T0 review · 1 major / 0 minor · reviewed 2026-06-30 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict Paper improves expected color changes over random vertices to O(sqrt n) but does not tighten the fixed-vertex bound that the Norine conjecture actually concerns. read the letter →

arxiv 2605.20184 v3 pith:ZJ4RP26A submitted 2026-05-19 math.CO

Lawrence Hollom This is my paper · ORCID
classification math.CO
keywords hypercube2-edge-coloringgeodesicscolorchangesantipodalpathsprobabilisticmethod
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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

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.

Watch

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 2 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hypercube geodesics with few colour changes." pith.science (2026). https://pith.science/paper/ZJ4RP26A

@misc{pith2026260520184,
  author       = {Pith},
  title        = {Pith review of: Hypercube geodesics with few colour changes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZJ4RP26A}},
  note         = {Machine review of arXiv:2605.20184}
}
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.

Figures

Figures reproduced from arXiv: 2605.20184 by the authors.

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

Review history (3 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    math.CO 2026-07 accept novelty 8.0 of 10

    Norine's conjecture is proved: every antipodal red-blue edge-coloring of the hypercube Q_n (n≥2) has a monochromatic path from a vertex to its antipode.

  2. Monochromatic Paths and a Topological Approach to Norine's Conjecture

    math.CO 2026-06 unverdicted novelty 7.0 of 10

    Proves a topological criterion for monochromatic antipodal paths in centrally symmetric simply connected 2-complexes and uses it to verify Norine's conjecture for classes of 2-edge-colored hypercubes obtained by symme...

  3. Antipodal paths in covers of spheres

    math.AT 2026-07 accept novelty 6.0 of 10

    For n≥2k−2, every open cover of S^n by k sets forces one set to contain a path between antipodal points; the bound is sharp.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · cited by 3 Pith papers

  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

    work page 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

    work page 2001

  4. [4]

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

    work page 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

    work page 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

    work page 2014

Show all 12 references
  1. [9]

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

    2013

  2. [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

  3. [11]

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

    2018

  4. [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

Pith tools

Reviewed June 30, 2026 · model on record in the stance chip above.