1
$\begingroup$

For any set $X$, let $[X]^2=\{\{a,b\}:a\neq b \in X\}$. If $n\in\mathbb{N}$ is a positive integer, let $S_n$ denote the collection of bijections $\varphi:\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$. Let $E_n\subseteq [S_n]^2$ be given by $$E_n = \{\{\varphi, \psi\}: \varphi, \psi \in S_n\text{ and } (\exists a\neq b\in \{0,\ldots,n-1\}) \varphi = (a\, b)\circ \psi\},$$ where $(a\,b)$ denotes the transposition of the elements $a$ and $b$.

Does $(S_n,E_n)$ contain a Hamiltonian cycle for every $n\in\mathbb{N}$? If not, does it contain a Hamiltonian path?

$\endgroup$

2 Answers 2

4
$\begingroup$

Yes, $(S_n, E_n)$ contains a Hamiltonian cycle for every $n \geq 3$. This follows by the Steinhaus–Johnson–Trotter algorithm . The transpositions can even be chosen to be consecutive elements in the previous permutation.

$\endgroup$
2
$\begingroup$

There is an answer to an old question of mine that says "yes".

For $n=1$, $S_n$ is trivial and there is nothing to prove. For $n=2$, the unique transposition gives you a Hamiltonian path, but not a cycle. For $n\geq 3$ there is a Hamiltonian cycle and you don't even need all transpositions, the neighbour transpositions are sufficient.

More generally, the proof that is in the linked paper in the linked answer generalises as follows: If $G$ is a finite group which has a minimal generating subset of involutions $S\subseteq G$, consider the non-commuting graph on $S$, i.e. vertices are $S$ and an edge exists iff two elements do not commute. If that graph happens to be cycle-free, the Cayley graph of $(G,S)$ contains a Hamiltonian cycle.

Proof: With two involutions, $G$ is just a dihedral group and we can explicitly write down the Hamiltonian cycle. For $n>2$ we argue by induction. The non-commuting graph is cycle-free, so we can choose to enumerate $S=\{s_1,s_2,\ldots,s_n\}$ such that $s_n$ is a leaf, i.e. there is at most one other vertex connected to it. Now consider the subgroup $H:=\langle s_1,\ldots s_{n-1}\rangle \leq G$ and its cosets $Hx$. By induction, $H$ contains a Hamiltonian cycle and therefore all the cosets do too. We will now inductively construct a strictly increasing sequence of subsets $H \subseteq X_k \subseteq G$ which are unions of cosets and all contain some Hamiltonian cycle. Because $G$ is finite, at some point we'll arrive at $X_k=G$.

We start with $X_0=H$ where we already know that a Hamiltonian cycle exists. If $X_k=s_n X_k$, then $X_k$ is already all of $G$ because it contains $H$ and is closed under multiplication with $s_n$. If $X_k\neq s_n X_k$, then there $y\in s_n X_k\setminus X_k$, say $y=s_n x$. The next set in the sequence will be $X_{k+1}:=X\cup Hy$. Note that this is a strict superset of $X_k$, because $y\notin X_k$. We will stitch together a Hamiltonian cycle of $X_k$ and one of $Hy$ to obtain a Hamiltonian cycle for $X_{k+1}$.

Let $\{x,sx\}$ and $\{x,s'x\}$ be the two edges in the Hamiltonian cycle of $X$ which contain the vertex $x$. Then neither $s$ nor $s'$ is equal to $s_n$, because $y=s_n x\notin X$. Because $s_n$ is a leaf in the non-commuting graph, at most one of the two is connected to $s_n$, the other therefore commutes with $s_n$. Wlog we assume that $s$ commutes: $ss_n = s_n s$.

The Hamiltonian cycle of $H$ has some edge $(h,sh)$ (otherwise we $H$ would be generated by $\{s_1,\ldots, s_{n-1}\}\setminus\{s\}$ contradicting the minimality of the generating set). Multiply with $h^{-1}$ so that the edge is $(1,s)$. Then multiply with $y$ to get a Hamiltonian graph for $Hy$ containing the edge $(y,sy)$.

Now we have two Hamiltonian cycles $$\begin{array}{cccc} \cdots \leftarrow & y &\leftarrow & sy & \leftarrow \cdots \\ \\ \cdots \rightarrow& x &\rightarrow & sx & \rightarrow \cdots \end{array}$$ (top one in $Hy$, bottom one in $X$) which we now stitch together like so: $$\begin{array}{cccc} \cdots \leftarrow & y & & sy & \leftarrow \cdots \\ & \uparrow && \downarrow & \\ \cdots \rightarrow& x & & sx & \rightarrow \cdots \end{array}$$ Note that the new edges are really edges in the Cayley graph: $y=s_n x$ and $sx = s(s_ny) = s_n(sy)$. This completes the induction.

$\endgroup$
1
  • $\begingroup$ Beautiful explanation, thanks! I would have liked to accept both answers $\endgroup$ Jun 25, 2021 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.