**Meeting:** Thursday 8:30-10:00 in the corridor 301.

**Lecturer:** Petr Gregor (gregor(at)ktiml.mff.cuni.cz)

**Course Information:** 2/0 Zk NTIN097 in SIS

**Homework**

To be assigned later.

**Lectures and lecture note assignments**

(From the previous years.)

- Lecture 1: Hypercubes, alternative definitions, basic properties, history of hypercube architectures.
*(scribe by David Pěgřímek)* - Lecture 2: Cayley graphs, orbit-stabilizer theorem, automorphisms of hypercubes.
*(scribe by Václav Vlček)* - Lecture 3: Structure of the automorphism group, distance-transitivity, symmetry breaking, distinguishing number.
*(scribe by Otakar Trunda)* - Lecture 4: Characterizations of hypercubes - a survey.
*(scribe by Vladislav Čunát)* - Lecture 5: Partial cubes, Djokovic-Winkler relation, median graphs, Mulder's convex expansion, Euler-type formula.
*(scribe by Kryštof Měkuta)* - Lecture 6: Nonexpansive maps, (weak) retracts, median sets, correspondence to 2-SAT.
*(scribe by Václav Vlček)* - Lecture 7: Retraction to a connected median set, distance center, fixed cube theorem.
*(scribe by Otakar Trunda)* - Lecture 8: Matchings and their spectra, maximal matchings, forcing number.
*(scribe by Kryštof Měkuta)* - Lecture 9: Counting perfect matchings, Fink's theorem, decomposition to Hamiltonian cycles, semiperfect 1-factorization.
*(scribe by David Pěgřímek)* - Lecture 10: Gray codes (reflected, monotone, ...), middle level problem, symmetric chain decomposition.
*(scribe by Václav Vlček)* - Lecture 11: Independent spanning trees, matrix-tree theorem, spectrum of the hypercube, two-rooted complete binary trees.
*(scribe by Petr Gregor)* - Lecture 12: Shadows (Kruskal-Katona theorem), intersecting families (Erdos-Ko-Rado theorem), vertex-isoperimetric problem.
*(scribe by Petr Gregor)* - Lecture 13: Edge-isoperimetric problem, linear arrangement, cutwidth, vertex separation, sumcut, bandwidth, pathwidth.
*(scribe by Vladislav Čunát)* - Lecture 14: Spanners, (local) detour subgraphs of small size / max. degree.
*(scribe by David Kuboň)* - Lecture 15: Vertex Turán numbers, s-face transversals, binary covering arrays.
*(scribe by Miloš Chromý)* - Lecture 16: Bootstrap percolation in hypercubes.
*(scribe by Vladan Glončák)*

**Course Description**

In this course we overview selected problems studied in hypercubes with emphasis on applications in theoretical computer science. Invitation (in Czech).

**Prerequisites**

I assume only elementary knowledge. The course is suitable for all students in the M.Sc. programme.

**Evaluation**

Average exercise grade will cover 70% of the final mark, and the other
30% will be given for graded scribes.

**Related Material**

There is no textbook for this (rather unusual) course, the scribes will contain recommended literature for each topic.

**Note**

Please let me know if you find some error in lecture scribes or if you have a solution to any of listed problems.