Nagy Hálózatok Matematikája szeminárium

2014 Tavasz

Vezető: Lovász László Király Zoltán

Szerda 16:15-17:45
Pázmány Péter sétány 1/C. 3-607


Hirdetmények



1. alkalom (II. 19.)

"Cikkosztás"


2. alkalom (II. 26.) Kun Gábor

"Benjamini-Schramm approximáció, expanderek és (T) tulajdonságú csoportok"

Egy végesen generált csoport (T) tulajdonságú, ha minden ergodikus, mértéktartó hatása egy valószínűségi mértéktéren expander. A (T) tulajdonságú csoportok és az expanderek elmélete számos ponton öszefonódott, kezdve Margulis expander konstrukciójával. Belátjuk Bowen sejtését, miszerint egy végesen generált (T) csoporthoz konvergáló gráfsorozat expanderek diszjunkt uniója kell hogy legyen. Ehhez fő eszközünk az ilyen gráfsorozatok egy érdekes kombinatorikus/ergodikus/spektrális jellemzése lesz. Az előadás nem feltételezi a (T) tulajdonságú csoportok ismeretét.


3. alkalom (III. 5.) Backhausz Ágnes

"L^p grafonok és ritka gráfok limeszei"
Borgs, Chayes, Cohn és Zhao cikke.

Az előadás Borgs, Chayes, Cohn és Zhao friss cikkének (arXiv:1401.2906) ismertetése. A szerzők a sűrű gráfokra használt Lovász--Szegedy konvergenciafogalmat alapul véve olyan gráflimesz-elméletet dolgoznak ki, mely nem korlátos fokú (az egyes csúcsok fokszáma végtelenhez tart), de ritka (az élsűrűség nullához tart) gráfsorozatok esetén is alkalmazható. A limeszobjektumok itt az L^p grafonok, melyek [0,1]^2-ből R-be képező L^p-beli szimmetrikus függvények.

Az egyik fő eredmény elégséges (korlátossághoz hasonló) feltételt ad arra, hogy egy gráfsorozatnak legyen olyan részsorozata, ami a vágástávolságban konvergál egy L^p-grafonhoz. A másik, hogy L^1 grafonokhoz tartozó véletlengráf-sorozatok 1 valószínűséggel konvergálnak az eredeti grafonhoz. Az előadas célja ezen eredmények, a megfelelő fogalmak és további, kapcsolódó tételek bemutatása.


4. alkalom (III. 12.) Csóka Endre

"Általánosított mintavétel, pozitív irányított gráfok"

Legyen F egy tetszőleges gráf, ami tartalmaz 4 hosszú kört, G pedig egy grafon. Tekintsünk egy véletlen F-mintavételt G-ből, és tegyük fel, hogy a kapott élek számának eloszlása megegyezik a konstans grafonéval. Ekkor G a konstans grafon. (Az n pontú mintavételt nevezem K_n-mintavételnek, ennek értelemszerű általálonosítása az F-mintavétel, ahol csak F élei mentén tudjuk meg, hogy G-ben van-e él.)
Utána még mesél pozitív irányított gráfokról is.


5. alkalom (III. 19.) Hubai Tamás

"Pozitív gráfok"

Egy (multi)gráfot k-címkézettnek nevezünk, ha csúcsai közül k darabot megjelöltünk az 1, 2, ..., k számokkal. Két k-címkézett gráf szorzatát úgy kapjuk, hogy a diszjunkt uniójukban az azonos címkéjű csúcsokat összehúzzuk, majd elfelejtjük a címkézést.

Az (Endre múlt heti előadásában szereplő) szimmetrikus gráfok pontosan azok, amik előállnak egy alkalmas k-címkézett gráf négyzeteként. Ezek mind pozitívak abban az értelemben, hogy bármilyen, valósokkal élsúlyozott gráfba menő homomorfizmusszámuk nemnegatív. Ennek megfordítása a pozitív gráfos sejtés.

Mind a szorzat, mind a pozitivitás természetes módon kiterjeszthető gráfok formális lineáris kombinációira (ezeket kvantumgráfoknak nevezzük). Itt is könnyen látszik, hogy k-címkézett kvantumgráfok négyzete mindig pozitív, de ebben az esetben már a megfordításról is tudunk nyilatkozni: Netzer és Thom 2013-as cikke szerint ugyanis ha egy kvantumgráf pozitív, akkor tetszőlegesen jól megközelíthető címkézett kvantumgráfok négyzetösszegével.

Valószínűleg az is igaz, hogy végtelen négyzetösszeggel már pontosan is felírható. Előadásomban azt fogom megmutatni, hogy ebből az erősebb változatból már következne a pozitív gráfos sejtés.

(Az előadás a múlt hetihez kapcsolódik, de nem épül rá, minden szükséges fogalmat definiálni fogok. Az eredmények Kunszenti-Kovács Dáviddal és Lovász Lászlóval közösek.)


6. alkalom (III. 26.) Csikvári Péter

"Párosítások és problémák"

Ez az előadás két nappal a Rényi Alfréd Matematikai Kutatóintézet FIKUSZ szemináriumán tartott előadásom után lesz (lásd itt), a FIKUSZ előadáson azonban nem lesznek bizonyítások. Így arra gondoltam, hogy nem tervezem meg szigorúan ezt az előadást: mesélek mindenféléről, de ha valakit érdekel egy hétfőn elmondott tétel bizonyítása akkor annak elmondására is szívesen vállalkozom. Egyébként főleg nem a saját vagy társszerzőim tételeiről beszélnék hanem mások eredményeiről és hogy milyen kérdéseket vetnek fel ezek az eredmények. Előre figyelmeztetek mindenkit, hogy nem ez lesz a valaha volt legjobban megtervezett előadás.


7. alkalom (IV. 2.) Backhausz Ágnes

"L^p grafonok és ritka gráfok limeszei"
Borgs, Chayes, Cohn és Zhao cikke.

Az előadás Borgs, Chayes, Cohn és Zhao friss cikkének (arXiv:1401.2906) ismertetésének folytatása. A szerzők olyan gráflimesz-elméletet dolgoznak ki, mely nem korlátos fokú (az egyes csúcsok fokszáma végtelenhez tart), de ritka (az élsűrűség nullához tart) gráfsorozatok esetén is alkalmazható. A limeszobjektumok itt az L^p grafonok, melyek [0,1]^2-ből R-be képező L^p-beli szimmetrikus függvények.

Az egyik fő eredmény elégséges (korlátossághoz hasonló) feltételt ad arra, hogy egy gráfsorozatnak legyen olyan részsorozata, ami megfelelő normálás után vágástávolságban konvergál egy L^p-grafonhoz. Az előadásban részben arról lesz szó, hogy ehhez az eredményhez milyen regularitási lemmák szükségesek és azok hogyan bizonyíthatók, részben pedig arról, hogy ebből az elégséges feltételből hogyan következik, hogy a gráfsorozatban az átlagos fokszám végtelenhez tart (egyszerű gráfokból álló sorozat esetén).


8. alkalom (IV. 23.) Deák Attila

"How unproportional must a graph be?"
Humberto Naves és Oleg Pikhurko cikke.

Legyen u_k(G,p) = max_{F,|V(F)|=k}|inj(F,G)-E(inj(F,G(n,p)))|, azaz legfeljebb mennyire térhet el egy n csúcsú gráfban F indukált példányainak száma a G(n,p) Erdős-Rényi gráfban való F példányszám várható értékétől. Ez azt méri, hogy egy G gráf mennyire van messze a p-kvázirandomtól, ha k csúcsú tesztgráfokat használhatunk.

Az előadásban azt fogom megmutatni, hogy u_k(G,p) minimuma k>= 4 esetén n^{k-2} nagyságrendű. Azaz a statisztikákkal nem tudjuk ennél jobban megközelíteni a G(n,p)-beli várható értéket.


9. alkalom (V. 7.) Kunszenti-Kovács Dávid

"Multigráf limeszek és Banach tér értékű grafonok"

Egy Lovász Lászlóval és Szegedy Balázzsal közösen íródó cikk eredményeit szeretném bemutatni. Multigráfok olyan csúcs-és-él homomorfizmusok szerint konvergens sorozataihoz óhajtunk limesz objektumot definiálni, amelyek mentén nincsen globális korlát az élmultiplicitásokra. Rámutatok, hogy a kompakt dekorációknál használt megfogalmazás milyen akadályokba ütközik, és ez hogyan küszöbölhető ki egy még absztraktabb, Banach tér értékű dekorációs kontextusban. A funkcionálanalízis nagyon hasznos nyelvezetet és segédeszközöket biztosít, de igyekszem mindvégig a konkrét kombinatorikus értelmezéssel kiegészítve emészthetővé tenni az előadást.


10. alkalom (V. 14.) Csiszárik Adrián és Hermann György

"Szociális hatás maximalizálása közel optimális időben"
Borgs, Brautbar, Chayes és Lucifer cikke.

Pletykák, fertőzések, marketing kampányok hatása terjedésének vizsgálatára gyakran használják a független kaszkád modellt. Ebben a modellben egy irányított gráfban adott kezdőcsúcsokból kiindulva, az élek mentén lépésenként, az élekre írt valószínűségek szerint, egy véletlen folyamatként terjed a hatás. Azt az algoritmikus feladatot tekintjük, hogy adott G gráfra és k-ra mely k darab kezdőcsúcsból indítsuk a folyamatot, hogy a hatás várható értékét maximalizáljuk. A cikkben a szerzők egy (1-1/e-\eps)-approximációs algoritmust adnak, amely O((m+n)\eps^{-3} \log n) időben fut, ami közel optimális: konstans approximációhoz \Omega(m+n) alsó korlátot adunk a futási időre. Az algoritmus randomizált, és 3/5 valósznűséggel ad helyes választ, a hiba azonban detektálható. Az algoritmus módosítható úgy, hogy az approximáció minőségéből áldozva, korai leállítással hamarabb véget érjen.

"Partíciófüggvények karakterizációja különböző modellekben"
Schrijver cikke.

A Freedman, Lovász és Schijver által bevezetett kapcsolási mátrix tulajdonságaival karakterizáljuk, hogy mely gráfparaméterek állnak elő a csúcsmodell illetve a spin-modell partíciófüggvényeiként abban az esetben, ha a súlyokra komplex értékeket is megengedünk. Az eredmény a két modellben hasonló: egy gráfparaméter akkor és csak akkor áll elő ilyen partíciófüggvényként, ha a gráfparaméter értéke az üres gráfon nulla, a paraméter kapcsolási mátrixának a rangja pedig exponenciálisan korlátozott.