Regularitási módszernek a Regularitási lemma és a Blow-up lemma (beágyazó lemma) együttes használatát szokás hívni. Rendkívül hatékony extremális gráfelméleti kérdésekben, több száz tétel bizonyításának adja a gerincét. Hátránya, hogy a Regularitási lemma csak "csillagászati" méretű gráfokra hasznos igazán.
Az előadásban egy olyan módszert láthatunk, ami a Regularitási lemmát képes kiváltani bizonyos esetekben, úgy, hogy a Blow-up lemma (mely kis gráfokra is érvényes) továbbra is használható legyen. A módszer működésének demonstrálására egy fa beágyazási tétel bizonyítását tekintjük: ha az $n$ csúcsú G gráf minimális foka legalább $n/2 +\varepsilon n$ valamely $\varepsilon >0$-ra, és $T$ egy $n$ csúcsú, korlátos fokú fa, $n$ elég nagy, akkor $T$ feszítőfája $G$-nek.
Ez egy ismert tétel. Bollobás sejtése volt 1978-ból, kb. 20 évre rá bizonyította Komlós, Sárközy és Szemerédi a Regularitási lemma használatával. 2010-ben beláttuk egy Nagy-György Judittal, Ian Levittel és Szemerédi Endrével közös cikkben, már a lemma használata nélkül, viszont így jóval bonyolultabban a tétel első bizonyításánál.
A legújabb bizonyítás előnye, hogy a Regularitási módszer több eleme is átvihető, de "kis" gráfokra is működik. Újdonság még emellett, hogy egy erősebb, ún. stabilitási változatot bizonyítunk: ha $G$ nincs nagyon közel két extremális esethez (két diszjunkt klikk uniója ill. teljes páros gráf), akkor $n/2-\varepsilon n$ -es minimális fokszám is elegendően nagy a tartalmazáshoz.
Egy $G(V,E)$ gráf esetén a $G^{(k)}$ gráf jelölje a $G$ pontos $k$-távolság gráfját, aminek csúcshalmaza megegyezik $V$-vel, és két csúcsot pontosan akkor köt össze él $G^{(k)}$-ban, ha $G$-ben a távolságuk pontosan $k$ volt (a csúcsok címkézettek). Az előadásban vizsgálandó kérdést a következő játék formájában vezetném be: Alice gondol egy egyszerű gráfra, és Bob feladata a gráf rekonstruálása, amihez csupán $k\ge 2$ pozitív egészekre a $G^{(k)}$ pontos $k$-távolságok gráfok egy általa választott részét használhatja.
A rekonstruáláshoz Bobnak lehetősége van elkérnie Alicetól bizonyos $k$ értékekre a gondolt gráf pontos $k$-távolság gráfjait. Az első kérdés az, hogy egyáltalán biztos-e, hogy Bob ki tudja találni a gondolt gráfot. Látjuk majd, hogy ha a gondolt gráf nem feltétlenül összefüggő, akkor nem feltétlenül tudja kitalálni. Ha Alicenak összefüggő gráfra kell gondolnia, akkor igazolható, hogy Bob mindig ki tudja találni a gráfot. (HF)
Megmutatjuk, hogy a triviális kitalálhatóságnál jóval több is igazolható, mindig elég csupán konstans sok $k$-ra elkérni a $G^{(k)}$ gráfokat. Sőt igazolni fogjuk, hogy az eredményünk éles is! Az eredmények Horváth Csongorral és Zsigri Bálinttal közösek.
We investigate the two-graphs associated with strongly regular polar graphs that belong to three infinite classes. Specifically, we examine the strongly regular graph $\Gamma(O^\pm(2m,2))$, which has vertices representing points of a nondegenerate hyperbolic or elliptic quadric $Q^\pm(2m-1,2)$ in the projective space $PG(2m-1,2)$. The set of vertices for $NO^\pm(2m,2)$ is the complement of $Q^\pm(2m-1,2)$. Additionally, we consider the vertices of the third graph $NO^\pm(2m+1,q)$, where $q$ is even, which correspond to hyperplanes of $PG(2m,q)$ that intersect the nondegenerate parabolic quadric in a nondegenerate hyperbolic or elliptic quadric.
Our main result is the proof of switching equivalence for the strongly regular polar graphs $NO^\pm(4m,2)$, $NO^\mp(2m+1,4)$, and $\Gamma(O^\mp(4m,2))$ with an isolated vertex. We establish this by providing an analytic description for these graphs and their corresponding two-graphs.
Adott, esetleg végtelen gráfhoz olyan lokális algoritmusokat vizsgálunk, amelyek a csúcsok által generált véletlen input felhasználásával lokális számolás után csúcsonként adnak ki egy outputot, például egy színezést. Az ilyen osztott számítási problémák keretei hasznosak kombinatorikai és optimalizálási problémákban (például független halmaz keresése véletlen gráfban), valamint valószínűségi modellek generálásában (pl. Ising, Uniform Feszítőerdő).
Az előadás ezen nagy témakör néhány érdekes eredményét ismerteti, és semmilyen előismeretet nem feltételez.