Designs, Extremal Problems, and Discrete Mathematics

When students study optimization in mathematics courses, they often learn about calculus-based approaches for continuous optimization. However, many problems of practical societal interest (such as optimal scheduling of flights) can be framed as discrete optimization problems. This course focuses on designs, networks, configurations, and discrete structures that are optimal or extremal in ways that we shall make precise. We introduce relevant notions from combinatorics and graph theory, branches of mathematics that students may find less familiar than algebra and geometry. Although most of the problems that we study are understandable to high school students, we see why many extremal problems are incredibly challenging—for each problem that we study, students learn where the current frontier of knowledge lies with examples of unsolved problems. 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, and finite projective planes).