Are these bipartite graphs Hamiltonian graphs? And do they have a name?

Question

Assume that $n = 2k + 1$, and $$A = \{ \alpha \in \{\,0,1 \,\}^{n} \mid w(\alpha) = k + 1 \}$$ $$B = \{ \alpha \in \{\,0,1 \,\}^{n} \mid w(\alpha) = k \}$$ where $w(\cdot)$ is the Hamming weight.

Let $V = A \cup B$ and $$E = \{ (\alpha_{1}, \alpha_{2}) \in V \times V \mid d(\alpha_{1}, \alpha_{2}) = 1 \}$$

where $d(\cdot, \cdot)$ is the Hamming distance. It is obvious that $G = (V,E)$ is a bipartite graph.

Q1: Is $G$ a Hamiltonian graph?

Q2: I believe that there is a name of this "combinatorial problem" or "graph" or "code", do you know that?

As for $n = 5$, I give a Hamiltonian cycle here. $$(01110,01100,01101,00101, \\ 00111,00110,10110,10010,\\ 10011,00011,01011,01001, \\ 11001,10001,10101,10100,\\ 11100,11000,11010,01010)$$

Answer 1

The bipartite Kneser graph $H(n,k)$ is the graph with vertex set consisting of:

• $A$, the set of all $k$-element subsets of $\{1,2, \dots,n\}$, and
• $B$, the set of all $(n-k)$-element subsets of $\{1,2,\dots,n\}$.

A vertex $S \in A$ and a vertex $T \in B$ are adjacent if and only if $S \subseteq T$.

Your graph is a special case of this graph: it is the graph $H(2k+1,k)$. (In my notation, $A$ and $B$ are swapped from yours: $A$ corresponds to the weight-$k$ strings of length $n$ and $B$ corresponds to the weight-$(k+1)$ strings.) It also has a special name, the middle layer graph.

---

The graph $H(n,k)$ is Hamiltonian for any $k \ge 1$ and $n \ge 2k+1$, so the middle layer graph is also Hamiltonian, but this is a relatively recent - and not easy - result. It was proven:

• For the middle layer graph in 2014 by Torsten Mütze (Proof of the middle levels conjecture, Proceedings of the London Mathematical Society, 2016, arXiv link).
• In general in 2015 by Torsten Mütze and Pascal Su (Bipartite Kneser graphs are Hamiltonian, Combinatorica, 2017, arXiv link).