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

Seminar
Speaker
Dan Hefetz (Ariel University)
Date
08/12/2019 - 15:30 - 14:00Add to Calendar 2019-12-08 14:00:00 2019-12-08 15:30:00 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. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
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) 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.

Last Updated Date : 04/12/2019