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.



All Courses


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 15 Jul 2024