Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
Gráfok, kapacitások, entrópiák: Bevezetés az információelméleti kombinatorikába
A tantárgy angol neve: Graphs, Capacities, Entropies: Introduction to Information Theoretic Combinatorics
Adatlap utolsó módosítása: 2022. június 10.
A gráfelmélet, a lineáris algebra, illetve a valószínűségszámítás alapvető ismereteit tartalmazó kurzusok elvégzése után célszerű felvenni.
Annak bemutatása, hogy az információelmélet eszköztára és problémafelvetései hogyan váltak gyümölcsözővé a kombinatorikában és a gráfelméletben. Ezzel kapcsolatos alapvető eredmények megismertetése és ennek keretében a diszkrét matematikai gondolkodás további fejlesztése.
1. Gráfok Shannon kapacitása, e paraméter legegyszerűbb korlátai (klikkszám és kromatikus szám), az ötszögprobléma, a problémakör gráfelméleti hatása: perfekt gráfok bevezetése.
2. Néhány fontosabb gráfosztály perfektsége, Perfekt Gráf Tétel és Erős Perfekt Gráf Tétel, Helyettesítési Lemma. 3. További érdekes gráfcsaládok: Kneser gráfok, Mycielski gráfok, normális gráfok, normális gráfok perfektsége.
4. Frakcionális kromatikus szám fogalma, kapcsolata a lineáris programozással, a hagyományos kromatikus számtól való lehetséges eltérése, értéke csúcstranzitív gráfokon. Gráfhomomorfizmus fogalma, színezési paraméterek jellemzése gráfhomomorfizmusok segítségével.
5. Csatorna zéró-hiba kapacitása visszacsatolás mellett, ennek kapcsolata a frakcionális kromatikus számmal, Lovász tétele a frakcionális és a hagyományos kromatikus szám lehetséges arányáról, McEliece-Posner tétel.
6. Lovász-féle theta függvény, az ötszögprobléma megoldása.
7. Bohman-Holzman tétel a páratlan körök Shannon kapacitásáról, Shannon kapacitás és Ramsey számok kapcsolata.
8. Gráfok Witsenhausen hányadosa, ennek kapcsolata a Shannon kapacitással.
9. Irányított gráfok Sperner kapacitása, ennek korlátai.
12. Gráfentrópia fogalma, információelméleti interpretációja, főbb tulajdonságai, szubadditivitásának alkalmazása.
13. Additivitási kérdések, perfekt gráfok jellemzése a gráfentrópia segítségével.
14. Kahn és Kim gráfentrópián alapuló algoritmusa részben rendezés teljes rendezéssé történő kiterjesztésére.
Heti 4 óra előadás.
szóbeli vizsga
Személyes egyeztetés alapján, fogadóórákon
Imre Csiszár, János Körner: Information Theory. Coding Theorems for Discrete Memoryless Systems, Second Edition, Cambridge University Press, 2011
László Lovász: Graphs and Geometry, American Mathematical Society, 2019
Edward R. Scheinermann, Daniel H. Ullman: Fractional Graph Theory, Wiley 1997
