Skip to main content

Preface Preface

“It is not enough to be in the right place at the right time. You should also have an open mind at the right time.” Paul Erdős, lamenting the fact that he did not invent extremal graph theory (see [267]).}
described in detail following the image
“My brain is open,” Paul Erdős.
The topic of these notes is extremal combinatorics, which is one of the most classical branches of combinatorial theory. Extremal combinatorics itself can be further divided into many distinct areas which can be traced back to the first half of the twentieth century, if not earlier. For instance,
  • extremal set theory goes back at least as far as Sperner’s Theorem from 1928 [271],
  • extremal graph theory began with Mantel’s Theorem from 1907 [213] and was first investigated in depth by Turán in 1941 [287],
  • Ramsey Theory was popularised in a 1947 paper of Erdős [92] which was inspired by a 1929 result of Ramsey [237] on a problem in formal logic and
  • some of the central extremal problems in arithmetic combinatorics can be traced back to the work of Schur in 1916 [256] and van der Waerden in 1927 [292].
While we will aim to cover many of the “greatest hits” of extremal combinatorics from the past, one should not get the impression that these notes constitute a review of ancient history. On the contrary, extremal combinatorics is one of the most vibrant branches of modern combinatorial theory and many of the most exciting recent advances in extremal combinatorics harken back to the classical questions and theorems at its origin.
In designing these notes, I have aimed to emphasize those topics which are most beautiful and are most relevant to contemporary (at the time that these notes were written) research in extremal combinatorics. Fortunately, in this area of mathematics, these two aims are almost completely aligned, and so very few compromises have had to be made. Of course, the notions of “beauty” and “relevance” are subjective. It is inevitable that the focus of these notes is biased towards my own interests, experience and taste.
The notes are divided into chapters, each of which brings together several topics of the same ilk. Each topic roughly fills one section. At the end of each chapter, there are two sections consisting of Exercises and Challenge Problems:
  • Exercises are designed to check your understanding of the topics covered in the chapter. They mainly consist of problems which test your comprehension of the key definitions, theorems and methods and your ability to apply them. These range from easy deductions to harder problems which require a few additional insights (of limited depth).
  • Challenge Problems are related to topics in these notes but solving them requires a greater level of ingenuity than Exercises. Solving some of these problems may require ideas that are beyond the scope of these notes (without warning). These problems are targeted at students who particularly enjoy thinking deeply about difficult problems or wish to “test their mettle.”
Near the end of these notes, there is an appendix on asymptotic (Big O) notation. It would be wise to familiarize yourself with this notation early on, as it will be used throughout the notes and you are likely to encounter it again in your mathematical studies. We will occasionally apply probabilistic arguments in these notes. In most cases, these arguments will be of the most basic type, requiring nothing deeper than linearity of expectation and the “First Moment Method.” I have also included an appendix on some of the basic facts from probability theory that we will use. There is also an appendix on some standard convexity inequalities which are applied in the notes. All three of these appendices are only included for the purposes of making these notes more-or-less self-contained.
I hope that you enjoy reading these notes as much as I have enjoyed writing them.