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

DOI10.1016/J.JCTB.2016.12.008zbMath1398.05095arXiv1404.6178OpenAlexW2963417541MaRDI QIDQ1989954

Yanyan Li

Publication date: 29 October 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1404.6178

zbMATH Keywords

digraphsoriented graphstypical structurecounting graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Almost all triangle-free triple systems are tripartite
• Hypergraph containers
• The fine structure of octahedron-free graphs
• Supersaturated graphs and hypergraphs
• Cycles in dense digraphs
• Hereditary properties of tournaments
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The number of graphs without forbidden subgraphs
• On pancyclic digraphs
• For which densities are random triangle-free graphs almost surely bipartite?
• The number of oriantations having no fixed tournament
• Acyclic orientations of graphs
• The typical structure of graphs without given excluded subgraphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments
• Independent sets in hypergraphs
• Simple Containers for Simple Hypergraphs
• The number of K _s,t -free graphs
• Hereditary properties of combinatorial structures: Posets and oriented graphs
• Testing subgraphs in directed graphs

Related Items (4)

Integer colorings with no rainbow 3-term arithmetic progression ⋮ Counting orientations of graphs with no strongly connected tournaments ⋮ Structure and enumeration theorems for hereditary properties in finite relational languages ⋮ DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS

This page was built for publication: On the structure of oriented graphs and digraphs with forbidden tournaments or cycles