és végül egy outsider cikk:
"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!
"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.
"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á.
"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.
"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.
"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.
"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.
"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.
"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 (d
"Unimoduláris véletlen fák"
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.
"Felcserélhető tömbök"
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.
"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.
10. alkalom (XI. 28.) Hermann György
Benjamini, Lyons és Schramm cikke.
11. alkalom (XII. 5.) Kunszenti-Kovács Dávid
Austin cikke.
12. alkalom (XII. 12.) Lovász László