Combinatorics

Module aims

Prove extremal bounds and bijections with named theorems, keeping constructions and obstructions in view.

Course outline

1. 01 Counting and double counting 20h

   Learning result Prove an identity by counting a set in two ways.

   Formative check Written derivation

2. 02 Graphs and extremal problems 25h

   Learning result For n≥r≥2, state Turán’s bound for a finite simple n-vertex K_{r+1}-free graph and exhibit the balanced complete r-partite equality graph T_r(n).

   Formative check Written derivation

3. 03 Set systems 25h

   Learning result Apply an intersecting-family or Sperner-type bound with hypotheses named.

   Formative check Written derivation

4. 04 Ramsey language 20h

   Learning result Prove a small Ramsey number upper or lower bound by a counting or probabilistic argument.

   Formative check Written derivation

5. 05 Generating functions (taught use) 20h

   Learning result Extract a coefficient or recurrence from a generating function that the syllabus licenses.

   Formative check Four-option check

6. 06 Tight examples 20h

   Learning result Give a construction showing a bound is best possible, or a counterexample to a naive strengthening.

   Formative check Counterexample

7. 07 Synthesis 20h

   Learning result Combine an extremal bound with a matching construction.

   Formative check Written derivation

Learning results

Prove or apply a named extremal or enumerative result and give a tight example.

Subject skills

Extremal graph theory at taught grain, double counting, generating functions as used in the synopsis topics, set systems.

Transferable skills

Match a construction to a bound; say when a theorem is sharp.