Hypercube structures
Winter term 2021/22
Meeting: Thursdays 10:40, at my office + on Zoom. The first lecture will be in the week 4.-8. 10.
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 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.