háromszögelő feszítő fák

Témavezető:	Tóthmérész Lilla
	ELTE TTK, Operációkutatási Tsz.
email:	lilla.tothmeresz@ttk.elte.hu

Projekt leírás

Alexander Postnikov-nak van egy nagyon meglepő tétele. Ez úgy szól, hogy ha veszünk egy G=(S,T,E) páros gráfot, és megnézzük hogy a feszítőfák hány féle fokszámsorozatot tudnak megvalósítani az S halmazon, és hányat a T-n, akkor ezeknek a száma mindig egyenlő. Vegyük például a K_4,2 teljes páros gráfot. Itt a 2 pontú osztályon a (4,1);(3,2);(2,3);(1,4) fokszámsorozatok valósíthatók meg (a (4,1) és az (1,4) négyféleképpen, a másik kettő pedig 12-féleképpen), a 4 pontú osztályon pedig a (2,1,1,1);(1,2,1,1);(1,1,2,1);(1,1,1,2) fokszámsorozatok (mindegyik 8-féleképpen). Látjuk, hogy mindkét esetben 4 lehetséges fokszámsorozat van, de egyáltalán nem világos hogy mi ennek az oka, vagy hogyan lehetne őket bijekcióba rakni. Postnikov egy nagyon szép geometriai bizonyítást adott erre az eredményre. Megmutatta hogy a gráfhoz hozzá lehet rendelni egy politópot, aminek a csúcsai a gráf éleinek felelnek meg, és néhány csúcs pontosan akkor határoz meg maximális dimenziós szimplexet, ha a megfelelő részgráf egy feszítő-fa. Majd megmutatta, hogy ha a politópot belsőleg diszjunkt szimplexekre bontjuk, akkor a szimplexeknek megfelelő feszítő-fa halmaz bijekciót ad az S-en és a T-n megvalósítható fokszámsorozatok között. Az ilyen feszítő-fa halmazokat nevezzük háromszögelőnek. Ezekről ismert néhány további érdekes tulajdonság is, és van néhány érdekes példa is háromszögelő fa-halmazokra. A cél további jellemzések, érdekes példák és alkalmazások keresése háromszögelő fa-halmazokra.

Hivatkozások

Postnikov, Alexander. Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN 2009, no. 6, 1026--1106.