**Meeting:** Tuesdays at 15:40 in my office (room 305).

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

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

**Homework**

**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, semi-induced matchings.
*(scribe by Kryštof Měkuta, Markéta Calábková)* - Lecture 9: Counting perfect matchings, Fink's theorem, decomposition to Hamiltonian cycles, semiperfect 1-factorization.
*(scribe by David Pěgřímek, Markéta Calábková)* - Lecture 10: Gray codes, permutation framework, middle and central levels problem, SCDs, various binary Gray codes.
*(scribe by Václav Vlček, Sasha Sami)* - 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)* - Lecture 17: Symmetric chain decompositions.
*(scribe by Ondřej Mička)* - Lecture 18: Binary counters.
*(scribe by Martin Dvořák)* - Lecture 19: Unique sink orientations.
*(scribe by Viktor Němeček)* - Lecture 20: Sensitivity conjecture.
*(scribe by Václav Končický)* - Lecture 21: Coin weighing, metric dimension.
*(scribe by Tung Anh Vu)* - Lecture 22: Distance magic labelings.
*(scribe by Petr Chmel)*

**Note:** Videos of the lectures from the year 2020/21 are available in the playlist on Stream UK.

**Course Description**

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

**Prerequisites**

I assume only elementary knowledge. The course is suitable for all students in all Master of Computer Science study programs.

**Evaluation**

Average exercise grade will cover 60% of the final mark, and the other
40% will be given for exam.

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