A short proof of the middle levels theorem

DOI10.19086/DA.3659zbMATH Open1404.05107arXiv1710.08249OpenAlexW2963999055WikidataQ129770612 ScholiaQ129770612MaRDI QIDQ4645033FDOQ4645033

Authors: Petr Gregor, Torsten Mütze, Jerri Nummenpalo 

Publication date: 9 January 2019

Published in: Discrete Analysis (Search for Journal in Brave)

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.

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

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

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cites Work

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

Cited In (20)

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

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)