Affordable Access

Publisher Website

Counting flags in triangle-free digraphs

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
34
Identifiers
DOI: 10.1016/j.endm.2009.07.105
Keywords
  • Caccetta-Häggkvist Conjecture
  • Triangles In Digraphs
  • Flag Algebras
Disciplines
  • Mathematics

Abstract

Abstract We prove that every digraph on n vertices with minimum out-degree 0.3465 n contains an oriented triangle. This improves the bound of 0.3532 n of Hamburger, Haxell and Kostochka. The main tool for our proof is the theory of flag algebras developed recently by Razborov.

There are no comments yet on this publication. Be the first to share your thoughts.