Teljes párosítások síkgráfokban
| Témavezető: | Csikvári Péter |
| ELTE TTK, Számítógéptudományi Tanszék | |
| email: | peter.csikvari@ttk.elte.hu |
Projekt leírá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.