Lecture: Combinatorial generation—graphs, structures and algorithms

Schedule: Oct 11 2023-Jan 10 2024, weekly on Wednesday, 16:00-17:30 CET
Location: Charles University Prague, Department of Theoretical Computer Science and Mathematical Logic, Room S301
Remote participation: via Zoom

Topics of lectures

• Oct 11: Introduction (counting/sampling/optimization/generation, Gray codes and flip graphs)
• Oct 18: General Gray code results (necessary conditions, stronger Hamiltonicity notions, Sekanina's and Fleischner's theorem, Lovász' conjecture, Cayley graphs, Tchuente's theorem)
• Oct 25: Book proof of the middle levels theorem
• Nov 01: No lecture
• Nov 08: The binary reflected Gray code (inductive and greedy definition, basic properties)
• Nov 15: The binary reflected Gray code (algorithms, Venn diagrams, combinations, Savage-Winkler construction of weight-monotonic Gray codes)
• Nov 22: Guest lecture by Arturo Merino (Gray codes for spanning trees of a graph)
• Nov 29: Permutations (lexicographic, Steinhaus-Johnson-Trotter, star transpositions)
• Dec 06: Guest lecture by Aaron Williams (Shift Gray codes: cool-lex order for combinations, bubble languages, shorthand universal cycles)
• Dec 13: Permutations (zigzag languages and Algorithm J, applications to bitstrings and binary trees)
• Dec 20: Permutations (zigzag languages: set partitions, tame patterns; topological orderings)