Struktury v hyperkrychlích

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.