Paleyn graafit laajennusaksioomien malleina

Abstract

Tutkielmassa tarkastellaan Paleyn graafeja ja laajennusaksioomia. Erityisesti osoitetaan, että Paleyn graafit ovat laajennusaksioomien malleja.

Graafien käsittelyä tutkielmassa pohjustetaan esittelemällä tarpeellista käsitteistöä. Esitellään satunnaisgraafin käsite, jonka avulla tarkastellaan graafien ominaisuuksia. Graafien ominaisuuksista tarkastellaan erityisesti laajennusaksioomia. Laajennusaksioomissa yleisesti ottaen vaaditaan, että jokaiselle graafin tietyn kaltaiselle solmujen osajoukolle on olemassa eri solmu, joka on liitetty osajoukon solmuihin vaaditulla tavalla. Laajennusaksioomista tutkielmassa erityisesti käsitellään k-laajennusaksioomia, ja osoitetaan, että k-laajennusaksioomien toteuttavia graafeja on aina olemassa ja että tämän ominaisuuden asymptoottinen todennäköisyys on 1.

Paleyn graafien käsittelyä varten määritellään neliönjäännös ja siihen liittyvä Legendren symboli. Käydään läpi näihin liittyviä tuloksia ja tarvittavia arvioita. Esitellään myös karakterin käsite, joka on tarpeellinen pääväittämämme todistuksessa. Määritellään Paleyn graafit, jonka jälkeen lopuksi todistetaan pääväite, että riittävän suuret Paleyn graafit toteuttavat k-laajennusaksioomat.