A 3-semi-perfect 1-factorization of the six-dimensional hypercube

2026/07/17 by Guillaume Lambard
Mathematics · #math.CO

paper · pdf

Abstract

For a 1-factorization F=\M₁,…,M_d\ of the hypercube Q_d, let G[F] have vertex set F, with M_iM_j an edge exactly when M_i∪ M_j is a Hamilton cycle. Behague proved that Q_k+ℓ has a 1-factorization F with G[F]≅ K_k,ℓ for all positive k,ℓ except possibly k=ℓ=3. We give an explicit 1-factorization of Q₆ for which G[F]≅ K_3,3, resolving the exceptional case. The construction is supplied as a finite certificate. Its correctness can be checked directly from the tables in the paper or by either of two independent, short, standard-library verifiers supplied with the certificate.

Related

• Connecting hypercube 1-factors
• A book proof of the middle levels theorem
• Perfect 1-factorisations of K_11,11
• Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions
• Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case