Wigderson Group

Extremal Combinatorics and Ramsey Theory

Extremal combinatorics studies the size and structure of discrete objects subject to natural constraints. The kinds of discrete objects one studies can include sets of integers, collections of points and lines in a plane, linear spaces of matrices, and graphs, i.e., collections of vertices, some pairs of which are joined by an edge. While a graph on n vertices can have up to (n²-n)/2 edges, the maximum possible number of edges drops significantly if we impose some constraints on the graph; for example, if we ask that the graph has no cycle, the maximum possible number of edges drops to n-1. We could also ask more refined questions: instead of excluding all cycles, we can exclude only cycles of a given length, and again ask for the maximum possible number of edges. For excluding cycles of length 3, the answer has been known for over 100 years. For length 4, the answer has been known for over 80 years. For lengths 5, 6, and 7, the answer has been known for over 50 years. But for length 8, we still have no idea what the answer is!

While many fundamental problems in extremal combinatorics remain open, the field has seen considerable progress in the past few decades. Many of the most exciting developments have utilized ideas from a wide array of other fields. These include algebra, ergodic theory, functional analysis, number theory, probability, theoretical computer science, and topology. This has led to a rich interplay between these fields and extremal combinatorics. By incorporating ideas from various areas, the Wigderson group seeks to answer fundamental questions about the structure of discrete objects as well as order and chaos within large systems.