A short proof of the middle levels theorem

DOI10.19086/DA.3659MaRDI QIDQ4645033zbMATH OpenOpenAlexWikidataFDO

Authors Petr Gregor, Torsten Mütze, Jerri Nummenpalo

Publication date 9 January 2019

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Abstract: Consider the graph that has as vertices all bitstrings of length $2n+1$ with exactly $n$ or $n+1$ entries equal to 1, and an edge between any two bitstrings that differ in exactly one bit. The well-known middle levels conjecture asserts that this graph has a Hamilton cycle for any $ngeq1$. In this paper we present a new proof of this conjecture, which is much shorter and more accessible than the original proof.

Recommendations

• Proof of the middle levels conjecture
• An update on the middle levels problem
• On generalized middle-level problem
• The antipodal layers problem
• A note on the middle levels problem

Cites work

• A constant-time algorithm for middle levels Gray codes
• A minimum-change version of the Chung-Feller theorem for Dyck paths
• An explicit 1-factorization in the middle of the Boolean lattice
• Bipartite Kneser graphs are Hamiltonian
• Catalan Numbers
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• Explicit matchings in the middle levels of the Boolean lattice
• Gray codes with restricted density
• scientific article; zbMATH DE number 3838053 (Why is no real title available?)
• scientific article; zbMATH DE number 2050057 (Why is no real title available?)
• scientific article; zbMATH DE number 866658 (Why is no real title available?)
• Long cycles in the middle two layers of the discrete cube
• Magical mathematics. The mathematical ideas that animate great magic tricks. With a foreword by Martin Gardner
• Monotone Gray codes and the middle levels problem
• Probabilistic combinatorics and the recent work of Peter Keevash
• Proof of the middle levels conjecture
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Trimming and gluing Gray codes

Cited in

(24)

• Explicit \(\Delta \)-edge-coloring of consecutive levels in a divisor lattice
• Gray codes and symmetric chains
• A constant-time algorithm for middle levels Gray codes
• On orthogonal symmetric chain decompositions
• On the central levels problem
• Proof of the middle levels conjecture
• A simple proof of a theorem on complements of middle graphs
• A numeral system for the middle-levels graphs
• 2-Factors without close edges in the n-dimensional cube
• Gray codes and symmetric chains
• Sparse Kneser graphs are Hamiltonian
• On a combinatorial generation problem of Knuth
• Rainbow cycles in flip graphs
• Rainbow cycles in flip graphs
• On 1-factorizations of bipartite Kneser graphs
• A local injective proof of log-concavity for increasing spanning forests
• Star transposition Gray codes for multiset permutations
• A book proof of the middle levels theorem
• Kneser graphs are Hamiltonian
• On orthogonal symmetric chain decompositions
• On the central levels problem
• Kneser graphs are Hamiltonian (extended abstract)
• Kneser graphs are Hamiltonian
• One sequence to rule them all: \( \mathcal{O}(1)\)-time parallel generation of mixed-radix Gray codes

This page was built for publication: A short 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 Q4645033)