A Szabad Uniform Feszítőerdő összefüggősége az élsúlyozás függvényében Fizika, Földtudományok és Matematika

35 OTDK, Fizika, Földtudományok és Matematika Szekció, Sztochasztika és statisztika Tagozat.

A Szabad Uniform Feszítőerdő összefüggősége az élsúlyozás függvényében

Helyezés: 3

Hallgatók: Borbényi Márton
Szak: Matematikus, Képzés típusa: msc, Intézmény: Eötvös Loránd Tudományegyetem, Kar: Természettudományi Kar,
Alexy Marcell
Szak: Matematika, Képzés típusa: bsc, Intézmény: Eötvös Loránd Tudományegyetem, Kar: Természettudományi Kar,
Imolay András
Szak: Matematika, Képzés típusa: bsc, Intézmény: Eötvös Loránd Tudományegyetem, Kar: Természettudományi Kar

Témavazető: Timár Ádám - tudományos főmunkatárs, N N Rényi Alfréd Matematikai Kutatóintézet, Division of Mathematics, The Science Institute, University of Iceland

Dolgozatunkban a Szabad Uniform Feszítőerdő (FSF) nevű objektumot vizsgáltuk. Ez egy valószínűségi mérték ami véges kimerítő gráfokban vett uniform feszítőfa gyenge limeszeként áll elő. Erről a végtelen véletlen részgráfról tudjuk, hogy `0`  valószínűséggel tartalmaz kört, azaz egy erdő. Ám az, hogy `1`  valószínűséggel összefüggő-e, már egy sokkal nehezebb kérdés.

Olyan gráfokkal foglalkoztunk, ami egy végtelen `d` -reguláris gráf (`mathbb{T}^d` ) szorzata egy súlyozott `H`  gráffal, ezt jelöltük `mathbb{T}^dsquare wH` -val. Pengfei Tang bebizonyította, hogy `mathbb{T}^dsquare K_2 ` FSF-je mindig összefüggő. Nekünk sikerült ezt az állítást tetszőleges `w`  számmal súlyozott `mathbb{T}^d square K_2`  esetén bebizonyítanunk. Illetve mutatunk egy bizonyítást, miszerint minden `d`  szám illetve csúcstranzitív `H`  gráf esetén van egy elég nagy `w`  konstans, amire `mathbb{T}^dsquare wH`  FSF-je összefüggő. 2020-ban Timár Ádám és Pete Gábor bebizonyította, hogy meglepő módon vannak olyan `d`  számok, illetve `H`  csúcstranzitív gráfok, amikre `mathbb{T}^dsquare H`  FSF-je nem összefüggő. Megmutatjuk, hogy bizonyításukból az is kiderül, hogy amennyiben a `H` -beli élek súlyait csökkentjük, a gráf FSF-je továbbra is nem összefüggő marad.