Connecting hypercube 1-factors

Lawrence Hollom, Benedict Randall Shaw · 2025

Read Connecting hypercube 1-factors by Lawrence Hollom, Benedict Randall Shaw (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-15698.txt.

Introduction

Lawrence Hollom and Benedict Randall Shaw solve a puzzle about splitting the edges of a hypercube into perfect matchings. A hypercube links points that differ in one coordinate, and a perfect matching pairs up all its points. A past question asked how few matchings must be joined before their union forms one connected web. Their 2025 work tightens the known bounds on that number.

Older work showed at least three matchings are needed, and a hand-built design reached about half the dimension plus one. The pair use a random method to do far better. Their bound grows only with the log of the dimension, which is much slower. In other words, a modest set of matchings, chosen the right way, already ties the whole cube together.

Catalog record

CREATORLawrence Hollom, Benedict Randall Shaw
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-15698

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Connecting hypercube 1-factors Lawrence Hollom, Benedict Randall Shaw Abstract A 1-factorisation of a regular graph G G is a partition of its edge set E ⁡ ( G ) E(G) into perfect matchings of G G . Behague asked for the minimal r = r ⁡ ( d ) r=r(d) such that some 1 1 -factorisation of the d d -dimensional hypercube Q d Q_{d} has the property that the union of any r r of its 1-factors is connected. Previous work by Laufer on perfect 1 1 -factorisations implied that r r is at least three, and Behague gave a construction with r = ⌈ d 2 ⌉ + 1 r=\big\lceil\frac{d}{2}\big\rceil+1 . We improve this upper bound, giving a random construction with r = O ⁡ ( log ⁡ d ) r=O(\log d) . In other words, we prove the existence of a 1-factorisation ℳ = { M 1 , … , M d } \mathcal{M}=\{M_{1},\dotsc,M_{d}\} of the hypercube Q d Q_{d} such that every 𝒩 ⊆ ℳ \mathcal{N}\subseteq\mathcal{M} of size Ω ⁡ ( log ⁡ d ) \Omega(\log d) is such that ⋃ 𝒩 \bigcup\mathcal{N} is connected. largesymbols”0C 1 Introduction A 1-factorisation of a graph G is a partition \mathcal{M}=\{M_{1},\dotsc,M_{k}\} of its edge-set into perfect matchings. That is, each M_{i} is a perfect matching of G and E(G)=\bigcup_{i=1}^{k}M_{i} . Of particular interest are perfect 1-factorisations—those where, for every pair of matchings M_{i},M_{j}\in\mathcal{M} , their union M_{i}\mathbin{\cup}M_{j} forms a Hamilton cycle. Indeed, it is a long-standing conjecture of Kotzig [ 7 ] that the complete graph K_{2n} always has a perfect 1-factorisation. This is known when n or 2n-1 are prime [ 1 , 7 ] , as well as for finitely many other values of n (see [ 10 ] and the references therein). In particular, cases as small as K_{64} remain open. 1-factorisations of the hypercube Q_{d} have also received significant attention. However, it is known that a 1-factorisation of Q_{d} cannot be perfect, as shown by Laufer [ 9 ] . One may note that a 1 -factorisation is perfect if and only if the union of any two of its 1 -factors is connected. This led Behague [ 3 ] to ask the following question, later repeated in the collection [ 2 ] . Question 1.1 ( [ 3 ] ) . For each d\in\mathbb{N} with d\geq 3 , let r=r(d) be the minimal positive integer such that there exists a 1-factorization \mathcal{M} of Q_{d} where the union of any r distinct 1-factors is connected. What is the value of r(d) ? The best known upper bound on r(d) was \lceil d/2\rceil+1 , proven by Behague [ 3 ] . Our main result is the following theorem, which significantly improves the upper bound on r(d) . Theorem 1.2 . The value r(d) is bounded above by O(\log d) . More precisely, there are constants d_{0} and c such that the following holds. For every d\in\mathbb{N} with d\geq d_{0} , there is a 1-factorisation \mathcal{M} of Q_{d} such that, for any \mathcal{N}\subseteq\mathcal{M} with \lvert\mathcal{N}\rvert\geq c\log_{2}d , the union \bigcup\mathcal{N} is connected. In fact, we can take d_{0}=3000 and c=45 . We note in particular that our proof gives a polynomial time randomised algorithm for constructing (with high probability) such a 1-factorisation. The lack of a perfect 1-factorisation of Q_{d} has led to the study of which weaker conditions we can insist that \mathcal{M} satisfies. In fact, Laufer also showed a more detailed result—that, if H is the graph on \mathcal{M} formed by connecting M_{i} and M_{j} iff M_{i}\mathbin{\cup}M_{j} is a Hamilton cycle, then H is bipartite. A 1 -factorisation \mathcal{M} is called semi-perfect if some matching M_{1} has the property that M_{1}\cup M_{i} is a Hamilton cycle for all other M_{i} —or equivalently, if H is the star graph of order n . Craft 1 1 1 Previous papers on this problem [ 3 , 6 ] attribute this conjecture to Craft, citing a webpage of Archdeacon titled “Problems in Topological Graph Theory,” of which no surviving copy containing a reference to the conjecture on semi-perfect 1 -factorisations could be found. conjectured that, for d\geq 2 , the hypercube Q_{d} has a semi-perfect 1 -factorisation. Královič and Královič [ 8 ] and Gochev and Gotchev [ 6 ] each proved this for odd d , and Chitra and Muthusamy [ 4 ] proved the full conjecture. Gochev and Gotchev also introduced the notion of k - semi-perfect 1-factorisations, those for which the graph H is K_{k,d-k} , and proved these exist for k,d even. Behague [ 3 ] went further, proving that for each k<d , the hypercube Q_{d} admits a k -semi-perfect 1 -factorisation. Setting k=\big\lfloor\frac{d}{2}\big\rfloor gives a 1 -factorisation in which any \lceil d/2\rceil+1 matchings must contain two whose union is connected, giving the previous upper bound on r(d) . In Section 1.1 , we outline our proof of Theorem 1.2 . In Section 1.2 , we collect some preliminary results on the Chernoff bound and on Hamming codes, both of which we will use in Section 2 , in which we present our proof of Theorem 1.2 . Finally, in Section 3 we give some concluding remarks and conjecture the value of r for the uniform random 1 -factorisation of Q_{d} . 1.1 Proof outline Consider the 1 -factorisation given by the directional matchings : the set of matchings of the form M_{x} , where M_{x} is the set of edges in direction x . We can see that the union of any two directional matchings is a disjoint union of 4 -cycles, and likewise that the union of any r directional matchings is a disjoint union of ‘small cubes’—copies of Q_{r} . In particular, for r<d , this is certainly not connected. Our aim will be to make a large number of random local perturbations to these directional matchings in such a way that the union of any r matchings is connected with very high probability—indeed, high enough probability to beat a union bound over all d\choose r possible sets of r matchings. We begin by choosing a large number of points of Q_{d} around which to make these small perturbations—in fact we will take most points of a particular Hamming code C on Q_{d} (reserving some space to later make larger perturbations). This gives a well-behaved, fairly dense set of vertices. Our perturbation at each vertex will simply swap the edges of a random square around that vertex between two matchings. The fact that any two vertices in the code are at distance at least 3 will be enough to guarantee that usually these perturbations are compatible—if not, we will ignore the perturbation. We will also make some larger perturbations, swapping within a 6 -cube instead, at an exponentially small proportion of vertices—these will be few enough that we can simply choose not to make any other swaps near them. In fact each ‘small cube’ is quite well connected, as it is a copy of Q_{r} . Our first step will be to show that it is sufficiently well-connected that, even after our perturbations, each small cube is still connected in the union of our r perturbed matchings. Indeed, we show

Read the complete text