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

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) is asymptotically at least 1/9. 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 1/9. The proof of the asymptotic result uses the method of flag algebras. I will try to use this result to explain (in some detail) how this method works.

Based on joint work with Shoni Gilboa, Roman Glebov, Nati Linial and Avraham Morgenstern.