A book proof of the middle levels theorem

DOI10.1007/S00493-023-00070-3MaRDI QIDQ6126419zbMATH OpenOpenAlexFDO

Authors Torsten Mütze

Publication date 9 April 2024

Published in Combinatorica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2306.13019

zbMATH Keywords

Hamilton cyclehypercubemiddle levels conjecture

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: We give a short constructive proof for the existence of a Hamilton cycle in the subgraph of the $(2n+1)$-dimensional hypercube induced by all vertices with exactly $n$ or $n+1$ many 1s.

Recommendations

• A short proof of the middle levels theorem
• Proof of the middle levels conjecture
• On the central levels problem
• On generalized middle-level problem
• An update on the middle levels problem

Cited in

(3)

• Skipping ropes: an efficient gray code algorithm for generating wiggly permutations
• Hamiltonian connectivity of some base-cobase graphs
• One sequence to rule them all: \( \mathcal{O}(1)\)-time parallel generation of mixed-radix Gray codes

This page was built for publication: A book proof of the middle levels theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126419)