Department of
Applied
Mathematics

Perfect Matchings Extend to Hamilton Cycles in Hypercubes

Jiří Fink

Abstract

Kreweras' conjecture asserts that any perfect matching of the hypercube Q_d (d >= 2) can be extended to a Hamilton cycle. We proved this conjecture. The proof is very nice and elegant and I will present it.

It is well known that Q_d is hamiltonian for every d >= 2. This statement can be traced back to 1872. Since then the research on Hamilton cycles in hypercubes satisfying certain additional properties has received considerable attention. An interested reader can find more details about this topic in the survey of Savage, e.g. Dvořák showed that any set of at most 2d-3 edges of Q_d (d >= 2) that induces vertex-disjoint paths is contained in a Hamilton cycle. Dimitrov and Škrekovski proved that for every perfect matching P of Q_d (d >= 3) there exists a Hamilton cycle that faults P, if and only if P is not a layer of Q_d.