"Gray code" for building teams

Question

Motivation. In a team of $n$ people, we had the task to build subteams of a fixed size $k<n$ such that every day, $1$ person of the subteam is replaced by another person in the team, but not in the subteam (so that the new subteam consisted of $k$ again). The question arose if and for what choices of $k$ and $n$ the subteam schedule can be built to contain each choice of $k$ people out of the team exactly once.

Formal version. For any set $X$ and positive integer $k$, let $[X]^k$ be the collection of subset of $X$ having $k$ elements. For $n\in\mathbb{N}$ let $[n] =\{1,\ldots,n\}$. For integers $1< k < n$ we define a graph $G(n, k)$ by $V(G(n,k)) = [[n]]^k$ and $$E(G(n,k)) = \big\{\{A, B\} : A, B \in [[n]]^k \land |A\cap B| = k-1\big\}.$$ For what choices of $1< k < n$ does $G(n,k)$ have a Hamiltonian path? Bonus question: Replace "path" by "cycle" in the original question. (The bonus question need not be answered for acceptance.)

Answer 1

This seems to be possible for all choices of $k$ and $n$. I found a page here by Dr. Ronald D. BAKER describing a more than sixty year old 'revolving door algorithm'.

When enumerating the k-element subsets of and n-set we are implicitly enumerating the partitions of the n-set into parts, one of size s=k and the other of size t=n-k. Hence the problem is often described as the enumeration of (s,t)-combinations. Suppose the think of the set as a collection of people and imagine them being divided into two adjacent rooms, k people in one room with the remaining n-k people in the other room. Now further imagine that there is a revolving door connecting the two rooms, and a change consists of an individual from each room entering that revolving door and exchanging sides. This analogy is the source of the moniker revolving door algorithm.

W. H. Payne created the following algorithm in 1959. The call to visit might, for example, output the k-subset or it might do the computations of an algorithm which needs all k-element subsets. Each k-subset is referenced by an index-list $c_k \dots c_2c_1$, the indices of the elements belonging to the subset sorted in order. Notice the code makes extensive use of conditionals, the branching command goto and line labels†.

algorithm RevDoorSubset(n, k)
     Array C[1..k+1]
R1:  for i ← 1 to k do    // initialize C
        C[i] ← i-1
     end for
     C[k+1] ← n
R2:  visit(C[ ], k)   // Do whatever is needed w/ subset (just print?)
R3:  if (k is odd)    // the easy cases
       if ( C[1]+1 < C[2] )                            
          C[1] ← C[1]+1
          goto R2
       else
           j ← 2
          goto R4
       fi
     else
       if ( C[1] > 0 )
          C[1] ← C[1]-1
          goto R2
       else
           j ← 2
          goto R5
       fi
     fi
    
R4:  if ( C[j] ≥ j )  // try to decrease C[j]
       C[j] ← C[j-1]
       C[j-1] ← j-2
       goto R2
     else
       j ← j+1
     fi
R5:  if ( C[j] + 1 < C[j+1] )     // try to increase C[j]
       C[j-1] ← C[j]
       C[j] ← C[j] + 1
       goto R2
     else
       j ← j + 1
       if ( j ≤ k)
         goto R4
       fi
     fi
     return
end

I've converted the algorithm to JavaScript; I don't think MathOverflow supports Stack Snippets but I've managed to host a working demo here in the Sandbox on Meta Stack Exchange. Click the 'Run code snippet' below the code, change the values of $n$ and $k$ and click 'Generate'.

You can also try it online here in case the Sandbox fails.

It seems this algorithm produces Hamiltonian cycles, but to prove it I'll need some sleep first.

Answer 2

The following recursive description of a revolving door sequence is taken from here, where it is also proved that it generates a Hamilton cycle. The $k$-subsets of $\{1,\dots,n\}$ are identified with the bitstrings of length $n$ with exactly $k$ entries equal to $1$. Let $R(k,n)$, denote the binary $\binom{n}{k}\times n$-matrix whose rows correspond to the required sequence of the $k$-sets. Then $$R(0,n)=\begin{pmatrix}0&0&\dots&0\end{pmatrix},\qquad R(n,n)=\begin{pmatrix}1&1&\dots&1\end{pmatrix},$$ and for $1\leqslant k\leqslant n-1$, we obtain $R(k,n)$ by writing down the $\binom{n-1}{k}$ rows of $R(k,n-1)$, putting an additional $0$ in front, and below this writing the $\binom{n-1}{k-1}$ rows of $R(k-1,n-1)$ in reverse order, putting an additional $1$ in front.

The precise Knuth reference mentioned in a comment above is Section 7.2.1.3. Generating all combinations in TAOCP, Volume 4A - Combinatorial Algorithms, Part 1.

Here's an interesting related result: If $n=2k-1$ then $\binom{n}{k}=\binom{n}{k-1}$, and we can hope that in the process every $(k-1)$-set is visited exactly once. That this is possible used to be the middle level conjecture which is now a theorem due to Torsten Mütze: Proof of the middle levels conjecture. Proceedings of the London Mathematical Society 112.4 (2016): 677-713.

Answer 3

Theorem. The graph $G(n,k)$ is Hamiltonian if $n\ge3$ and $0\lt k\lt n$.

Proof. If $k=1$ or $k=n-1$ it's obvious, because $G(n,k)\cong K_n$ in those cases. Now consider the graph $G=G(n,k)$ where $2\le k\le n-2$. Let $$S=\{A\in[[n]]^k:1\in A\},\quad S'=\{A\in[[n]]^k:1\notin A\}.$$ Since the induced subgraphs $G[S]$ and $G[S']$ are isomorphic to $G(n-1,k-1)$ and $G(n-1,k)$ respectively, they are Hamiltonian by the inductive hypothesis. Moreover, since the graphs are edge transitive, we can choose a Hamiltonian cycle $C$ in $G[S]$ containing the edge $$\{A,B\}=\{\{1,\dots,k\},\ \{1,\dots,k-1,k+1\}\}$$ and a Hamiltonian cycle $C'$ in $G[S']$ containing the edge $$\{A',B'\}=\{\{2,\dots,k,k+2\},\ \{2,\dots,k+1\}\}.$$ Now we get a Hamiltonian cycle in $G$ by removing the edges $\{A,B\}$ and $\{A',B'\}$ from $C\cup C'$, and replacing them with $\{A,A'\}$ and $\{B,B'\}$.