






















For integers \(r\ge 2\), \(t\ge 1\) and a real number \(a\in(3/2,2]\), we study the typical structure of oriented graphs and digraphs that do not contain a blow-up \(T_{r+1}^t\) of a transitive tournament. We prove that almost every \(T_{r+1}^t\)-free oriented graph on n vertices admits an r-partition \(V_1\cup\cdots\cup V_r\) such that each induced subgraph \(G[V_i]\) is \(T_2^t\)-free, and the same holds for almost every \(T_{r+1}^t\)-free digraph.Consequently, the number \(f(n,T_{r+1}^t)\) of labelled \(T_{r+1}^t\)-free oriented graphs satisfies \(f(n,T_{r+1}^t)=|\mathcal{P}_{n,r,t}|(1+o(1))\), where \(\mathcal{P}_{n,r,t}\) is the family of oriented graphs admitting such an r-partition with each part \(T_2^t\)-free; an analogous statement holds for digraphs.When \(t=1\) this recovers the result of K"uhn, Osthus, Townsend and Zhao (2017) that almost all \(T_{r+1}\)-free oriented graphs (resp. digraphs) are r-partite, thereby confirming a generalised form of Cherlin's conjecture. Our proof combines the hypergraph container method, a weighted Erdős-Stone theorem, and a stability analysis for near-extremal \(T_{r+1}^t\)-free digraphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。