Connecting hypercube 1-factors

Abstract

A 1-factorisation of a regular graph $G$ is a partition of its edge set $E(G)$ into perfect matchings of $G$. Behague asked for the minimal $r=r(d)$ such that some $1$-factorisation of the $d$-dimensional hypercube $Q_d$ has the property that the union of any $r$ of its 1-factors is connected. Previous work by Laufer on perfect $1$-factorisations implied that $r$ is at least three, and Behague gave a construction with $r=\lceil \frac{d}{2}\rceil +1$. We improve this upper bound, giving a random construction with $r=O(\log d)$. In other words, we prove the existence of a 1-factorisation $\mathcal{M}=\{M_1,\dots ,M_d\}$ of the hypercube $Q_d$ such that every $\mathcal{N}\subseteq \mathcal{M}$ of size $\hat{I}\text{c◯}(\log d)$ is such that $\bigcup \mathcal{N}$ is connected.

14 pages