Typical Structure of Oriented Graphs and Digraphs with Forbidden Blow-Up Transitive Triangles

Abstract

Transitive tournament (including transitive triangle) and its blow-up have some symmetric properties. In this work, we establish an analogue result of the Erdös-Stone theorem of weighted digraphs with a forbidden blow-up of the transitive tournament. We give a stability result of oriented graphs and digraphs with forbidden blow-up transitive triangles and show that almost all oriented graphs and digraphs with forbidden blow-up transitive triangles are almost bipartite, which reconfirms and strengthens the conjecture of Cherlin.

Keywords

• forbidden digraph
• Erdös-Stone theorem
• transitive triangle
• blow-up