Syllabus
- 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.
Annotation
Many objects in various areas of theoretical computer science may be formulated as problems in hypercubes. The lecture offers an overview of selected problems studied in hypercubes with emphasis on applications in theoretical computer science.
It assumes only elementary knowledge and it is suitable for students in the M.Sc. programme.