Lovász conjecture

In graph theory, the Lovász conjecture (1970) is a classical problem on Hamiltonian paths in graphs. It says:: "Every finite connected vertex-transitive graph contains a Hamiltonian path".The original article of Lovász stated the result in the opposite, butthis version became standard. In 1996 Babaipublished a conjecture sharply contradicting this conjecture,but both conjectures remain widely open.It is not even known if a single counterexample would necessarily lead to a series of counterexamples.

Historical remarks

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

Cayley graphs

Another version of Lovász conjecture states that: "Every finite connected Cayley graph contains a Hamiltonian cycle".While this version is open as well, there exist an exampleof vertex-transitive graph with no Hamiltonian cycles(but with Hamiltonian paths). This example is the Petersen graph.

The advantage of the Cayley graph formulation is that such graphscorrespond to a finite group $G$ and a
generating set $S$. Thus one can askfor which $G$ and $S$ the conjecture holdsrather than attack it in full generality.

pecial cases

The Lovász conjecture is straightforward for abelian groups. It was proved in 1986 to hold for p-groups by D. Witte. It is open even for dihedral groups, although for special sets of generators some progress has been made.

When group $G\; =\; S\_n$ is a symmetric group, theare many attractive generating sets. For example,Lovász conjecture holds in the following cases of generating sets:
* $a\; =\; (1,2,dots,n),\; b\; =\; (1,2)$ (long cycle and a transposition).
* $s\_1\; =\; (1,2),\; s\_2\; =\; (2,3),\; dots,\; s\_\{n-1\}\; =\; (n-1,n)$ (Coxeter generators).
* any set of transpositions corresponding to a labelled tree on $\{1,2,..,n\}$.
* $a\; =(1,2),\; b\; =\; (1,2)(3,4)cdots,\; c\; =\; (2,3)(4,5)cdots$

General groups

For general finite groups, only a few results are known:
* $S=\{a,b\},\; (ab)^2=1$ (R.A. Rankin generators)
* $S=\{a,b,c\},\; a^2=\; b^2=c^2=\; [a,b]\; =1$ (Rapaport-Strasser generators)
* $S=\{a,b,c\},\; a^2=1,\; c\; =\; a^\{-1\}ba$ (Pak-Radoičić generators)
* $S=\{a,b\},\; a^2\; =\; b^s\; =(ab)^3\; =\; 1,$ where $|G|,s\; =\; 2~mod\; ~4$ (here we have (2,s,3)-presentation, [http://www.math.ohio-state.edu/~glover/preprints/HamCubCayFin.pdf Glover-Marušič theorem] )

Finally, it is known that for every finite group $G$ "there exists"a generating set of size at most $log\_2\; |G|$ such thatthe 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 $Omega(log^5\; |G|)$ (Krivelevich-Sudakov [http://www.math.princeton.edu/~bsudakov/pseudo-hamiltonian.pdf] ).

Directed graph version

For directed Cayley graphs (digraphs) the Lovász conjecture is false. Various counterexamples were obtained by R.A. Rankin. Still, many of the above results hold in this restrictive setting.

References

*L. Babai, [http://www.cs.uchicago.edu/research/publications/techreports/TR-94-10 Automorphism groups, isomorphism, reconstruction] , in "Handbook of Combinatorics", Vol. 2, Elsevier, 1996, 1447-1540.
*D. E. Knuth, The Art of Computer Programming, Vol. 4, draft of section 7.2.1.2.
*I. Pak, R. Radoičić, [http://www-math.mit.edu/~pak/hamcayley8.pdf Hamiltonian paths in Cayley graphs] , 2002.