Stadler Domonkos: Extremális gráfok véges geometriai konstrukciói

$(k,g)$-gráfnak hívjuk a $k$-reguláris, $g$ bőségű gráfokat. Adott $k$ és $g$ esetén könnyű belátni a $(k,g)$-gráfok csúcsszámára vonatkozó Moore-korlátnak nevezett alsó becslést. Ezen korlátot elérő gráfok a Moore-gráfok. Ismert, hogy páros $g$ esetén a Moore-gráfok mindegyike valamely általánosított sokszög illeszkedési gráfja. Páratlan $g$ esetén pedig csak néhány Moore-gráf létezik.. Az ismert legkisebb csúcsszámú $(k,g)$-gráfok páratlan g esetén is sokszor illeszkedési gráfokból származnak egy ügyesen választott csúcshalmaz törlésével, majd néhány olyan él hozzáadásával, mely $g$-t 1-gyel csökkenti és helyreállítja a törölt csúcsok szomszédainak fokszámát. A legtöbb ismert konstrukcióban véges síkok illeszkedési gráfjaiból készítettek $5$ bőségű gráfokat. A kutatás célja $g=7$ és $g=11$ esetén hasonló konstrukciók előállítása az általánosított négyszögek és hatszögek geometriai tulajdonságainak felhasználásával.