Lecture: Combinatorial generation—graphs, structures and algorithms

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

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 framework)
• Dec 15: Permutations (zigzag framework: bitstrings, binary trees+triangulations)
• Jan 05: Permutations (zigzag framework: set partitions, tame patterns; topological orderings)

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.

Exercise 2

Solve 3 of the 5 problems below.

• Prove that the Cayley graph of the symmetric group with any set of transpositions as generators is bipartite, with partition classes of the same size.
• Devise an efficient algorithm to generate equivalence classes of permutations under cyclic shifts and reversals, called rosary permutations. Specifically, the algorithm should list $(n-1)!/2$ permutations of $\{1,\ldots,n\}$ such that if $a_1\cdots a_n$ is listed, then no cyclic shift of it or of the reversed string should be listed.
• Consider the following simple greedy algorithm for permutation generation: Repeatedly reverse the shortest possible prefix that creates a new permutation. Prove that this algorithm succeeds to list all $n!$ permutations of $\{1,\ldots,n\}$.
• Consider the flip graph of linear extensions of the $2\times k$ grid poset under transpositions. How many vertices does the flip graph have, i.e., what is the number of linear extensions of the grid poset? Under what conditions is the flip graph balanced, i.e., both of its partition classes have the same size?
• A Dyck path of length $2n$ is a path in the integer lattice that starts at the origin $(0,0)$, ends at $(2n,0)$, and consists of upsteps $(+1,+1)$ and downsteps $(+1,-1)$, with the property that the path never moves below the abscissa. Describe a bijection between Dyck paths of length $2n$ and binary trees with $n$ nodes. Using your bijection, translate the greedy algorithm for listing all binary trees known from the lecture to a greedy algorithm for listing all Dyck words.