This course will explain ideas for solving the problem of determining or estimating the maximum or minimum possible cardinality of a collection of finite objects that satisfies certain requirements. For example, how many edges can a graph on n vertices have if it does not contain a triangle?

Topics: Double counting, pigeonhole principle, Erdos-Szekeres theorem,
Mantel’s theorem, Turan’s theorem, Dirichlet’s theorem. Ramsey theorem
for graphs: bounds on Ramsey numbers. Extremal set theory: intersecting
families, Erdos-Ko-Rado theorem, maximal intersecting families, Furedi’s
theorem. Chains and antichains: Dilworth’s theorem, Sperner’s theorem,
Bollobas’ theorem.
Algebraic Methods: Even-odd town problem, Fisher’s inequality,
2-distance sets in `$\mathbb{R}^n$`

, bounds on the number of sets with
restricted pairwise intersections. Probabilistic methods: lower bounds
for Ramsey numbers, tournaments, dominating sets, sum-free sets of
integers.

Last updated: 15 Jul 2024