The symmetric chain decomposition extension conjecture for hypercubes

A symmetric chain decomposition (SCD) of the hypercube QnQ_n is a partition of its vertices into symmetric chains, where a symmetric chain is a path (xk,xk+1,,xnk)(x_k,x_{k+1},\ldots,x_{n-k}) such that xix_i lies at level ii for every kinkk\leq i\leq n-k. The symmetric chain decomposition extension conjecture. Every SCD can be extended to a Hamilton cycle in QnQ_n. 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 QnQ_n 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.