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

DOI10.37236/10694MaRDI QIDQ2170792zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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.

Recommendations

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

Cites work

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

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)