Hypercube problems

Meeting: Wednesday 14:00-15:30, room S301 (corridor of KTIML). The first lecture will be on Oct 10.
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)
• Lecture 17: Symmetric chain decompositions. (scribe by Ondřej Mička)
• Lecture 18: Binary counters. (scribe by Martin Dvořá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.