Lovász conjecture

The problem of finding Hamiltonian paths in highly symmetric graphs is quite old. As Donald Knuth describes it in volume 4 of The Art of Computer Programming,[2] the problem originated in British campanology (bell-ringing). Such Hamiltonian paths and cycles are also closely connected to Gray codes. In each case the constructions are explicit.

A Hamiltonian path in the permutohedron, a Cayley graph of the symmetric group with Coxeter generators

Every directed Cayley graph of an abelian group has a Hamiltonian path; however, every cyclic group whose order is not a prime power has a directed Cayley graph that does not have a Hamiltonian cycle.[4] In 1986, D. Witte proved that the Lovász conjecture holds for the Cayley graphs of p-groups. It is open even for dihedral groups, although for special sets of generators some progress has been made.

When group ${\displaystyle G=S_{n}}$ is a symmetric group, there are many attractive generating sets. For example, the Lovász conjecture holds in the following cases of generating sets:

• ${\displaystyle a=(1,2,\dots ,n),b=(1,2)}$ (long cycle and a transposition).
• ${\displaystyle s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)}$ (Coxeter generators). In this case a Hamiltonian cycle is generated by the Steinhaus–Johnson–Trotter algorithm.
• any set of transpositions corresponding to a labelled tree on ${\displaystyle \{1,2,..,n\}}$.
• ${\displaystyle a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots }$

Stong has shown that the conjecture holds for the Cayley graph of the wreath product Z_m wr Z_n with the natural minimal generating set when m is either even or three. In particular this holds for the cube-connected cycles, which can be generated as the Cayley graph of the wreath product Z₂ wr Z_n.[5]

For general finite groups, only a few results are known:

• ${\displaystyle S=\{a,b\},(ab)^{2}=1}$ (Rankin generators)
• ${\displaystyle S=\{a,b,c\},a^{2}=b^{2}=c^{2}=[a,b]=1}$ (Rapaport–Strasser generators)
• ${\displaystyle S=\{a,b,c\},a^{2}=1,c=a^{-1}ba}$ (Pak–Radoičić generators[6])
• ${\displaystyle S=\{a,b\},a^{2}=b^{s}=(ab)^{3}=1,}$ where ${\displaystyle |G|,s=2~mod~4}$ (here we have (2,s,3)-presentation, Glover–Marušič theorem[7]).

Finally, it is known that for every finite group ${\displaystyle G}$ there exists a generating set of size at most ${\displaystyle \log _{2}|G|}$ such that the corresponding Cayley graph is Hamiltonian (Pak-Radoičić). This result is based on classification of finite simple groups.

The Lovász conjecture was also established for random generating sets of size ${\displaystyle \Omega (\log ^{5}|G|)}$.[8]