An Optimization-based Primer on Flag Algebras

Abstract

Despite all the progress made in the past two decades, a unifying theory of enumeration algorithms seems, by any reasonable metric, a distant milestone – if achievable at all. In the mean time, we search for tools and inspiration in the slightly more developed settings of counting and density estimation. The theory of flag algebras offers a systematic approach to derive computer-assisted proofs of density estimation results in asymptotic extremal combinatorics. We start with a brief survey of the theory from an optimization standpoint. We then focus on a conic programming strong duality relation lying at its core, while providing simpler proofs along the way. At the end, we mention possible extensions and ramifications of our approach.