en>Mattg82: clean up, removed orphan tag using AWB

2010-02-18T17:49:45Z

clean up, removed orphan tag using AWB

New page

In [[graph theory]], the '''Lovász conjecture''' (1970) is a classical problem on [[Hamiltonian path]]s in graphs. It says:
: Every finite connected [[vertex-transitive graph]] contains a Hamiltonian path.
The original article of [[László Lovász|Lovász]] stated the result in the opposite, but
this version became standard. In 1996 [[László Babai|Babai]] published a conjecture sharply contradicting this conjecture,<ref>[[László Babai|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.</ref> 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 [[Donald Knuth|Knuth]] describes it in volume 4 of [[The Art of Computer Programming]],<ref>[[Donald Knuth|D. E. Knuth]], [[The Art of Computer Programming]], Vol. 4, draft of section 7.2.1.2.</ref> the problem originated in [[United Kingdom|British]] [[change ringing|campanology]] (bell-ringing). Such Hamiltonian paths and cycles are also closely connected to [[Gray code]]s. In each case the constructions are explicit.

== Variants of the Lovász conjecture ==
=== Hamiltonian cycle ===
Another version of '''Lovász conjecture''' states that
: ''Every finite connected [[vertex-transitive graph]] contains a Hamiltonian cycle'' except the five known counterexamples.

There are 5 known examples of vertex-transitive graphs with no Hamiltonian cycles (but with Hamiltonian paths): the [[complete graph]] ''K''2, the [[Petersen graph]], the [[Coxeter graph]] and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle.<ref>Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census "Cubic Symmetric Graphs (The Foster Census)."]</ref>

===Cayley graphs===
None of the 5 vertex-transitive graphs with no Hamiltonian cycles is a Cayley graph, therefore that leads to a weaker version of the conjecture:
: ''Every finite connected [[Cayley graph]] contains a Hamiltonian cycle''.

The advantage of the Cayley graph formulation is that such graphs correspond to a [[finite group]] <math>G</math> and a
[[Generating set of a group|generating set]] <math>S</math>. Thus one can ask for which <math>G</math> and <math>S</math> the conjecture holds rather than attack it in full generality.

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

==Special cases==
[[File:Steinhaus-Johnson-Trotter-Permutohedron.svg|thumb|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.<ref>{{citation
| last1 = Holsztyński | first1 = W.
| last2 = Strube | first2 = R. F. E.
| doi = 10.1016/0012-365X(78)90059-6
| issue = 3
| journal = Discrete Mathematics
| mr = 522721
| pages = 263–272
| title = Paths and circuits in finite groups
| volume = 22
| year = 1978}}.</ref>
In 1986, D. Witte proved that the Lovász conjecture holds for the Cayley graphs of [[p-group]]s. It is open even for [[dihedral group]]s, although for special sets of generators some progress has been made.

When group <math>G = S_n</math> is a [[symmetric group]], there are many attractive generating sets. For example, the Lovász conjecture holds in the following cases of generating sets:
* <math>a = (1,2,\dots,n), b = (1,2)</math> (long cycle and a [[Transposition (mathematics)|transposition]]).
* <math>s_1 = (1,2), s_2 = (2,3), \dots, s_{n-1} = (n-1,n)</math> ([[Coxeter group|Coxeter generators]]). In this case a Hamiltonian cycle is generated by the [[Steinhaus–Johnson–Trotter algorithm]].
* any set of transpositions corresponding to a [[Tree (graph theory)|labelled tree]] on <math>\{1,2,..,n\}</math>.
* <math>a =(1,2), b = (1,2)(3,4)\cdots, c = (2,3)(4,5)\cdots</math>

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'''2 wr '''Z'''''n''.<ref>{{citation
| last = Stong | first = Richard
| doi = 10.1016/0012-365X(87)90212-3
| issue = 1
| journal = Discrete Mathematics
| mr = 891546
| pages = 75–80
| title = On Hamiltonian cycles in Cayley graphs of wreath products
| volume = 65
| year = 1987}}.</ref>

==General groups==
For general finite groups, only a few results are known:
* <math>S=\{a,b\}, (ab)^2=1</math> ([[R.A. Rankin]] generators)
* <math>S=\{a,b,c\}, a^2= b^2=c^2=[a,b]=1</math> ([[Rapaport-Strasser]] generators)
* <math>S=\{a,b,c\}, a^2=1, c = a^{-1}ba</math> ([[Igor Pak|Pak]]-[[Radoičić]] generators<ref>[[Igor Pak|I. Pak]], [[Radoičić|R. Radoičić]], [http://www.math.ucla.edu/~pak/papers/hamcayley9.pdf Hamiltonian paths in Cayley graphs], 2002.</ref>)
* <math>S=\{a,b\}, a^2 = b^s =(ab)^3 = 1, </math> where <math>|G|,s = 2~mod ~4</math> (here we have (2,s,3)-[[Presentation of a group|presentation]], Glover-Marušič theorem<ref>Henry Glover and Dragan Marusic [http://www.math.ohio-state.edu/~glover/preprints/HamCubCayFin.pdf Hamiltonicity of Cubic Cayley Graphs]</ref>).

Finally, it is known that for every finite group <math>G</math> there exists a generating set of size at most <math>\log_2 |G|</math> 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 <math>\Omega(\log^5 |G|)</math>.<ref>[[Michael Krivelevich]] and Benny Sudakov [http://www.math.princeton.edu/~bsudakov/pseudo-hamiltonian.pdf Sparse Pseudo-Random Graphs are Hamiltonian]</ref>

==References==
{{reflist}}

{{DEFAULTSORT:Lovasz Conjecture}}
[[Category:Algebraic graph theory]]
[[Category:Conjectures]]
[[Category:Finite groups]]
[[Category:Graph theory]]
[[Category:Group theory]]
[[Category:Hamiltonian paths and cycles]]

Net acid excretion - Revision history

en>Mattg82: clean up, removed orphan tag using AWB