Porupsánszki István: A cage problémakör véges geometriai konstrukciói

Véges Geometria Szeminárium

Abstract: Az ún. cage probléma egy jól ismert gráfelméleti probléma: adott (k,g) pár esetén  határozzuk meg a k-reguláris, g bőségű gráfok közül a legkisebb csúcsszámúakat. Ismert alsó becslés (Moore-korlát) és néhány konkrét eset, de általánosságban keveset tudunk. Éppen ezért rengeteg variációja van a problémának, jelenleg is sokan aktívan kutatják. Ez a téma alapvetően gráfelméleti, azonban a konstrukciók jelentős része a véges geometriából jön: projektív síkok, általánosított négy- és hatszögek illeszkedési gráfjainak különböző geometriai tulajdonságokon alapuló módosításaival lehet "jó" gráfokat konstruálni. Előadásomban néhány ilyen konstrukciót szeretnék bemutatni.