Frucht sats - Frucht's theorem

Den Frucht graf , en 3-regelbunden graf vars automorfism grupp realiserar trivialgrupp .

Frucht's teorem är en teorem i algebraisk grafteori som antogs av Dénes Kőnig 1936 och bevisades av Robert Frucht 1939. Den säger att varje ändlig grupp är gruppen symmetrier i en ändlig, icke-riktad graf . Starkare för varje ändlig grupp G finns det oändligt många icke-isomorfa enkla anslutna grafer så att automorfism gruppen var och en av dem är isomorf till  G .

Bevisidé

Huvudidén med beviset är att observera att Cayley-grafen för G , med tillägg av färger och orienteringar på sina kanter för att skilja G- generatorerna från varandra, har önskad automorfismgrupp. Om var och en av dessa kanter ersätts med en lämplig subgraf, så att varje ersättningsundergraf i sig är asymmetrisk och två ersättare är isomorfa om och bara om de ersätter kanter av samma färg, kommer den oriktade grafen som skapas genom att utföra dessa ersättningar också har G som sin symmeturgrupp.

Diagramstorlek

Med tre undantag - de cykliska grupperna av ordningarna 3, 4 och 5 - kan varje grupp representeras som symmetrier i en graf vars hörn bara har två banor . Därför är antalet hörn i diagrammet högst två gånger gruppens ordning. Med en större uppsättning undantag kan de flesta ändliga grupper representeras som symmetrier för en vertex-transitiv graf , med ett antal hörn lika med gruppens ordning.

Speciella grafer

Det finns starkare versioner av Fruchs teorem som visar att vissa begränsade familjer av grafer fortfarande innehåller tillräckligt med grafer för att förverkliga någon symmetri-grupp. Frucht bevisade att det faktiskt finns många 3-regelbundna grafer med önskad egenskap; till exempel har Frucht-diagrammet , ett 3-regelbundet diagram med 12 hörn och 18 kanter, inga icke-privata symmetrier, vilket ger en realisering av denna typ för den triviala gruppen . Gert Sabidussi visade att vilken grupp som helst kan realiseras som symmetri-grupperna av många många distinkta k - vanliga grafer , k- vertikala kopplade grafer eller k- kromatiska grafer , för alla positiva heltal värden k (med för vanliga grafer och för k - kromatiska grafer). Av de fakta att varje graf kan rekonstrueras från inneslutningens partiella ordning av dess kanter och hörn, att varje ändlig delordning är ekvivalent med Birkhoffs representationssats till ett ändligt fördelningsgitter , följer att varje slutlig grupp kan realiseras som symmetrier av ett distribuerande galler och av grafen för gallret en mediangraf . Det är möjligt att förverkliga varje begränsad grupp som en grupp av symmetrier i ett starkt regelbundet diagram . Varje ändlig grupp kan också realiseras som symmetrier i en graf med särskiljande nummer två: man kan (felaktigt) färga grafen med två färger så att ingen av grafens symmetrier bevarar färgningen.

Vissa viktiga klasser av diagram är dock oförmögna att förverkliga alla grupper som deras symmetrier. Camille Jordan karakteriserade symmetrigrupperna av träd som den minsta uppsättningen av ändliga grupper som innehöll den triviala gruppen och stängdes under direkta produkter med varandra och kransprodukter med symmetriska grupper ; i synnerhet är den cykliska gruppen av ordning tre inte ett träds symmetri-grupp. Plandiagram kan inte heller förverkliga alla grupper som deras symmetrier; till exempel är de enda ändliga enkla grupperna som är symmetri för plana diagram de cykliska grupperna och den alternerande gruppen . Mer allmänt är alla mindre stängda graffamiljer oförmögna att representera alla begränsade grupper med symmetrierna i dess grafer. László Babai antar, starkare, att varje mindre sluten familj bara kan representera ändligt många icke-cykliska ändliga enkla grupper.

Oändliga diagram och grupper

Izbicki utökade dessa resultat 1959 och visade att det fanns oändligt många oändliga diagram som förverkligade någon begränsad symmetri-grupp. Slutligen bevisade Johannes de Groot och Sabidussi 1959/1960 oberoende att någon grupp (som släppte antagandet att gruppen var ändlig) kunde realiseras som gruppen av symmetrier i en oändlig graf.

Referenser

Källor