Proof of the middle levels conjecture

DOI10.1112/PLMS/PDW004zbMath1336.05082arXiv1404.4442OpenAlexW3100954633WikidataQ64012489 ScholiaQ64012489MaRDI QIDQ2809275

Torsten Mütze

Publication date: 27 May 2016

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

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

zbMATH Keywords

middle layer graph

Mathematics Subject Classification ID

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

Related Items (29)

Inside the binary reflected gray code: flip-swap languages in 2-gray code order ⋮ Efficient Computation of Middle Levels Gray Codes ⋮ Probabilistic combinatorics and the recent work of Peter Keevash ⋮ Extending perfect matchings to Gray codes with prescribed ends ⋮ On a Combinatorial Generation Problem of Knuth ⋮ Graphs whose Kronecker covers are bipartite Kneser graphs ⋮ Flip-swap languages in binary reflected Gray code order ⋮ Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle ⋮ Star transposition Gray codes for multiset permutations ⋮ Towards a problem of Ruskey and Savage on matching extendability ⋮ Trimming and gluing Gray codes ⋮ Unnamed Item ⋮ Packings in bipartite prisms and hypercubes ⋮ On the central levels problem ⋮ Unnamed Item ⋮ Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity ⋮ A short proof of the middle levels theorem ⋮ Hamiltonian cycle enumeration via fermion-zeon convolution ⋮ A minimum-change version of the Chung-Feller theorem for Dyck paths ⋮ Explicit \(\Delta \)-edge-coloring of consecutive levels in a divisor lattice ⋮ A numeral system for the middle-levels graphs ⋮ Rainbow Cycles in Flip Graphs ⋮ On 1-factorizations of bipartite Kneser graphs ⋮ A constant-time algorithm for middle levels Gray codes ⋮ Orthogonal Symmetric Chain Decompositions of Hypercubes ⋮ Gray codes and symmetric chains ⋮ A minimum-change version of the Chung-Feller theorem for Dyck paths ⋮ Rainbow Cycles in Flip Graphs. ⋮ Sparse Kneser graphs are Hamiltonian

Uses Software

• OEIS

Cites Work

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

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