CSCI 7000: Topics in Combinatorics with Applications to Computer Science (Grad, Fall 2023) (a.k.a. Asymptotic Combinatorics a.k.a. Advanced Counting)
Syllabus
Student hours for this class: Thursdays 12:30-1:30 US Mountain Time, at my zoom linkBooks
There is no textbook for this class, we will read selections from some subset of the books below, lecture notes, and research articles. However, regardless of what we cover in class, these books are great resources! All the books below are either freely available, or available through CU libraries; in the latter case, the link below is to the CU Library Proxy that will log you in (if you don't want that look at the URL - it should be fairly clear how to modify it to not do that, or ask me for help).
- Wilf. Generatingfunctionology
- Flajolet and Sedgewick. Analytic combinatorics
- Loehr. Combinatorics.
- Jukna. Extremal Combinatorics with applications in Computer Science.
- van Lint and Wilson. A course in combinatorics.
- Stanley. Enumerative Combinatorics, Volume I
- Harary & Palmer. Graphical enumeration.
- Beck & Sanyals. Combinatorial Reciprocity Theorems: An Invitation to Enuemrative Geometric Combinatorics.
Problem Sets
- Problem Set 1: Fibonacci
- Problem Set 2: Generating Functions
- Problem Set 3: Exponential Generating Functions
- Problem Set 4: Permutations by exponential generating functions
Problem Set 5: Inclusion-exclusionUpdated 10/17- Problem Set 6: Counting with complexity
- Problem Set 7: Counting under symmetry
Final project topics
(Project topics posted w/ permission of their authors, in alphabetical order by last name)- Robin Bowers: Connections Between Regular Languages and Rational Series
- Melody Hsu: Combinatorial Bingo!
- Gülce Kardeş: A constant lower bound on the union closed sets conjecture
- Guangkuo Liu: Recursive graph formula for quantum entanglement
- Mert Okyay: Counting states by colored graphs
- Chethan Kavaraganahalli Prasanna: Generating functions in the wild - Random graphs
- Elise Tate: Counting Lattice Points in a Fixed Dimensional Polytope
- Lyryl Varekamp: Graph theory in quantum systems