Applications of flag algebras in extremal graph theory

Abstract

We present an introduction to the theory of flag algebras, a framework under which computer-assisted proofs in asymptotic extremal combinatorics may be derived. We develop the theory of flag algebras for simple graphs and demonstrate how classical problems in extremal graph theory can be proved using flag algebras. We demonstrate the semidefinite method, an algorithm which allows us to derive proofs in extremal graph theory in an almost mechanical manner. Specifically, we will focus on using the semidefinite method to bound Turan densities. In addition, we discuss the limitations of this approach and heuristics which improve its performance. We then consider the use of flag algebras in tackling several difficult problems in graph theory. Namely, we present a proof of the Erd¨os pentagon problem, which asks for the maximum density of pentagons in a triangle-free graph; we give a exposition on how flag algebras have been used to bound Ramsey numbers; we describe the methodology used to prove a case of a conjecture on permutations due to Myers [Mye02]. We also derive Tur´an densities for 4- and 5-uniform hypergraphs, many of which are novel to this thesis.