Nicholas Crawford: Flag Algebra and Applications

Flag Algebra and Applications

Nicholas Crawford

Abstract: In 2007 Razborov introduced the concept of flag algebras. Since then, it has garnered much attention from the extremal combinatorics community as a tool to prove upper bounds on various types of Turán, Ramsey, and structural type problems. In this talk, we will explore the basics of flag algebra, using Mantel's Theorem as a motivating example, to develop the basic identities and concepts needed to prove upper bounds using the plain flag algebra method. We then apply flag algebras to a variation of Turán's problem originally posed by Erdős. Specifically, Erdős asks what the minimum threshold is ensuring that every $k$-partite graph with sufficiently high pairwise edge density contains a given subgraph. Extending this, we address the more general question: given graphs $F$ and $H$, can we construct a subgraph $G$ of the $n$-blow-up of $H$ that avoids $F$ while maximizing the minimum pairwise edge density? We resolve the cases where $F=H=C_k$ and $F=H=K_{2,3}$.