On the local structure of oriented graphs -- a case study in flag algebras (Q2170792)

Summary: Let \(G\) be an \(n\)-vertex oriented graph. Let \(t(G)\) (respectively \(i(G))\) be the probability that a random set of \(3\) vertices of \(G\) spans a transitive triangle (respectively an independent set). We prove that \(t(G) + i(G) \geqslant \frac{1}{9}-o_n(1)\). Our proof uses the method of flag algebras that we supplement with several steps that make it more easily comprehensible. We also prove a stability result and an exact result. Namely, we describe an extremal construction, prove that it is essentially unique, and prove that if \(H\) is sufficiently far from that construction, then \(t(H) + i(H)\) is significantly larger than \(\frac{1}{9}\). We go to greater technical detail than is usually done in papers that rely on flag algebras. Our hope is that as a result this text can serve others as a useful introduction to this powerful and beautiful method.