|
|
|
|||||||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Csonka Bence: A Shannon-kapacitás és a Mycielski-konstrukció kapcsolata |
|
|||
|
|
||||
|
||||
| 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. |
||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013
