Course description

How large must a gathering of people be in order to ensure that either six of the people mutually know one another or that six of the people are mutual strangers? How many rooks (or knights or bishops) can be placed on a standard chessboard such that no two of them are attacking one another? Are there optimal fair experimental designs by which we may mutually compare thirteen competing brands of fabric softener without having to directly compare all seventy-eight possible pairs of brands? These problems are examples of extremal problems in combinatorics and graph theory a sub-discipline of mathematics that involves a very different way of thinking relative to areas such as algebra geometry and calculus. In this course we explore some classical extremal (and fun) problems including the ones mentioned above. The methods we develop are applicable to a variety of important practical problems such as optimal scheduling of flights. Topics are drawn from the following areas Ramsey theory (classical Ramsey numbers van der Waerden numbers and the happy end problem) two-player positional games (tic-tac-toe and the Hales-Jewett theorem generalized maker-breaker games) and optimal combinatorial designs (balanced incomplete block designs Steiner triple systems difference sets finite projective planes).

Instructor

Associated Schools

  • Harvard Division of Continuing Education

Enroll now.
Take course