Lovász-sejtés

A Wikipédiából, a szabad enciklopédiából

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.

Variációk[szerkesztés | forrásszöveg szerkesztése]

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 K2 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 a G csoportok és S generátorhalmazok esetében. Abel-csoportok és p-csoportok Cayley-gráfjaira például teljesül, de diéder-csoportokra még mindig nincs eredmény.

Az G = S_n szimmetrikus csoport esetén a sejtés teljesül ezekre a generátorhalmazokra:

  • a = (1,2,\dots,n), b = (1,2) (hosszú ciklus és egy transzpozíció)
  • s_1 = (1,2), s_2 = (2,3), \dots, s_{n-1} = (n-1,n) Coxeter- generátorok]])
  • a \{1,2,..,n\} halmaz címkézett fáinak megfelelő transzpozíciók halmaza
  • 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.

Speciális esetek[szerkesztés | forrásszöveg szerkesztése]

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átor halmaz esetében van bizonyítás:

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

Ismert továbbá az a tény, hogy minden véges G csoporthoz létezik legfeljebb \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.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

Irodalom[szerkesztés | forrásszöveg szerkesztése]