The Library
Counting flags in triangle-free digraphs
Tools
Hladký, Jan, Králʼ, Daniel and Norine, Serguei (2016) Counting flags in triangle-free digraphs. Combinatorica, 37 (1). pp. 49-76. doi:10.1007/s00493-015-2662-5 ISSN 0209-9683.
|
PDF
WRAP-counting-flags-triangle-free-digraph-Kral-2017.pdf - Accepted Version - Requires a PDF viewer. Download (640Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00493-015-2662-5
Abstract
Motivated by the Caccetta-Häggkvist 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||
Library of Congress Subject Headings (LCSH): | Directed graphs, Graph theory | ||||
Journal or Publication Title: | Combinatorica | ||||
Publisher: | Springer | ||||
ISSN: | 0209-9683 | ||||
Official Date: | 17 June 2016 | ||||
Dates: |
|
||||
Volume: | 37 | ||||
Number: | 1 | ||||
Page Range: | pp. 49-76 | ||||
DOI: | 10.1007/s00493-015-2662-5 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 4 March 2016 | ||||
Date of first compliant Open Access: | 12 June 2017 | ||||
Funder: | Univerzita Karlova, National Science Foundation (U.S.) (NSF), Natural Sciences and Engineering Research Council of Canada (NSERC) | ||||
Grant number: | GAUK 202-10/25800, DMS-070103 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year