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.
תאריך עדכון אחרון : 04/12/2019