The symmetric chain decomposition extension conjecture for hypercubes
The symmetric chain decomposition extension conjecture for hypercubes
A symmetric chain decomposition (SCD) of the hypercube is a partition of its vertices into symmetric chains, where a symmetric chain is a path such that lies at level for every . The symmetric chain decomposition extension conjecture. Every SCD can be extended to a Hamilton cycle in . This conjecture extends results of Streib and Trotter and the Greene–Kleitman construction, which show that particular SCDs can be extended to Hamilton cycles. It is motivated by the conjecture of Ruskey and Savage that every matching in extends to a Hamilton cycle.
Sources & referencesView supporting material
Primary source
Petr Gregor, Ondřej Mička and Torsten Mütze, “On the central levels problem”, arXiv:1912.01566 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.