"A regularitási partíció egyértelműségéről"
A gráfelmélet alapvető segédeszköze Szemerédi Regularitási Lemmája, mely adott megngedett hibához minden gráfnak egy partícióját adja. Aszerint, hogy hogyan mérjük a hibát, beszélhetünk "eredeti" partícióról (Szemerédi), "gyenge" partícióról (Frieze-Kannan), és "erős" partícióról (Alon-Fischer-Krivelevich-Szegedy M. és mások).
Mivel a gráfnak lehet tranzitív automorfizmus-csoportja, egyik fajta partíció sem lehet egyértelmű, de ez megengedi, hogy a "váz" gráf (template) lényegében egyértelmű legyen. Egyszerű példák mutatják, hogy a gyenge és eredeti partícióknak a váza sem egyértelmű. Alon, Shapira és Stav megmutatta, hogy az "erős" változatra alkalmas paraméterek mellett bizonyítható egyértelműség. Megmutatható az is, hogy még a "gyenge" partíció váza is lényegében egyértelmű egy aszimptotikus értelemben.
A bizonyítások egyik érdekes segédeszköze Pikhurko egy tétele, melyben két gráf "szerkesztési" (edit) távolságát és annak egy tört-változatát hasonlítja össze.
Jan Hladky, Andras Mathe, Viresh Patel, Oleg Pikhurko:
Poset limits can be totally ordered
http://arxiv.org/abs/1211.2473
"Korlátos fokú nagy gráfok és az Aldous--Lyons sejtés"
Tekintsük azokat a gráfokat, melyek minden csúcsának fokszáma legfeljebb egy megadott konstans. Egy ilyen G gráf minden csúcsához vegyük annak r sugarú környezetét. Ezen környezetek eloszlását a G gráf r-környezetstatsztikájának nevezzük. A korlátos fokú gráfok elméletének egy központi kérdése, hogy milyen eloszlások állnak elő r-környezetstatisztikaként, pontosabban ezek limeszeként. Ennek van egy ismert természetes feltétele, az azonban nem világos, hogy ez a feltétel elégséges-e. Aldous és Lyons még sejtésként fogalmazta meg az elégségességet, mára azonban sokkal kétségesebbnek tarják. Előadásomban a kérdést, annak jelentőségét, és néhány ezzel kapcsolatos eredményt fogok bemutatni.
"Hipergráfok limeszei martingálokkal"
Zhao cikke.
Az előadás témája Yufei Zhao: 'Hypergraph limits via martingales' című cikke, mely Elek Gábor és Szegedy Balázs 2012-es, hipergráfok sűrű értelemben vett konvergenciájáról és a limeszobjektum létezéséről szóló tételére ad új bizonyítást, ultralimeszek felhasználása nélkül. A szerző a gráfokra vonatkozó korábbi eredmény (Lovász László és Szegedy Balázs, 2006) martingálos bizonyításához tér vissza, és élszínezésekkel, valamint lineáris egyenletek beépítésével fogja meg a hiperélekben megjelenő együttes eloszlásokat és információtöbbletet.
"Részben rendezett halmazok limesze teljesen rendezhető"
Hladky, Máthé, Patel és Pikhurko cikke.
A gráf-limeszhez hasonlóan definiálható részben rendezett halmazok limesze
is. Konvergens részben rendezett halmazok limesze egy (S,F,mu,<<,W)
kernel, ahol (S,F,mu) egy valószínűségi mező, << egy részben rendezés ezen
a mezőn, W: SxS->[0,1] pedig FxF mérhető függvény, amire igaz hogy:
W(x,y)>0 => x<<y
W(x,y)>0 és W(y,z)>0 => W(x,z)=1
S. Janson megmutatta, hogy a limesz választható úgy, hogy (S,F,mu)=([0,1],B,lambda), ahol B a Borel szigma-algebra, lambda pedig a Lebesgue-mérték.
A cikkben megmutatják, hogy a limesz választható úgy is, hogy << a standard rendezés a [0,1]-en, ezzel a limesz teljesen rendezett lesz. Erre mutatnak egy kombinatorikus és egy valós analízist használó bizonyítást. A szemináriumon vázolom a valós analízist hasznaló bizonyítást és a kombinatorikus bizonyításhoz használt Regularitási Lemmát.
"Felfújt gráfok előfordulása feszített részgráfként"
Hatami, Hirst és Norine cikke.
Egy gráf felfújtját úgy kapjuk, hogy minden csúcsot kicserélünk véges sok csúcsra, és két új csúcsot pontosan akkor kötünk össze, ha a hozzájuk tartozó eredeti csúcsok között futott él. Ha a kiindulási gráf minden csúcsát ugyanannyi csúccsal helyettesítjük, akkor egyenletes felfújtról beszélünk.
Megmutatjuk, hogy ha egy G gráf a lehető legtöbb feszített példányt tartalmazza H egy elég nagy egyenletes felfújtjából (a G-vel azonos csúcsszámú gráfok közül), akkor G maga is majdnem felfújtja H-nak. Ez aszimptotikus választ ad Bollobás, Egawa, Harris és Jin egy 1995-ös kérdésére.
"The entropy of random-free graphons and properties"
Hatami és Norine cikke.
Every graphon defines a random graph on any given number n of vertices. It was known that the graphon is random-free (0-1 valued almost everywhere) if and only if the entropy of this random graph is subquadratic. We prove that for random-free graphons, this entropy can grow as fast as any subquadratic function. However, if the graphon belongs to the closure of a random-free graph property, then the entropy is O(n*log n). We also give a simple construction of a non-stepfunction random-free graphon for which this entropy is linear, refuting a conjecture of Janson.
"Kvázimonoton gráfok"
Bollobas, Janson és Riordan cikke.
We call kernel or graphon a symmetric function $W$ on $[0,1]$ as the representation of the limit of a convergent $(G_n)$ graph sequence. In this context it is natural to investigate the relationship between specific properties of the the sequence and the kernel. In this paper it is shown that the kernel is monotone if and only if the sequence satisfies a `quasi-monotonicity' property.
"Benjamini-Schramm convergence and Betti numbers"
In the talk I will review sparse convergence and derive one of its most important consequences, the convergence of the normalized Betti numbers of simplicial complexes. The proof goes through spectral theory. All the notions will be introduced.
"The Ajtai-Komlos-Simonovits-Szemeredi decomposition of possibly sparse
graphs"
Hladky, Komlós, Piguet, Simonovits, Stein és Szemerédi cikke.
I will talk about a decomposition technique which Ajtai, Komlos, Simonovits, and Szemeredi developed to attack the Erdos-Sos tree embedding conjecture, and which we (together with Komlos, Piguet, Simonovits, Stein, and Szemeredi) used to attack the Loebl-Komlos-Sos Conjecture. The decomposition applies to all graphs - dense or sparse - and extends the Szemeredi Regularity decomposition.
The only prerequisite needed is the knowledge of the Regularity Lemma and its proof.
"Factor of iid élszínezések"
A lokális algoritmus fogalmának egy természetes kiterjesztése a factor of iid folyamat. A factor of iid gráfszínezések kérdése egy vizsgált terület, melynek egyik fontos eredménye, hogy k fokszámkorlátos gráf csúcsszínezhető k+1 színnel. Ebből következik, hogy élszínezhető is 2k-1 színnel. Előadásomban mutatok egy factor of iid folyamatot, ami minden d fokszámkorlátos gráf éleit kiszínezi d+o(d) színnel, páros gráfokra pedig d+1 színnel mutatjuk meg ugyanezt.