Syllabus
- Flip graphs
- Binary strings (binary reflected Gray code)
- Binary strings (monotone and balanced Gray codes)
- Combinations (transpositions and shifts)
- Catalan objects (parenthesis expressions)
- Middle levels theorem
- Permutations (transpositions, shifts and reversal)
- Permutations (linear extensions)
- Permutations (pattern-avoiding permutations)
- Geometric objects (triangulations, non-crossing matchings)
- De Bruijn sequences
- Spanning trees and bases of matroids
Annotation
In computer science and mathematics we frequently encounter different kinds of combinatorial objects, such as bitstrings, permutations, partitions, binary trees, triangulations, spanning trees, perfect matchings etc. A recurring problem of interest is to exhaustively generate all the objects from a class, each object exactly once.
We discuss algorithms for that task, and we will introduce the techniques for developing and analyzing them. We touch upon related questions, such as combinatorial counting and random sampling, including methods from graph theory, order theory, geometry and algebra.