Description
Véges Geometria szeminárium
Absztrakt:
Egy gráf erősen reguláris, ha minden csúcs foka k, valamint bármely két szomszédos csúcsnak lambda közös szomszédja van, és bármely két nem szomszédos csúcsnak mu közös szomszédja van. A teljes k-részes gráfok ilyenek, de ortogonális Latin négyzetekből és Steiner rendszerekből is képezhetők példák. Ismert, hogy ezen családok minden elemében található Hamilton-kör. Ezzel szemben például a Petersen-gráf erősen reguláris, viszont nincs benne Hamilton-kör.
Pyber László megmutatta, hogy létezik N természetes szám, hogy minden legalább N csúcsú, összefüggő erősen reguláris gráfban van Hamilton kör. Az eredmény azon alapszik, hogy a fenti említett 3 családhoz nem tartozó erősen reguláris gráfok pszeudorandom struktúrával rendelkeznek. Az előadáson ez az eredmény lesz bemutatva [1] alapján.
[1] László Pyber: Large connected strongly regular graphs are Hamiltonian, 2014, https://arxiv.org/abs/1409.3041