Counting flags in triangle-free digraphs

Abstract

Motivated by the Caccetta-Haggkvist Conjecture, we prove that every digraph on n vertices with minimum outdegree 0.3465n contains an oriented triangle. This improves the bound of 0.3532n of Hamburger, Haxell and Kostochka. The main new tool we use in our proof is the theory of flag algebras developed recently by Razborov.

19 pages, 7 figures; this is the final version to appear in Combinatorica

References in corpus (2)

• On the Number of Pentagons in Triangle-Free Graphs
• Non-three-colorable common graphs exist

Cited by in corpus (10)

• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Rainbow triangles in three-colored graphs
• Inducibility of directed paths
• Solving Turán's Tetrahedron Problem for the ${\ell }_2$-Norm
• Infinite dimensional finitely forcible graphon
• Decomposing graphs into edges and triangles
• Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
• The dimension of the feasible region of pattern densities
• Short rainbow cycles in graphs and matroids