"Cikkosztás"
"A korreláció lecsengése véletlenített lokális algoritmusokban"
Backhausz, Szegedy és Virág cikke.
Tekintsünk olyan gráfokat, ahol minden csúcs foka d>2. Ezeken értelmezett véletlenített lokális algoritmusokat vizsgálunk. Ez lényegében az alábbit jelenti r sugarú szabály esetén: a gráf minden csúcsa kap egy véletlen cimkét a [0,1] intervallumból, egymástól függetlenül, azonos eloszlással, majd minden csúcs a saját r sugarú környezetében levő csúcsok és azok cimkéi alapján egy előre megadott szabály szerint kap egy új számot. A szabályt leíró függvény minden csúcsnál ugyanaz; lehet például az r sugarú környezetben levő csúcsok cimkéinek átlaga.
Azt láttuk be, hogy egy ilyen algoritmusban két, egymástól k távolságra levő csúcshoz tartozó valószínűségi változó korrelációjának abszolút értéke nem lehet több (k+1-2k/d)(d-1)^{-k/2}-nél, függetlenül a szabálytól, ha a gráfban nincs 2r+k+2-nél rövidebb kör, és minden csúcs foka d. Az előadásban erről az eredményről és a bizonyításhoz felhasznált Ramanujan-graphingokról lesz szó.
"Gráf homomorfizmusok és távhatás"
Brightwell és Winkler cikke.
A H gráfon egy sétát d-elágazónak nevezünk, ha minden lépés után minden elért csúcsból d újabb séta indul. Ezen séták összességére tekinthetünk a d+1-reguláris Cayley-fa H-ba menő homomorfizmusaiként. Ezen homomorfizmusok közül azok, amelyek a H gráf minden élét fedik, megfeleltethetők a gráf d+1 színnel való színezéseinek. Ebben az értelemben a séta kiindulópontja egy legfeljebb d+1-kromatikus gráfon tetszőlegesen sok lépés után meghatározza a leszármazottai konfigurációját, így a kromatikus számra ezen homomorfizmusok jellemzésével újabb alsó korlátot kapunk. Az előadás ezen eredményeket ismerteti.
"Lokális algoritmusok korlátai véletlen ritka gráfokon"
Gamarnik és Sudan cikke.
A lokális algoritmusok a gráfok csúcsain párhuzamosan futó algoritmusok, amelyek a gráf egy globális tulajdonságát számolják ki. Minden csúcs csak a saját r sugarú környezetét, valamint valamilyen véletlent használhat. Hatami, Lovász és Szegedy sejtése szerint kiszámítható a maximális független csúcshalmaz véletlen (ritka) d-reguláris gráfokon. Jelen cikk megmutatja, hogy a sejtés nem igaz, ugyanis minden lokális algoritmus által előállított független csúcshalmaz mérete legfeljebb a 1/2 + 1 / (2 * 2^(-1/2))-szerese a valódi maximumnak, ha d elég nagy. A bizonyítás fő elemeként megmutatjuk, hogy nagy d-reguláris véletlen gráfok esetén a nagy független halmazok klaszterezettek. Vagyis két nagy független halmaz metszete vagy nagyon kicsi, vagy nagyon nagy. Ez a tulajdonság azonban nem áll fenn lokális algoritmusok által előállított nagy független halmazok esetében.
"A Neumann-probléma dinamikai változata és a Lovász Local Lemma"
Belátjuk, hogy minden elég jó expandernek van nagy derékbőségű (girth) és minimális fokszámú feszített részgráfja. Új bizonyítást adunk és erősítjük Gaboriau és Lyons dinamikai megoldását a Neumann-problémára (azaz, hogy van-e minden nemamenábilis csoportnak nemkommutatív, szabad részcsoportja). Tételünk érdekes kiegészítése Bourgain és Gamburd SL_2(F_p) részcsoportjainak Cayley-gráfjára vonatkozó tételének. A tételt alkalmazzuk Thomassen nagy derékbőségű és átlagfokszámú gráfokra vonatkozó sejtésére is.
"Determinisztikus és nem-determinisztikus gráftulajdonság tesztelés"
Gishboliner és Shapira cikke.
Gráfok egy P tulajdonságát tesztelhetőnek nevezzük, ha néhány lokális vizsgálat alapján eldönthető egy gráfról, hogy igaz-e rá P, vagy epszilon-távol áll tőle. Az "epszilon-távol áll tőle" kifejezés alatt azt értjük, hogy legalább epszilon*n^2 élt kell hozzáadnunk/törölnünk az eredeti gráfhoz/gráfból, hogy az így kapott gráfra teljesüljön P. (Ahol n a gráf csúcsainak számát jelöli.)
P nem-determinisztikusan tesztelhető tulajdonság, ha létezik olyan tanúsítvány, amely alapján már könnyen ellenőrizhető, hogy a gráfra teljesül-e P.
Az előadás során azt a Lovász-Vesztergombi tételt fogjuk belátni, hogy egy tulajdonság akkor és csak akkor tesztelhető, ha nem-determinisztikusan tesztelhető. A bizonyítás során gráflimeszeket nem, a Szemerédi-féle regularitási lemmát viszont alkalmazni fogjuk.
folytatás
"Síkgráfok limesze"
Benjamini és Schramm cikke.
Tekintsük a (G_j, o_j) párokból álló sorozatot, ahol minden j-re G_j véges összefüggő gráf, o_j pedig G_j-nek egy véletlenszerűen választott csúcsa. A (G, o) párt a sorozat Benjamini-Schramm féle (gyenge) limeszének nevezzük, ha minden r>0-ra és minden (H, o') gráfra annak a valószínűsége, hogy (H, o') izomorf o_j egy r sugarú környezetével G_j-ben, konvergál annak a valószínűségéhez, hogy (H, o') izomorf o r sugarú környezetével G-ben. Megmutatjuk, hogy ha a sorozat tagjai fokszámkorlátos síkgráfok, akkor G-n egy véletlen séta 1 valószínűséggel lesz visszatérő.
"Részgráf gyakoriságok tapasztalati és extremális tulajdonságainak
feltérképezése"
Ugander, Backstrom és Kleinberg cikke.
Egy nagy szociális hálózatra tekinthetünk úgy, mint sok kis, sűrű gráf összességére. Ezeket a gráfokat a feszített részgráf gyakoriságok segítségével egy koordináta-rendszerben elhelyezve azt tapasztaljuk, hogy egy görbe mentén koncentrálódnak. Felmerül a kérdés, hogy a tapasztalt struktúra milyen mértékben "szociális" és milyen mértékben "gráf" tulajdonság. A kérdés elemzéséhez a cikk egyrészt ad egy sztochasztikus generatív modellt (az Erdős-Rényi modell egy kitejesztését, amelyben megadhatjuk egy kettő hosszú út háromszöggé válásának valószínűségét), amely jól közelíti a szociális hálózatokon tapasztalt feszített részgráf gyakoriságokat, másrészt gráfhomomorfizmus sűrűségekre megfogalmazott becslések (Kruskal-Katona, Moon-Moser és a Sidorenko-sejtés bizonyított részeinek) segítségével korlátot számolunk a feszített részgráf gyakoriságokra egy LP feladat megoldásával.
"A nemlineáris hôvezetési egyenlet sűrű gráfokon és gráflimeszek"
Medvedev cikke.
Georgi Medvedev ezen című cikkét alapul véve megvizsgáljuk, hogyan lehet diszkrét közönséges differenciálegyenletek nagy rendszereibôl határátmenettel új limesz egyenletekhez jutni és, hogy ebbôl milyen következtetéseket lehet levonni a kontinuum-limeszre vonatkozóan. Ezen túl szó esik arról is, hogy ennek mennyiben van köze a gráflimeszek, ezen belül is a grafonok elméletéhez.
"Kompaktság és véges forszolhatóság grafonokon"
Glebov, Král és Volec cikke.
Egy $W$ grafon végesen forszolható, ha létezik gráfoknak egy véges $H_1, H_2, ..., H_k$ családja úgy, hogy az ezekhez tartozó $d(H_i,W)$ sűrűségek egyértelműen meghatározzák $W$-t, vagyis ha egy $W'$ grafonra igaz, hogy $d(H_i,W)=d(H_i,W')$ minden $i$-re, akkor $W$ és $W'$ gyengén izomorf, azaz $d(H,W)=d(H,W')$ bármely $H$ gráfra.
Minden $W$ grafonhoz definiálhatunk egy $T(W)$ topológikus teret a következőképpen: $L_1[0,1]$ egy $U$ nyílt halmazára legyen $U^W$ azon $[0,1]$-beli $x$-ek halmaza, amire az $f_x^W(y)=W(x,y)$ függvény eleme $U$-nak. Legyen $T(W)$ azon $f\in L_1[0,1]$ függvények halmaza, melyekre igaz, hogy $f$ minden $U$ nyílt környezetére $U^W$ pozitív mértékű. $T(W)$ örököl egy topológiát $L_1[0,1]$-től.
Lovász és Szegedy azt sejtette, hogy minden $W$ végesen forszolható grafonhoz tartozó $T(W)$ topológikus tér kompakt.
A cikk erre a sejtésre mutat egy ellenpéldát.