An Optimization-based Primer on Flag Algebras


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.

May 23, 2019 10:00 AM — 10:45 AM
Schloss Dagsthul, Leibniz-Zentrun für Informatik
66687 Wadern, Merzig-Wadern, Saarland, Germany
Aritanan Gruber
Assistant Professor

“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!"
(desconheço a autoria; agradeço a indicação)