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.
| Comments: | 8 pages, 1 figure |
| Subjects: | Combinatorics (math.CO) |
| Cite as: | arXiv:2605.20184 [math.CO] |
| (or arXiv:2605.20184v2 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.20184 arXiv-issued DOI via DataCite |
From: Lawrence Hollom [view email]
[v1]
Tue, 19 May 2026 17:59:50 UTC (13 KB)
[v2]
Fri, 22 May 2026 15:35:25 UTC (14 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。