The Middle levels problem

Tomáš Kaiser¹

University of West Bohemia, Plzeň

Let $B_k$ be the bipartite graph formed by the middle two levels of the lattice of subsets of a $(2k+1)$-element set. The well-known Middle levels problem is the question whether $B_k$ is hamiltonian for all $k \geq 1$. As a step towards an answer, we show that $B_k$ has a spanning 3-connected cubic subgraph.

Footnotes

... Kaiser¹

joint work with P. Horák, M. Rosenfeld and Z. Ryjáček