A short proof of the middle levels theorem

10/23/2017
by   Petr Gregor, et al.
0

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 n≥ 1. In this paper we present a new proof of this conjecture, which is much shorter and more accessible than the original proof.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset