Cayleyn graafien 1-faktoroinnista

Abstract

Tässä pro gradu -tutkielmassa käsitellään Cayleyn graafeja ja niihin liittyvää avointa 1-faktorointikonjektuuria. Cayleyn graafit ovat graafeja, jotka havainnollistavat algebrallisten ryhmien rakennetta suhteessa johonkin ryhmän virittävään joukkoon. Cayleyn graafien 1-faktorointikonjektuurin mukaan parillisen kertaluvun ryhmän Cayleyn graafi voidaan virittävästä joukosta riippumatta 1-faktoroida eli jakaa 1-säännöllisiin, virittäviin ja särmien osalta pareittain erillisiin aligraafeihin.

Tutkielman ensimmäisessä varsinaisessa luvussa käsitellään yleisesti graafiteoriaa ja määritellään graafiteorian keskeisimmät käsitteet. Vastaavasti luvussa 3 käsitellään ryhmäteorian perusteita, kuten permutaatioita, ryhmiä, erilaisia aliryhmiä, ryhmien välisiä tuloja, symmetriaryhmiä sekä edellisiin liittyviä lauseita. Graafiteoriaa käsittelevästä luvusta 2 poiketen luvun 3 jälkimmäisellä puolikkaalla käsitellään monia sellaisia määritelmiä ja tuloksia, jotka eivät usein sisälly suoraan yliopiston maisteritason opetukseen, kuten Sylowin lauseita, nilpotentteja ryhmiä ja puolisuoria tuloja. Molempien lukujen sisältöä havainnollistetaan esimerkeillä.

Lukujen 2 ja 3 valmistelevat tarkastelut mahdollistavat Cayleyn graafien käsittelyn luvussa 4. Siinä todistetaan, että jokainen äärellisesti virittyvä ryhmä on isomorfinen yhtenäisen, suuntaamattoman ja paikallisesti äärellisen graafin symmetriaryhmän aliryhmän kanssa. Tämän jälkeen määritellään kyseisessä lauseessa esitetyn konstruktion pohjalta Cayleyn graafit ja käsitellään niiden vaihtoehtoisia määritelmiä, ominaisuuksia ja solmutransitiivisuutta, ja annetaan esimerkkejä.

Tutkielman 5. luku keskittyy Cayleyn graafien 1-faktorointikonjektuuriin. Luvussa määritellään konjektuurin esittämiseksi tarvittavat käsitteet, todistetaan eräissä konjektuurin osatulosten todistuksissa tarvittava Vizingin lause ja lopulta todistetaan konjektuuri Richard A. Stongin vuoden 1985 artikkeliin pohjautuen suurille perheille äärellisiä ryhmiä: ryhmille, joiden kertaluku on luvun 2 potenssi, Abelin ryhmille, diedriryhmille ja nilpotenteille ryhmille. Numeroituvasti äärettömien ryhmien osalta konjektuuri todistetaan äärettömästi virittyville ryhmille ja Abelin ryhmille. Viimeisessä luvussa esitetään yhteenveto tutkielman sisällöstä sekä pohditaan jatkotutkimusmahdollisuuksia.