Combinatorics

模块目标

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

课程大纲

1. 01 Counting and double counting 20h

   学习结果 Prove an identity by counting a set in two ways.

   形成性检查 书面推导

2. 02 Graphs and extremal problems 25h

   学习结果 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).

   形成性检查 书面推导

3. 03 Set systems 25h

   学习结果 Apply an intersecting-family or Sperner-type bound with hypotheses named.

   形成性检查 书面推导

4. 04 Ramsey language 20h

   学习结果 Prove a small Ramsey number upper or lower bound by a counting or probabilistic argument.

   形成性检查 书面推导

5. 05 Generating functions (taught use) 20h

   学习结果 Extract a coefficient or recurrence from a generating function that the syllabus licenses.

   形成性检查 四选一检查

6. 06 Tight examples 20h

   学习结果 Give a construction showing a bound is best possible, or a counterexample to a naive strengthening.

   形成性检查 反例

7. 07 Synthesis 20h

   学习结果 Combine an extremal bound with a matching construction.

   形成性检查 书面推导

学习结果

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

学科技能

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

可迁移技能

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