Proof of the middle levels conjecture

DOI10.1112/PLMS/PDW004zbMATH Open1336.05082arXiv1404.4442OpenAlexW3100954633WikidataQ64012489 ScholiaQ64012489MaRDI QIDQ2809275FDOQ2809275

Authors: Torsten Mütze 

Publication date: 27 May 2016

Published in: Proceedings of the London Mathematical Society. Third Series (Search for Journal in Brave)

Abstract: Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length $2n+1$ that have exactly $n$ or $n+1$ entries equal to 1, with an edge between any two vertices for which the corresponding bitstrings differ in exactly one bit. The middle levels conjecture asserts that this graph has a Hamilton cycle for every $ngeq1$. This conjecture originated probably with Havel, Buck and Wiedemann, but has also been attributed to Dejter, ErdH{o}s, Trotter and various others, and despite considerable efforts it remained open during the last 30 years. In this paper we prove the middle levels conjecture. In fact, we construct $2^{2^{Omega(n)}}$ different Hamilton cycles in the middle layer graph, which is best possible.

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

Recommendations

• A short proof of the middle levels theorem
• An update on the middle levels problem
• On generalized middle-level problem
• The antipodal layers problem
• scientific article; zbMATH DE number 1439443

zbMATH Keywords

middle layer graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Combinatorial codes (94B25)

Cites Work

• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Kneser's conjecture, chromatic number, and homotopy
• An update on the middle levels problem
• An explicit 1-factorization in the middle of the Boolean lattice
• Triangle-free Hamiltonian Kneser graphs
• The prism over the middle-levels graph is Hamiltonian
• A Survey of Combinatorial Gray Codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• An inductive construction for Hamilton cycles in Kneser graphs
• Hamiltonian paths in Cayley graphs
• Monotone Gray codes and the middle levels problem
• Long cycles in the middle two layers of the discrete cube
• Hamilton cycles and paths in vertex-transitive graphs-current directions
• Gray codes with restricted density
• Lexicographic matchings cannot form Hamiltonian cycles
• Explicit matchings in the middle levels of the Boolean lattice
• Construction of 2-factors in the middle layer of the discrete cube
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• On generalized middle-level problem

Cited In (42)

• Space-optimal quasi-Gray codes with logarithmic read complexity
• Hamiltonian cycle enumeration via fermion-zeon convolution
• On a combinatorial generation problem of Knuth
• Probabilistic combinatorics and the recent work of Peter Keevash
• Long cycles in the middle two layers of the discrete cube
• Flip-swap languages in binary reflected Gray code order
• On the hardness of Gray code problems for combinatorial objects
• Disproving the Single Level Conjecture
• Efficient Computation of Middle Levels Gray Codes
• On generalized middle-level problem
• A minimum-change version of the Chung-Feller theorem for Dyck paths
• A minimum-change version of the Chung-Feller theorem for Dyck paths
• A note on the middle levels problem
• Sparse Kneser graphs are Hamiltonian
• Construction of 2-factors in the middle layer of the discrete cube
• Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle
• On the spectrum of the middle-cube
• Kneser graphs are Hamiltonian
• Explicit \(\Delta \)-edge-coloring of consecutive levels in a divisor lattice
• An update on the middle levels problem
• Graphs whose Kronecker covers are bipartite Kneser graphs
• Star transposition Gray codes for multiset permutations
• A numeral system for the middle-levels graphs
• Packings in bipartite prisms and hypercubes
• On Hamilton cycles in highly symmetric graphs
• Rainbow cycles in flip graphs
• Rainbow cycles in flip graphs
• Gray codes and symmetric chains
• Gray codes and symmetric chains
• Hamiltonian cycles and symmetric chains in Boolean lattices.
• On orthogonal symmetric chain decompositions
• Towards a problem of Ruskey and Savage on matching extendability
• On 1-factorizations of bipartite Kneser graphs
• Trimming and gluing Gray codes
• On prism-Hamiltonian bipartite graphs
• On the central levels problem
• A constant-time algorithm for middle levels Gray codes
• Extending perfect matchings to Gray codes with prescribed ends
• A short proof of the middle levels theorem
• Orthogonal Symmetric Chain Decompositions of Hypercubes
• Inside the binary reflected gray code: flip-swap languages in 2-gray code order
• A book proof of the middle levels theorem

Uses Software

• OEIS

This page was built for publication: Proof of the middle levels conjecture

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