# Lecture: Combinatorial generation - graphs, structures and algorithms

Schedule: Oct 06 2022-Jan 05 2023, weekly on Thursday, 12:20-13:50 CETLocation: Charles University Prague, Department of Theoretical Computer Science and Mathematical Logic, Room S301

Remote participation: Zoom link

## Topics of lectures

- Oct 06: Introduction (counting/sampling/generation, flip graphs)
- Oct 13: Binary reflected Gray code (construction, properties)
- Oct 20: BRGC algorithms and Venn diagrams
- Oct 27: Weight-monotonicity (Savage-Winkler), combinations (transpositions, homogeneous)
- Nov 03: Weight ranges, middle levels theorem (book proof)
- Nov 10: Permutations (lexicographic, Steinhaus-Johnson-Trotter)
- Nov 17: —no lecture (public holiday)—
- Nov 24: Guest lecture by Arturo Merino (Gray codes for spanning trees of a graph)
- Dec 01: Guest lecture by Aaron Williams (Shift Gray codes: cool-lex order for combinations, bubble languages, shorthand universal cycles)
- Dec 08: Permutations (star transpositions, zigzag languages)
- Dec 15:

## Exercise 1

Solve 3 of the 5 problems below.- Show that solving the Towers of Hanoi problem on three pegs with $n$ disks requires at least $2^n-1$ moves.
- Prove that the hypercube $Q_n$ is Hamilton-laceable, i.e., it admits a Hamilton path between every pair of vertices of opposite parity.
- An $n$-Venn diagram is called symmetric if there is a point in the plane such that rotating the diagram by $2\pi/n$ around that point leaves it invariant. In other words, each curve is obtained by rotation from any of the other curves. Show that if there is a symmetric $n$-Venn diagram, then $n$ must be prime. Hint: Consider the size of orbits of the hypercube automorphism that cyclically shifts bits when $n$ is not prime.
- Consider the flip graph of $(n,k)$-combinations, i.e., bitstrings of length $n$ with weight $k$, under adjacent transpositions, i.e., transpositions of a 0 and 1 that are at adjacent positions. Does this flip graph admit a Hamilton cycle?
- Show that every Hamilton cycle in the subgraph of the hypercube $Q_{2n+1}$ induced by the levels $n$ and $n+1$ is balanced, i.e., every bit position is flipped the same number of times. Hint: Consider the subgraphs obtained by fixing one bit, and the edges between them.