×

On the local structure of oriented graphs – a case study in flag algebras. (English) Zbl 1496.05086

Summary: 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) \geqslant \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.

MSC:

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

References:

[1] N. Alon, R. A. Duke, H. Lefmann, V. R¨odl, and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), 80-109. · Zbl 0794.05119
[2] B. Andr´asfai, P. Erd˝os, and V. S´os, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205-218. · Zbl 0284.05106
[3] D. Conlon and J. Fox, Graph removal lemmas, Surveys in Combinatorics, Cambridge University Press, 2013, 1-50. · Zbl 1301.05309
[4] CSDP, A C Library for Semidefinite Programming,https://projects.coin-or. org/Csdp.
[5] S. Das, H. Huang, J. Ma, H. Naves, and B. Sudakov, A problem of Erd˝os on the minimum number of k-cliques, J. Combinatorial Theory Ser. B 103 (2013), 344-373. · Zbl 1301.05185
[6] P. Erd˝os and L. Moser, On the representation of directed graphs as unions of orderings, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964), 125-132. · Zbl 0136.44901
[7] V. Falgas-Ravry and E. R. Vaughan, On applications of Razborov’s flag algebra calculus to extremal 3-graph theory.arXiv:1110.1623(2011).
[8] A. W. Goodman, On sets of acquaintances and strangers at any party, Am. Math Mon 66 (1959), 778-783. · Zbl 0092.01305
[9] H. Huang, N. Linial, H. Naves, Y. Peled, and B. Sudakov, On the 3-local profiles of graphs, Journal of Graph Theory 76 (2014), 236-248. · Zbl 1305.05120
[10] O. Pikhurko and E. R. Vaughan, Minimum Number ofk-Cliques in Graphs with Bounded Independence Number, Combinatorics Probability and Computing 22 (2013), 910-934. · Zbl 1282.05183
[11] A. Razborov, Flag algebras, Journal of Symbolic Logic 72(4) (2007), 1239-1282. · Zbl 1146.03013
[12] R. Stearns, The voting problem, Amer. Math. Monthly 66 (1959), 761-763. · Zbl 0090.25101
[13] E. R. Vaughan, Flagmatic software, A tool for researchers in extremal graph theory. http://jakubsliacan
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.