Combinatorics Seminar

When: Sunday, October 27, 10am
Where: Schreiber 309
Speaker: Dan Hefetz, Ariel Aviv University
Title: On the local structure of oriented graphs - a case study in flag algebras

Abstract:

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) \geq \frac{1}{9} - o_n(1)$. 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}$. 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.