Proof of the middle levels conjecture
From MaRDI portal
Publication:2809275
Abstract: Define the middle layer graph as the graph whose vertex set consists of all bitstrings of length that have exactly or 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 . 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 different Hamilton cycles in the middle layer graph, which is best possible.
Recommendations
Cites work
- scientific article; zbMATH DE number 2059939 (Why is no real title available?)
- scientific article; zbMATH DE number 1439443 (Why is no real title available?)
- A Survey of Combinatorial Gray Codes
- An explicit 1-factorization in the middle of the Boolean lattice
- An inductive construction for Hamilton cycles in Kneser graphs
- An update on the middle levels problem
- Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
- Construction of 2-factors in the middle layer of the discrete cube
- Explicit matchings in the middle levels of the Boolean lattice
- Gray codes with restricted density
- Hamilton cycles and paths in vertex-transitive graphs-current directions
- Hamiltonian paths in Cayley graphs
- Kneser's conjecture, chromatic number, and homotopy
- Lexicographic matchings cannot form Hamiltonian cycles
- Long cycles in the middle two layers of the discrete cube
- Monotone Gray codes and the middle levels problem
- On generalized middle-level problem
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- The prism over the middle-levels graph is Hamiltonian
- Triangle-free Hamiltonian Kneser graphs
Cited in
(42)- Orthogonal Symmetric Chain Decompositions of Hypercubes
- A book proof of the middle levels theorem
- Hamiltonian cycle enumeration via fermion-zeon convolution
- Space-optimal quasi-Gray codes with logarithmic read complexity
- Long cycles in the middle two layers of the discrete cube
- On a combinatorial generation problem of Knuth
- Probabilistic combinatorics and the recent work of Peter Keevash
- 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 note on the middle levels 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
- Construction of 2-factors in the middle layer of the discrete cube
- Sparse Kneser graphs are Hamiltonian
- Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle
- On the spectrum of the middle-cube
- Explicit \(\Delta \)-edge-coloring of consecutive levels in a divisor lattice
- Kneser graphs are Hamiltonian
- 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.
- Towards a problem of Ruskey and Savage on matching extendability
- On orthogonal symmetric chain decompositions
- Trimming and gluing Gray codes
- On 1-factorizations of bipartite Kneser graphs
- On the central levels problem
- On prism-Hamiltonian bipartite graphs
- 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
- Inside the binary reflected gray code: flip-swap languages in 2-gray code order
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)
