Fagin-féle 0-1 törvények

Abstract

Ezen szakdolgozatban különböző tulajdonságokat kielégítő relációs struktúrák előfordulásának aszimptotikus valószínűségét vizsgáljuk. Definiáljuk a véges véletlen gráfok modelljét és a véletlen gráfot. Kimondjuk R. Fagin 0-1 törvényét és hasonló állításokat fogalmazunk meg. Továbbá azt tárgyaljuk, hogy milyen tulajdonságok esetén létezik az aszimptotikus valószínűség,és mikor nem. Elsőrendű és nem elsőrendű tulajdonságok esetén mutatunk példákat az aszimptotikus valószínűségekre. Továbbá megmutatjuk Fagin tételének egy általánosítását. Végül ismertetünk két tételt, melyek megadják, hogy egy relációs struktúra automorfizmuscsoportja ,,tipikusan" melyik csoporttal izomorf.