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

DOI10.37236/10694zbMATH Open1496.05086arXiv1908.06480OpenAlexW4288261357MaRDI QIDQ2170792FDOQ2170792

Authors: Shoni Gilboa, Roman Glebov, Dan Hefetz, Nathan Linial, Avraham Morgenstern 

Publication date: 6 September 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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)geqfrac19-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 $frac19$. 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.

Full work available at URL: https://arxiv.org/abs/1908.06480

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Flag algebras
• On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
• On the 3-local profiles of graphs

zbMATH Keywords

flag algebrasRamsey-type resultGoodman's theorem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Semidefinite programming (90C22) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Ramsey theory (05D10)

Cites Work

• Flag algebras
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• The Voting Problem
• Title not available (Why is that?)
• On Sets of Acquaintances and Strangers at any Party
• Graph removal lemmas
• On the 3-local profiles of graphs
• The Algorithmic Aspects of the Regularity Lemma
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• A problem of Erdős on the minimum number of \(k\)-cliques

Cited In (2)

• On the 3-local profiles of graphs
• On the structure of oriented graphs and digraphs with forbidden tournaments or cycles

This page was built for publication: On the local structure of oriented graphs -- a case study in flag algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170792)