Lovász-sejtés

A Lovász-sejtés a matematika, konkrétabban a gráfelmélet egyik nyitott kérdése. Így szól:

Minden véges, összefüggő csúcstranzitív gráfban létezik Hamilton-út.

Lovász László eredetileg az állítást fordítva fogalmazta meg 1970-es cikkében, de a sejtés mégis a fenti megfogalmazásban terjedt el. Babai László 1996-ban publikált egy sejtést, ami erősen ellentmond a Lovász-sejtésnek, viszont egyelőre még mindkettő bizonyítatlan. Még az sem bizonyított, hogy egyetlen ellenpélda létezése ellenpéldák sokaságához vezetne-e.

Hamilton-kör biztosan nem létezik minden véges, összefüggő, csúcstranzitív gráfban. Öt ellenpélda ismert, nevezetesen a Petersen-gráf, a K₂ teljes gráf, a Coxeter-gráf és két további gráf. Ezért a Hamilton-körös változat csak gyengítve fogalmazható meg:^[1]

Az öt ismert kivételen kívül minden véges, összefüggő csúcstranzitív gráfban létezik Hamilton-kör.

Az öt ismert ellenpélda közül egyik sem Cayley-gráf, ami szintén motivál egy változatot:

Minden véges, összefüggő Cayley-gráf tartalmaz Hamilton-kört.

Ezeknek a változatoknak sincs általános, ismert bizonyítása.

A Cayley-gráfos változat kezelhető csoportelméleti módszerekkel és vannak is ismert eredmények speciális ${\displaystyle G}$ csoportok és ${\displaystyle S}$ generátorhalmazok esetében. Abel-csoportok és p-csoportok Cayley-gráfjaira például teljesül, de diédercsoportokra még mindig nincs eredmény.

Az ${\displaystyle G=S_{n}}$ szimmetrikus csoport esetén a sejtés teljesül ezekre a generátorhalmazokra:

• ${\displaystyle a=(1,2,\dots ,n),b=(1,2)}$ (hosszú ciklus és egy transzpozíció)
• ${\displaystyle s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)}$ Coxeter-generátorok)
• a ${\displaystyle \{1,2,..,n\}}$ halmaz címkézett fáinak megfelelő transzpozíciók halmaza
• ${\displaystyle a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots }$

Az irányított Cayley-gráfok esetén a sejtésre R.A. Rankin több ellenpéldát is adott.

Abel-csoportok esetében az állítás elég egyszerűen belátható. Általános véges csoportokra csak néhány speciális generátorhalmaz esetében van bizonyítás:

• ${\displaystyle S=\{a,b\},(ab)^{2}=1}$ (Rankin-generátorok)
• ${\displaystyle S=\{a,b,c\},a^{2}=b^{2}=c^{2}=[a,b]=1}$ (Rapaport-Strasser-generátorok)
• ${\displaystyle S=\{a,b,c\},a^{2}=1,c=a^{-1}ba}$ (Pak-Radoičić-generátorok)
• ${\displaystyle S=\{a,b\},a^{2}=b^{s}=(ab)^{3}=1,}$ ahol ${\displaystyle |G|,s=2~mod~4}$ (lásd: Glover-Marušič theorem)

Ismert továbbá az a tény, hogy minden véges ${\displaystyle G}$ csoporthoz létezik legfeljebb ${\displaystyle \log _{2}|G|}$ elemű generátorhalmaz úgy, hogy a hozzá tartozó Cayley-gráf tartalmaz Hamilton-kört (Pak-Radoičić). Ez az eredmény a véges egyszerű csoportok osztályozásán alapul.

1. ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archiválva 2008. július 20-i dátummal a Wayback Machine-ben

• Babai László, Automorphism groups, isomorphism, reconstruction, Handbook of Combinatorics, Vol. 2, Elsevier, 1996, 1447-1540.
• Donald Knuth, A számítógép-programozás művészete, Vol. 4, draft of section 7.2.1.2.
• Igor Pak és Rados Radoičić, Hamiltonian paths in Cayley graphs, 2002.

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!