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

2012 Ősz

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


A félév során kiemelten foglalkozunk a nyári princetoni konferencia érdekes cikkeivel, főleg az alábbiakkal:

1. alkalom (IX. 19.) Szegedy Balázs

"Nem standard módszerek a struktúra limesz elméletekben"

Az előadás célja bemutatni egy eszköztárat. ami meglepően hasznosnak bizonyul nagy struktúrák megértésében. Ez magába foglalja az ultra szorzat terek mérték és integrál elméletét, illetve topologikus tulajdonságait. Számtalan felhasználás közt szerepel a hipergráfok limesz elmélete, Gowers normák analizálása, illetve a graphingok elmélete.

Utána cikkosztás lesz!


2. alkalom (IX. 26.) Backhausz Ágnes

"Martingálelméleti módszerek alkalmazása véletlen gráfok vizsgálatára"
Backhausz Ágnes és Móri Tamás cikke.

Két olyan véletlen gráfmodellt vezetünk be, ahol a megszülető csúcs szomszédainak kiválasztásakor nem csupan a régi csúcsok fokszáma, hanem a csúcsok adott csoportjának valamely jellemzője határozza meg a csoport kiválasztásának valőszínűségét. Martingálelméleti módszerekkel sikerült bizonyítani, hogy a d fokszámú csúcsok aránya 1 valószínűséggel konvergál valamely c_d>0 konstanshoz mindkét esetben minden lehetséges d egész számra. A (c_d) számsorozat polinomiálisan cseng le, amint d végtelenhez tart, vagyis skálafüggetlen viselkedést találtunk.


3. alkalom (X. 3.) Hubai Tamás

"Az interpolációs módszer kombinatorikus alkalmazása és véletlen ritka gráfok skálalimesze"
Bayati, Gamarnik és Tetali cikke.

Ritka gráfok két véletlen modelljével foglalkozunk: az Erdős-Rényi gráfban N csúcs között cN élt húzunk be egymástól függetlenül, a véletlen r-reguláris gráfnál pedig az összes r-reguláris közül választunk egyet egyenletes eloszlással.

Megmutatjuk, hogy ha N a végtelenhez tart, akkor a független pontok maximális aránya egy csak c-től ill. r-től függő értékhez konvergál. Ugyanez igaz a maximális vágás ill. a legnagyobb q-osztályú feszítő részgráf méretére N-nel normalizálva és még három másik (hiper)gráfparaméterre.

A bizonyítás alapötlete az interpolációs módszer, vagyis az, hogy két véletlen gráf diszjunkt unióját lépésenként alakítjuk át egyetlen véletlen gráffá.


4. alkalom (X. 10.) Bencs Ferenc

"Permutáció-sorozatok limesze"
Hoppen, Kohayakawa, Moreire, Ráth és Sampaio cikke.

A cikk nyomán megvizsgáljuk a permutáció sorozatokat, majd definiálunk a részpermutáció-sűrűség segítségével konvergenciát ezek közt. Ki fog derülni, hogy ezen konvergens sorozatokhoz definiálhatunk limesz objektumokat, melyek speciális Lebesgue-mérhető függvények. Bizonyítani fogjuk, hogy minden limesz objektum határértéke egy permutáció sorozatnak, és ezen határértékek lényegében egyértelműek. Látni fogjuk azt is, hogy ezen konvergencia fogalom metrizálható lesz a limesz objektumokkal kibővített kompakt térben, amiben a permutációk sűrű halmazt alkotnak.


5. alkalom (X. 17.) Blázsik Zoltán

"Kvázirandom permutációk karakterizációja"
Král és Pikhurko cikke.

Kombinatorikus objektumok kvázirandomságát már több különböző struktúra esetén részletesen megvizsgálták. Chung, Graham és Wilson megmutatták,hogy ha egy nagy gráfban a 4 csúcsú részgráfok sűrűsége aszimptotikusan ugyanolyan, mint a véletlen gráfban, akkor bármely k csúcsú részgráf sűrűsége is aszimptotikusan ugyanolyan lesz. Ez a cikk egy hasonló karakterizációs tételt lát be permutációk esetén; bevezeti a P(k) tulajdonság fogalmát és megmutatja,hogy a P(4) tulajdonságból következik a P(k) tulajdonság minden k-ra. Végül belátja, hogy a permutáció-sorozat kvázirandomsága ekvivalens a P(4)tulajdonsággal.


6. alkalom (X. 24.) Mezei Tamás

"Nagy eltérés tétel Erdős-Rényi gráfokra"
Chatterjee és Varadhan cikke.

A nagy eltérések elmélete azt vizsgálja, hogy bizonyos események valószínűsége milyen gyorsan csökken, miközben az eloszlás egy paramétere a végtelenhez tart. Egy ilyen tételt szeretnénk E-R gráfokra belátni (az élek bevételének a valószínűség legyen fix, a csúcsszám pedig tartson végtelenhez). Ehhez szükségünk lesz a grafonok elméletéből néhány alaperedményre, illetve Szemerédi lemmájának egy változatára is. Ezután megvizsgáljuk, hogy általában hogyan is néz ki egy E-R gráf, ha egy ritka esemény következett be. Ennek alkalmazásaként körüljárjuk azt a kérdést, hogy ha a háromszögek száma az E-R gráfban 1+epszilonszorosa a várható értéknek, akkor hogyan is néz ki az E-R gráf.


7. alkalom (XI. 7.) Csóka Endre

"Korlátos fokú gráfok tesztelhető paraméterei"

Azt a kérdéskört vizsgáljuk, hogy ha kapunk egy hatalmas, de korlátos fokú gráfot, akkor mik azok a tulajdonságai, paraméterei, amiket már valamiféle konstans méretű mintavételezéssel is jól megbecsülhetünk. Ennek, vagyis a korlátos fokú gráfok Benjamini-Schramm elméletének, és ahhoz kapcsolódóan a lokális algoritmusok elméletének az eddigi eredményeit igyekszem bemutatni, benne számos új, még publikálatlan, vagy frissen publikált eredménnyel. A témának az eredeti motivációit más természettudományok adták, de az azóta újabb, meglepő kapcsolatokra is fény derült. Az innen származó Aldous-Lyons sejtésről például kiderült, hogy mély csoportelméleti jelentőséggel bír. Továbbá arra is mutatkozik remény, hogy ebből a témából nő majd ki az az eszköztár, amivel matematikailag jobban megfoghatunk olyan állításokat, amik igazak a gyakorlatban előforduló gráfokra, de nem minden gráfra.


8. alkalom (XI. 14.) Deák Attila

"Exponenciális véletlen gráf modellek"
Chatterjee és Diaconis cikke.

Sourav Chatterjee, Persi Diaconis: Estimating and understanding exponential random graph models c. cikket fogom elmondani.

Legyenek T_1, T_2, ..., T_k gráfokon értelmezett függvények (élszám, háromszögek száma, csillagok száma,...). Ezen függvények segítségével akarunk véletlen gráfokat generálni, és ezeket vizsgálni. Egy G gráf kiválasztásának valószínűsége exp(sum b_i*T_i)-vel arányos.
A különféle vizsgálatokhoz fontos, hogy kiszámoljuk, vagy legalábbis megbecsüljük a normalizáló konstanst. Erre fogok mutatni egy módszert, ami bizonyos b_i-k esetén megadja ezt.
Bizonyos paraméterértékek esetén a kapott véletlen gráfok egy E-R gráfhoz hasonlóan fognak viselkedni, de nem minden model eredményez E-R-hez hasonló gráfot.


9. alkalom (XI. 21.) Szűcs Gábor

"Nagy átmérőjű csúcs-tranzitív gráfok"
Benjamini, Finucane és Tessera cikke.

Legyen (X_n) véges, összefüggő, csúcs-tranzitív gráfok egy sorozata, ahol |X_n| = o(diam(X_n)^q), q>0. Ekkor van egy olyan részsorozata, amely (újraskálázva) Gromov-Hausdorff távolságban konvergál egy d dimenziós, invariáns Finschler-metrikával elátott tóruszhoz (d1 és q elég kicsi, akkor (X_n) konvergál egy körhöz.


10. alkalom (XI. 28.) Hermann György

"Unimoduláris véletlen fák"
Benjamini, Lyons és Schramm cikke.

Cayley-gráfok gyökeres unimoduláris véletlen fáit (URT) és invariáns erdőit vizsgáljuk. Ezt az eszköztárat tekintjük át, megadva egy karakterizációt a korlátos fokú URT-kre. Ennek felhasználásával adunk egy új bizonyítást arra, hogy minden URT szofikus mértéket generál.


11. alkalom (XII. 5.) Kunszenti-Kovács Dávid

"Felcserélhető tömbök"
Austin cikke.

Tim Austin júniusi princetoni előadását követve bemutatom a felcserelhető tömbök elméletét, néhány főbb eredményt és azok kapcsolatát a gráflimeszekkel. Sok szempontból ekvivalensnek tekinthető a két elmélet, de a különböző formalizmusok miatt hol az egyik, hol a másik használata lehet célravezetőbb.

Az első eredmények felcserélhető val. változókról de Finettitol származnak a 30-as évekből, de lényegében a 80-as évekig kellett várni a többdimenzios, és így a gráfokhoz is kapcsolható változatokra.


12. alkalom (XII. 12.) Lovász László

"Borel gráfok, grafingok és gráf-limeszek"

A korlátos fokú gráfok limeszeinek egyik lehetséges leírása "grafing"-ok segítségével történik. Az előadásban áttekintjük az ehhez szükséges, önmagában is érdekes és nem-triviális elméletet, a Borel gráfok elméletét, a grafingok néhány ismert és új tulajdonságát, és azt a kérdést, hogy milyen gráf-tulajdonságok örökíthetők át a limesz-grafingra.