Adott egy $n$ elemű ábécé. Tudjuk, hogy bizonyos betűk megkülönböztethetőek és néhány összetéveszthető. A Shannon-kapacitás azt vizsgálja, hogy aszimptotikusan hány olyan $t$ hosszú szó hozható létre az ábécé felhasználásával, melyek közül bármely két szó megkülönböztethető. Az ábécét tudjuk gráfokkal reprezentálni, viszont a mai napig nyitott kérdés még egyszerű gráfok Shannon-kapacitása is. Például a hét hosszú kör kapacitása sem ismert.
A kapacitás felső becslésére több függvény is ismert: frakcionális kromatikus szám, theta szám, frakcionális Haemers-korlát.
A Mycielski-konstrukció egy olyan gráfoperáció, ami növeli a gráf kromatikus számát eggyel, a klikkszámot pedig nem módosítja. Ez a konstrukció volt az egyik első példa, hogy a távolság a klikkszám és a kromatikus szám között tetszőlegesen nagy lehet.
Célunk, hogy megvizsgáljuk, hogyan hat a Mycielski-konstrukció a Shannon-kapacitást felülről becslő gráfparaméterekre. Az utóbbi években meghatároztuk a theta szám esetén érvényes összefüggést, idén pedig a frakcionális Haemers-korlátra vonatkozó formulát találtunk.
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.