Leírás
Kannan, Tetali és Vempala állította fel azt a sejtést, hogy
tetszőleges fokszámsorozat realizációin a swap Markov lánc gyorsan
kever. Először Cooper, Dyer és Greenhill igazolta a sejtést reguláris
fokszámsorozatokra. Az ő munkájuk során sok részeredmény született, de
sokáig mindegyik eredmény valamilyen értelemben reguláris (közel
reguláris, félig reguláris, stb.) fokszámsorozatokról szólt. Először
Greenhill igazolta a sejtést ritka, irreguláris fokszámsorozatokra. A
közelmúltban sikerült sűrű és irreguláris fokszámsorozatokra igazolni
a Kannan-Tetali-Vempala sejtést. Ez az eredményünk és Greenhill
eredménye alapján könnyen igazolható az is, hogy egy tetszőleges
Erdős-Rényi random gráf fokszámsorozata nagy valószínűséggel olyan,
amelyek realizációin a swap Markov lánc gyorsan kever. Nemrégiben az
eredményeinket sikerült általánosítani. Sikerült bizonyítani, hogy
minden ún. stabil fokszámsorozat realizációin a swap Markov lánc
gyorsan kever. Megmutatható, hogy minden lambda nagyobb mint 2
paraméterű skálafüggetlen gráf fokszámsorozata nagy valószínűséggel
stabil, így a realizációin a swap Markov lánc szintén gyorsan kever.
Sikerült megadnunk egy instabil fokszámsorozatot, és bizonyítani, hogy
annak a realizációin is a swap Markov lánc gyorsan kever. Végül
megmutattuk azt is, hogy minden instabil fokszámsorozat vagy
dekomponálható kisebb fokszámsorozatokra vagy van olyan realizációja,
amelynek egy nagy feszített részgráfjának a fokszámsorozata pontosan
az az instabil fokszámsorozat, amely realizációin a gyors keverést
bizonyítottuk.
Közös munka Erdős Péterrel, Mezei Tamással, Soltész Dániellel, Soukup
Lajossal és Catherine Greenhillel.