标题： 连接超立方体1-因子 显示英文标题

标题： Connecting hypercube 1-factors

摘要： 一个正则图 $G$ 的1-分解是将其边集 $E(G)$ 分解为 $G$ 的完美匹配。 Behague要求最小的$r=r(d)$，使得某些$1$-分解的$d$维超立方体$Q_d$具有这样的性质：其任何$r$个1-因子的并集是连通的。 之前Laufer关于完美$1$-因子分解的工作表明，$r$至少为三，并且 Behague给出了一个具有$r=\big\lceil\frac{d}{2}\big\rceil+1$的构造。 我们改进了这个上界，给出了一个具有$r=O(\log d)$的随机构造。 换句话说，我们证明了超立方体$Q_d$的 1-分解$\mathcal{M} = \{M_1,\dotsc,M_d\}$的存在，使得每个大小为$\Omega(\log d)$的$\mathcal{N}\subseteq \mathcal{M}$都满足$\bigcup \mathcal{N}$是连通的。 显示英文摘要

摘要： 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=\big\lceil\frac{d}{2}\big\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,\dotsc,M_d\}$ of the hypercube $Q_d$ such that every $\mathcal{N}\subseteq \mathcal{M}$ of size $\Omega(\log d)$ is such that $\bigcup \mathcal{N}$ is connected.