Lovász dohad - Lovász conjecture - Wikipedia

v teorie grafů, Lovász dohad (1969) je klasický problém Hamiltonovské cesty v grafech. Říká:

Každý konečný připojen vrchol-tranzitivní graf obsahuje a Hamiltonova cesta.

Původně László Lovász uvedl problém opačně, ale tato verze se stala standardní. V roce 1996 László Babai zveřejnil domněnku, která ostře odporuje této domněnce,^[1] ale oba dohady zůstávají široce otevřené. Není ani známo, zda jediný protiklad by nutně vedlo k sérii protikladů.

Historické poznámky

Problém nalezení hamiltonovských cest ve vysoce symetrických grafech je poměrně starý. Tak jako Donald Knuth popisuje to ve svazku 4 z Umění počítačového programování,^[2] problém vznikl v britský kampanologie (zvonění). S takovými hamiltoniánskými cestami a cykly jsou také úzce spojeny Šedé kódy. V každém případě jsou konstrukce explicitní.

Varianty Lovászova domněnky

Hamiltonovský cyklus

Další verze Lovász dohad tvrdí, že

Každý konečný připojen vrchol-tranzitivní graf obsahuje Hamiltoniánský cyklus kromě pěti známých protikladů.

Existuje 5 známých příkladů grafů přechodných vrcholů bez hamiltonovských cyklů (ale s hamiltonovskými cestami): the kompletní graf ${ displaystyle K_ {2}}$, Petersenův graf, Coxeterův graf a dva grafy odvozené z grafů Petersen a Coxeter nahrazením každého vrcholu trojúhelníkem.^[3]

Cayleyovy grafy

Žádný z 5 vertex-tranzitivních grafů bez Hamiltonovských cyklů není Cayleyův graf. Toto pozorování vede k slabší verzi domněnky:

Každý konečný připojen Cayleyův graf obsahuje Hamiltoniánský cyklus.

Výhodou formulace Cayleyova grafu je, že takové grafy odpovídají a konečná skupina ${ displaystyle G}$ a agenerující sada ${ displaystyle S}$. Lze tedy požádat o které ${ displaystyle G}$ a ${ displaystyle S}$ domněnka spíše drží, než aby na ni zaútočila v plné obecnosti.

Směrovaný Cayleyův graf

U směrovaných Cayleyových grafů (digrafů) je domněnka Lovász nepravdivá. Různé protipříklady byly získány Robert Alexander Rankin. Mnoho z níže uvedených výsledků stále platí v tomto omezujícím nastavení.

Speciální případy

Hamiltonovská cesta v permutohedron, Cayleyův graf symetrické skupiny s generátory Coxeter

Každý směrovaný Cayleyův graf abelianská skupina má hamiltonovskou cestu; nicméně každá cyklická skupina, jejíž řád není hlavní silou, má směrovaný Cayleyův graf, který nemá hamiltonovský cyklus.^[4]V roce 1986 D. Witte dokázal, že Lovászova domněnka platí pro Cayleyovy grafy p-skupiny. Je otevřený i pro dihedrální skupiny, ačkoli u speciálních sad generátorů bylo dosaženo určitého pokroku.

Když skupina ${ displaystyle G = S_ {n}}$ je symetrická skupina, existuje mnoho atraktivních generujících sad. Například domněnka Lovász platí v následujících případech generování množin:

• ${ displaystyle a = (1,2, tečky, n), b = (1,2)}$ (dlouhý cyklus a transpozice ).
• ${ displaystyle s_ {1} = (1,2), s_ {2} = (2,3), tečky, s_ {n-1} = (n-1, n)}$ (Coxeter generátory ). V tomto případě je Hamiltoniánský cyklus generován Algoritmus Steinhaus – Johnson – Trotter.
• jakákoli sada provedení odpovídající a označený strom na ${ displaystyle {1,2, .., n }}$.
• ${ displaystyle a = (1,2), b = (1,2) (3,4) cdots, c = (2,3) (4,5) cdots}$

Stong ukázal, že domněnka platí pro Cayleyův graf věnec produkt Z_m wrZ_n s přirozenou minimální generující sadou, když m je sudý nebo tři. To platí zejména pro cykly spojené s krychlí, které lze vygenerovat jako Cayleyův graf produktu věnce Z₂ wrZ_n.^[5]

Obecné skupiny

U obecných konečných skupin je známo jen několik výsledků:

• ${ displaystyle S = {a, b }, (ab) ^ {2} = 1}$ (Rankin generátory)
• ${ displaystyle S = {a, b, c }, a ^ {2} = b ^ {2} = c ^ {2} = [a, b] = 1}$ (Rapaport – Strasser generátory)
• ${ displaystyle S = {a, b, c }, a ^ {2} = 1, c = a ^ {- 1} ba}$ (Pak –Radoičić generátory^[6])
• ${ displaystyle S = {a, b }, a ^ {2} = b ^ {s} = (ab) ^ {3} = 1,}$ kde ${ displaystyle | G |, s = 2 ~ mod ~ 4}$ (tady máme (2, s, 3) -prezentace, Glover – Marušičova věta^[7]).

Nakonec je známo, že pro každou konečnou skupinu ${ displaystyle G}$ existuje nanejvýš generující sada velikosti ${ displaystyle log _ {2} | G |}$ takový, že odpovídající Cayleyův graf je Hamiltonian (Pak-Radoičić). Tento výsledek je založen na klasifikace konečných jednoduchých skupin.

Lovászova domněnka byla také vytvořena pro náhodné generování množin velikosti ${ displaystyle Omega ( log ^ {5} | G |)}$.^[8]

Reference