Sylabus
- Charakterizace hyperkrychlí, základní vlastnosti.
- Věta o orbitě a stabilizátoru, grupa automorfismů.
- Parciální krychle, mediánové grafy, konvexní expanze.
- Neexpanzivní zobrazení, korespondence s 2-SAT.
- Párování, Grayovy kódy, Hamiltonovská dekompozice.
- Nezávislé kostry, stromy, komunikační robustnost.
- Stíny, protínající se systémy, isoperimetrické problémy.
- Problémy lineárních rozvržení, šířkové parametry.
- Vliv proměnných booleovských funkcí, harmonická analýza.
- Pakování a pokrývání, využití samoopravných kódů.
- Turánovské a související extremální problémy.
Anotace
Mnohé objekty v různých oblastech jako je teorie booleovských funkcí, extremální kombinatorika, teorie kódování, paralelní výpočty, atd. je přirozené reprezentovat jako struktury v hyperkrychlích. Přednáška nabízí přehled vybraných struktur studovaných na hyperkrychlích s důrazem na aplikace v informatice.
Nabízí i otevřené otázky pro případný vlastní výzkum. Předpokládá pouze elementární znalosti a je vhodná pro studenty magisterského cyklu.