Fruchtsova věta - Fruchts theorem - Wikipedia

The Frucht graf, 3-pravidelný graf, jehož skupina automorfismu realizuje triviální skupina.

Fruchtova věta je teorém v algebraická teorie grafů dohadoval se Dénes Kőnig v roce 1936[1] a prokázáno Robert Frucht v roce 1939.[2] Uvádí se, že každý konečný skupina je skupina symetrie konečný neorientovaný graf. Silněji pro každou konečnou skupina G existuje nekonečně mnoho neizomorfní jednoduchý spojené grafy takové, že automorfická skupina každého z nich je izomorfní naG.

Důkaz

Hlavní myšlenkou důkazu je pozorovat, že Cayleyův graf z G, s přidáním barev a orientací na jeho okrajích pro rozlišení generátorů G jeden od druhého, má požadovanou skupinu automorfismu. Proto pokud je každá z těchto hran nahrazena příslušným podgrafem, takže každý náhradní podgraf je asymetrický a dvě náhrady jsou izomorfní, pokud a pouze pokud nahradí hrany stejné barvy, pak bude i neřízený graf vytvořený provedením těchto náhrad také mít G jako jeho skupina symetrie.[3]

Velikost grafu

Až na tři výjimky - cyklické skupiny řádů 3, 4 a 5 - může být každá skupina reprezentována jako symetrie grafu, jehož vrcholy mají pouze dva oběžné dráhy. Proto je počet vrcholů v grafu nanejvýš dvojnásobkem pořadí skupiny. S větší sadou výjimek lze většinu konečných skupin reprezentovat jako symetrie a vrchol-tranzitivní graf, s počtem vrcholů rovným pořadí skupiny.[4]

Speciální skupiny grafů

Existují silnější verze Fruchtovy věty, které ukazují, že určité omezené rodiny grafů stále obsahují dostatek grafů k realizaci jakékoli skupiny symetrie. Frucht[5] dokázal, že ve skutečnosti je jich spousta 3 pravidelné grafy s požadovanou vlastností existují; například Frucht graf, 3-pravidelný graf s 12 vrcholy a 18 hranami, nemá žádné netriviální symetrie, což poskytuje realizaci tohoto typu pro triviální skupina. Gert Sabidussi ukázal, že kteroukoli skupinu lze realizovat jako skupiny symetrie spočítatelně mnoha odlišných k-pravidelné grafy, kgrafy spojené s vrcholem nebo k-chromatické grafy, pro všechny kladné celočíselné hodnoty k (s pro běžné grafy a pro k-chromatické grafy).[6] Z faktů, že každý graf lze rekonstruovat z kontejnmentu částečná objednávka jeho hran a vrcholů, že každý konečný dílčí řád je ekvivalentní Birkhoffova věta o reprezentaci na konečnou distribuční mříž z toho vyplývá, že každou konečnou skupinu lze realizovat jako symetrie distribuční mřížky a grafu mřížky, a střední graf.[3] Je možné realizovat každou konečnou skupinu jako skupinu symetrií a silně pravidelný graf.[7] Každá konečná skupina může být také realizována jako symetrie grafu s rozlišovací číslo dva: jeden může (nesprávně) vybarvit graf dvěma barvami, takže žádná ze symetrií grafu nezachová zbarvení.[8]

Některé důležité třídy grafů však nejsou schopné realizovat všechny skupiny jako jejich symetrie. Camille Jordan charakterizoval skupiny symetrie stromy jako nejmenší množina konečných skupin obsahujících triviální skupina a uzavřeno pod přímé produkty spolu navzájem a výrobky z věnců s symetrické skupiny;[9] zejména cyklická skupina řádu tři není skupina symetrie stromu. Rovinné grafy také nejsou schopni realizovat všechny skupiny jako jejich symetrie; například jediný konečné jednoduché skupiny což jsou symetrie rovinných grafů cyklické skupiny a střídavá skupina .[10] Obecněji, každý malá uzavřená rodina grafů není schopen reprezentovat všechny konečné skupiny podle symetrií svých grafů.[11] László Babai dohady, silněji, že každá menší uzavřená rodina může představovat pouze konečně mnoho necyklických konečných jednoduchých skupin.[12]

Nekonečné grafy a skupiny

Izbicki rozšířil tyto výsledky v roce 1959 a ukázal, že existují nespočetně mnoho nekonečný grafy realizující jakoukoli konečnou skupinu symetrie.[13] Konečně, Johannes de Groot a Sabidussi v letech 1959/1960 nezávisle prokázali, že kteroukoli skupinu (upustíme od předpokladu, že skupina bude konečná) lze realizovat jako skupinu symetrií nekonečného grafu.[14][15]

Reference

  1. ^ Kőnig (1936)
  2. ^ Frucht (1939)
  3. ^ A b Babai (1995), diskuse následující po větě 4.1.
  4. ^ Babai (1995), Oddíl 4.3.
  5. ^ Frucht (1949)
  6. ^ Sabidussi (1957)
  7. ^ Babai (1995), Věta 4.3.
  8. ^ Albertson, Michael O .; Collins, Karen L. (1996), „Symetrie lámání v grafech“, Electronic Journal of Combinatorics, 3 (1): R18, PAN  1394549.
  9. ^ Babai (1995), Návrh 1.15. Babai datuje Jordanův výsledek do roku 1869, ale do své bibliografie zahrnuje pouze jordánský článek z roku 1895.
  10. ^ Babai (1995), diskuse následující po větě 1.17.
  11. ^ Babai (1995), Věta 4.5.
  12. ^ Babai (1995), diskuse následující po větě 4.5.
  13. ^ Izbicki (1959)
  14. ^ de Groot (1959)
  15. ^ Sabidussi (1960)

Zdroje