Borbényi Márton: Teljes párosítások síkgráfokban

Egyéni Kutatómunka 1

2020/21 I. félév

Témavezető:
Csikvári Péter (ELTE TTK, Számítógéptudományi Tanszék)
Beszámoló:
Előadás:

A teljes párosítások számának meghatározására nem ismert gyors algoritmus tetszőleges gráf esetén. Azonban síkgráfok esetén Kasteleyn illetve tőle függetlenül Temperley és Lieb adott ilyen algoritmust. Richard Kenyon jelentősen továbbfejlesztette elméletüket. 1995-ben megjelent Local statistics of lattice dimers című cikkében megmutatta például hogyan lehet egy adott konfiguráció esélyét kiszámolni, ha választunk egy véletlen teljes párosítást a négyzetrácsban vagy a hatszögrácsban. Ehhez egy mély elméletet épített fel. Célom a témakör komolyabb megértése, cikkek olvasása.