MA 376: Extremal Combinatorics
Credits: 3:0
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.