Combinatorics and Graph Theory
Advanced counting and the structure of graphs: enumerative, existence and extremal problems with double counting, invariants such as the mutilated chessboard, the pigeonhole principle and the Erdős–Szekeres theorem, compositions and multisets, Stirling numbers of both kinds, Bell numbers and the twelvefold way, Catalan numbers with the reflection principle and the first-return decomposition, inclusion and exclusion with Bonferroni inequalities, derangements, surjections and the ménage problem, ordinary generating functions for making change, dice and linear recurrences, exponential generating functions and the exponential formula for set partitions, permutations, labeled graphs and Cayley's formula for trees, integer partitions with Ferrers diagrams, Euler's distinct-equals-odd theorem, the pentagonal number theorem and the Hardy–Ramanujan asymptotic, connectivity with Whitney's inequality, blocks and ear decompositions, Euler tours, de Bruijn sequences and the Chinese postman problem, Hamilton cycles with the theorems of Ore and Dirac and tournaments, planar graphs with Euler's formula, the Platonic solids, duality and Kuratowski's theorem, graph coloring with Brooks' theorem, Mycielski graphs, the five color theorem and the history of the four color theorem, chromatic polynomials by deletion and contraction, matchings with Berge's, Hall's and König's theorems and the Gale–Shapley stable matching algorithm, network flows with the max-flow min-cut theorem, the Edmonds–Karp algorithm and Menger's theorem, and a capstone on Ramsey numbers, Schur's theorem and the probabilistic method, with runnable Python examples throughout.
MATH-460 Year 4 3 credits 12 lessons · 4 h 42 min ▶ Video lessons coming soon
Offered by HSM University · Mathematics & Statistics
This is the American version of this course. See the Canadian version.
What you'll learn
- Distinguish enumerative, existence and extremal problems, and prove results by double counting, invariants, the pigeonhole principle and bijections, including the Erdős–Szekeres theorem.
- Count compositions, multisets, set partitions and permutations by cycles using Stirling, Bell and Catalan numbers, and prove their recurrences and the reflection principle.
- Apply the principle of inclusion and exclusion to derangements, surjections, divisibility and forbidden positions, and use Bonferroni inequalities as bounds.
- Use ordinary generating functions to count selections and compositions, solve linear recurrences by partial fractions, and derive the Catalan formula from a functional equation.
- Use exponential generating functions and the exponential formula to count labeled structures such as set partitions, permutations with restricted cycles, graphs and trees.
- Prove identities for integer partitions with generating functions and Ferrers diagrams, including Euler’s pentagonal number theorem, and estimate the growth of counting sequences.
- Analyze connectivity with Whitney’s inequality and blocks, decide when Euler tours exist, construct de Bruijn sequences, and apply Ore’s and Dirac’s conditions for Hamilton cycles.
- Apply Euler’s formula to planar graphs, prove that \(K_5\) and \(K_{3,3}\) are not planar, classify the Platonic solids, and state Kuratowski’s theorem.
- Bound chromatic numbers using cliques, greedy coloring and Brooks’ theorem, prove the five color theorem, and compute chromatic polynomials by deletion and contraction.
- Find maximum matchings with augmenting paths, prove and apply Hall’s and König’s theorems, and compute stable matchings with the Gale–Shapley algorithm.
- Compute maximum flows and minimum cuts with augmenting paths, prove the max-flow min-cut theorem, and derive Menger’s theorem and König’s theorem from it.
- Prove bounds on Ramsey numbers, apply Ramsey-type theorems such as Schur’s, and use the probabilistic method and linearity of expectation to prove that combinatorial objects exist.
Course content
12 lessons · 4 h 42 min total · final exam
- 1 Why combinatorics: counting, structure and existence 22 min · quiz
- 2 Bijections, multisets, Stirling and Catalan numbers 24 min · quiz
- 3 Inclusion–exclusion and derangements 22 min · quiz
- 4 Ordinary generating functions 21 min · quiz
- 5 Exponential generating functions and set partitions 22 min · quiz
- 6 Integer partitions, recurrences and asymptotics 20 min · quiz
- 7 Graphs: connectivity, Euler tours and Hamilton cycles 25 min · quiz
- 8 Planar graphs and Euler’s formula 23 min · quiz
- 9 Graph coloring and chromatic polynomials 26 min · quiz
- 10 Matchings: Hall’s theorem, König’s theorem and stable marriage 26 min · quiz
- 11 Network flows: max-flow min-cut and Menger’s theorem 26 min · quiz
- 12 Capstone: Ramsey theory and the probabilistic method 25 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
Advanced counting and the structure of graphs: enumerative, existence and extremal problems with double counting, invariants such as the mutilated chessboard, the pigeonhole principle and the Erdős–Szekeres theorem, compositions and multisets, Stirling numbers of both kinds, Bell numbers and the twelvefold way, Catalan numbers with the reflection principle and the first-return decomposition, inclusion and exclusion with Bonferroni inequalities, derangements, surjections and the ménage problem, ordinary generating functions for making change, dice and linear recurrences, exponential generating functions and the exponential formula for set partitions, permutations, labeled graphs and Cayley's formula for trees, integer partitions with Ferrers diagrams, Euler's distinct-equals-odd theorem, the pentagonal number theorem and the Hardy–Ramanujan asymptotic, connectivity with Whitney's inequality, blocks and ear decompositions, Euler tours, de Bruijn sequences and the Chinese postman problem, Hamilton cycles with the theorems of Ore and Dirac and tournaments, planar graphs with Euler's formula, the Platonic solids, duality and Kuratowski's theorem, graph coloring with Brooks' theorem, Mycielski graphs, the five color theorem and the history of the four color theorem, chromatic polynomials by deletion and contraction, matchings with Berge's, Hall's and König's theorems and the Gale–Shapley stable matching algorithm, network flows with the max-flow min-cut theorem, the Edmonds–Karp algorithm and Menger's theorem, and a capstone on Ramsey numbers, Schur's theorem and the probabilistic method, with runnable Python examples throughout.
Part of the Science stream, typically taken in year 4.