On the structure of oriented graphs and digraphs with forbidden tournaments or cycles

Daniela Kuhn, Deryk Osthus, Timothy Townsend, Yi Zhao

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)
166 Downloads (Pure)

Abstract

Motivated by his work on the classification of countable homogeneous oriented graphs, Cherlin asked about the typical structure of oriented graphs (i) without a transitive triangle, or (ii) without an oriented triangle. We give an answer to these questions (which is not quite the predicted one). Our approach is based on the recent ‘hypergraph containers’ method, developed independently by Saxton and Thomason as well as by Balogh, Morris and Samotij. Moreover, our results generalise to forbidden transitive tournaments and forbidden oriented cycles of any order, and also apply to digraphs. Along the way we prove several stability results for extremal digraph problems, which we believe are of independent interest.
Original languageEnglish
Pages (from-to)88-127
Number of pages40
JournalJournal of Combinatorial Theory. Series B
Volume124
Early online date9 Jan 2017
DOIs
Publication statusPublished - May 2017

Keywords

  • Typical structure
  • Digraphs
  • Oriented graphs
  • Counting graphs

Fingerprint

Dive into the research topics of 'On the structure of oriented graphs and digraphs with forbidden tournaments or cycles'. Together they form a unique fingerprint.

Cite this