Seznámit se s problematikou hyperkrychlí.

The course gives an introduction into the area of hypercube problems.

Předmět je ukončen zkouškou.

The course is finished by an exam.

• B. Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, Cambridge, 1986.

• R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2011.

• S. Jukna, Extremal Combinatorics with Applications in Computer Science, Springer, Berlin, 2001.

• F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.

• vybraná časopisecká literatura.

• B. Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, Cambridge, 1986.

• R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2011.

• S. Jukna, Extremal Combinatorics with Applications in Computer Science, Springer, Berlin, 2001.

• F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.

• selected journal papers.

Zkouška se skládá z písemného řešení tří sad domácích úloh v průběhu semestru a ústní zkoušky. Výsledná známka je určena ze 60% hodnocením řešení domácích úloh a z 40% hodnocením ústní zkoušky.

The exam consists of solving three sets of exercises during the semester and an oral exam. Average exercise grade will cover 60% of the final mark, and the other 40% will be given for the oral exam.

• 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.

• Hypercube characterizations, basic properties.

• Orbit and stabilizer theorem, group of automorphisms.

• Parcial cubes, median graphs, convex expansion.

• Nonexpansive maps, correspondence to 2-SAT.

• Matchings, Gray codes, Hamiltonian decomposition.

• Independent spanning trees, robustness of communication.

• Shadows, intersecting systems, isoperimetric problems.

• Linear layout problems, width parameters.

• Influence of variables of boolean functions, harmonic analysis.

• Packing and covering, applications of self-correcting codes.

• Turán numbers and other extremal problems.