Geodesic
On the local structure of oriented graphs -- a case study in flag algebras
The electronic journal of combinatorics, Tome 29 (2022) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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)$. 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 $\frac{1}{9}$. 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.
DOI : 10.37236/10694
Classification : 05C35, 05C20, 05C30, 05C69, 05D10, 90C22
Mots-clés : flag algebras, Ramsey-type result, Goodman's theorem 
@article{10_37236_10694,
     author = {Shoni  Gilboa and Roman Glebov and Dan Hefetz and Nati  Linial and Avraham Morgenstern},
     title = {On the local structure of oriented graphs -- a case study in flag algebras},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {3},
     doi = {10.37236/10694},
     zbl = {1496.05086},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10694/}
}
TY  - JOUR
AU  - Shoni  Gilboa
AU  - Roman Glebov
AU  - Dan Hefetz
AU  - Nati  Linial
AU  - Avraham Morgenstern
TI  - On the local structure of oriented graphs -- a case study in flag algebras
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10694/
DO  - 10.37236/10694
ID  - 10_37236_10694
ER  - 
%0 Journal Article
%A Shoni  Gilboa
%A Roman Glebov
%A Dan Hefetz
%A Nati  Linial
%A Avraham Morgenstern
%T On the local structure of oriented graphs -- a case study in flag algebras
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10694/
%R 10.37236/10694
%F 10_37236_10694
Shoni  Gilboa; Roman Glebov; Dan Hefetz; Nati  Linial; Avraham Morgenstern. On the local structure of oriented graphs -- a case study in flag algebras. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10694

Cité par Sources :