The typical structure of oriented graphs and digraphs with forbidden blow-up of transitive tournaments

Jianxi Liu; Meili Liang; Ruiling Zheng; Yue Guan

arxiv: 2605.18458 · v2 · pith:XL7Q7DYBnew · submitted 2026-05-18 · 🧮 math.CO · math.OC

The typical structure of oriented graphs and digraphs with forbidden blow-up of transitive tournaments

Meili Liang , Yue Guan , Ruiling Zheng , Jianxi Liu This is my paper

Pith reviewed 2026-05-20 09:12 UTC · model grok-4.3

classification 🧮 math.CO math.OC

keywords oriented graphsdigraphstransitive tournamentsblow-upsforbidden subgraphsstabilityhypergraph containersextremal counts

0 comments

The pith

Almost every T_{r+1}^t-free oriented graph on n vertices admits an r-partition into T_2^t-free induced subgraphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for r at least 2, t at least 1 and a parameter a in (3/2,2], almost every oriented graph avoiding a blow-up of the transitive tournament T_{r+1}^t can be split into r vertex parts where each induced subgraph avoids the smaller blow-up T_2^t. The identical partition property holds for digraphs. This determines the asymptotic count of all such graphs, equaling the count of graphs with the partition property up to a (1+o(1)) factor, and recovers the known multipartite structure when t equals 1.

Core claim

We prove that almost every T_{r+1}^t-free oriented graph on n vertices admits an r-partition V_1 ∪ ⋯ ∪ 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)=|P_{n,r,t}|(1+o(1)), where 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 that almost all T_{r+1}-free oriented graphs are r-partite.

What carries the argument

The r-partition into parts each inducing a T_2^t-free subgraph, obtained by combining stability analysis for near-extremal T_{r+1}^t-free digraphs with the hypergraph container method and a weighted Erdős-Stone theorem.

If this is right

The number of labelled T_{r+1}^t-free oriented graphs equals the number of graphs admitting the r-partition with T_2^t-free parts, up to a (1+o(1)) factor.
The same asymptotic count holds for the corresponding family of digraphs.
When t=1 almost every T_{r+1}-free oriented graph or digraph is r-partite.
The typical examples concentrate on graphs whose structure is exactly this restricted r-partition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same stability-plus-container technique could be tested on other forbidden oriented subgraphs to obtain analogous partition descriptions.
For fixed small r and t, direct enumeration on moderate n would provide a concrete check of how closely the actual count tracks the predicted asymptotic.
The result supplies a model for the concentration of extremal examples around specific multipartite constructions in directed graphs.

Load-bearing premise

The stability analysis for near-extremal T_{r+1}^t-free digraphs remains valid for a in (3/2,2] and combines with the hypergraph container method and weighted Erdős-Stone theorem to force the r-partition property.

What would settle it

A sequence of T_{r+1}^t-free oriented graphs on n vertices, with n growing, that cannot be partitioned into r sets each inducing a T_2^t-free subgraph, yet whose proportion among all such graphs does not tend to zero, would falsify the typical-structure claim.

Figures

Figures reproduced from arXiv: 2605.18458 by Jianxi Liu, Meili Liang, Ruiling Zheng, Yue Guan.

**Figure 1.** Figure 1: for examples). In his classification of countable homogeneous oriented graphs, Cherlin [3] made several conjectures, among them that almost all T3-free oriented graphs are tripartite. This was proved by K¨uhn, Osthus, Townsend and Zhao [7] (KOTZ), who also showed that for any k ≥ 2, almost all Tk+1-free oriented graphs and digraphs are k-partite. A natural generalisation is to forbid a blow-up of a transit… view at source ↗

read the original abstract

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\H{o}s-Stone theorem, and a stability analysis for near-extremal \(T_{r+1}^t\)-free digraphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends the 2017 typical-structure result to blow-ups T_{r+1}^t but the stability lemma's uniformity down to a=3/2 looks like the part that needs the closest check.

read the letter

This paper generalizes the Kühn-Osthus-Townsend-Zhao theorem on almost all T_{r+1}-free oriented graphs and digraphs being r-partite to the case of forbidding blow-ups T_{r+1}^t for any fixed t ≥ 1. The main claim is that almost every such graph or digraph on n vertices has an r-partition in which each induced subgraph on a part is itself T_2^t-free, and this gives the asymptotic count via the family of all such partitioned graphs. For t=1 the statement reduces exactly to the earlier result, which is a clean check. The argument routes through hypergraph containers, a weighted Erdős-Stone theorem, and a stability analysis for near-extremal T_{r+1}^t-free digraphs that is supposed to work for every a in (3/2,2]. That combination is the natural way to push the t=1 case forward, and the abstract indicates they have carried it out. The soft spot is precisely the stability step. If the edit-distance or constant in the stability lemma worsens as a approaches 3/2, the supersaturation supplied by containers may not be strong enough to force every typical member into the claimed partition. The paper treats this as settled, but the parameter range is exactly where one would look first for a gap. This is written for people already working on extremal problems for directed graphs and tournament blow-ups; anyone who has read the 2017 paper will see immediately what has been added. It is worth sending to a serious referee so the stability details and the absorption of error terms can be verified directly.

Referee Report

1 major / 3 minor

Summary. The manuscript proves that for integers r≥2, t≥1 and real a∈(3/2,2], almost every T_{r+1}^t-free oriented graph on n vertices admits an r-partition V_1∪⋯∪V_r such that each induced subgraph G[V_i] is T_2^t-free; the same holds for digraphs. Consequently f(n,T_{r+1}^t)=|P_{n,r,t}|(1+o(1)), where P_{n,r,t} is the family of oriented graphs with this partition property (and analogously for digraphs). When t=1 this recovers the Kühn–Osthus–Townsend–Zhao theorem that almost all T_{r+1}-free oriented graphs/digraphs are r-partite, confirming a generalized form of Cherlin’s conjecture. The 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.

Significance. If the stability result holds uniformly on the stated interval for a, the work supplies a precise typical-structure theorem for a natural family of forbidden directed subgraphs, extending the t=1 case to blow-ups. The combination of container methods with weighted extremal theorems and stability yields an asymptotic enumeration that is a clear advance in the directed extremal theory; the parameter-free nature of the final count (once stability is granted) is a technical strength.

major comments (1)

[§4] §4, stability lemma for near-extremal digraphs: the claimed o(n²) edit-distance bound to the balanced complete r-partite construction with T_2^t-free parts must be shown to hold with constants independent of a as a↓3/2. If the implicit o(1) term or the stability constant deteriorates near the lower endpoint, the supersaturation supplied by the hypergraph containers (used in §5) may no longer force every typical member to admit the asserted r-partition, rendering the typical-structure statement false for part of the parameter range.

minor comments (3)

[Introduction] The introduction should contain a short roadmap paragraph explicitly listing the three main ingredients (containers, weighted Erdős-Stone, stability) and indicating where each is applied.
[§2] Notation for the blow-up T_{r+1}^t and the family P_{n,r,t} is introduced in the abstract but should be repeated with a formal definition in §2 before the main statements.
[§1] A brief remark on why the lower threshold a>3/2 is necessary (or at least natural) would help readers; if it arises from a concrete calculation in the stability proof, a pointer to that calculation is useful.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review of our manuscript and for raising this important point about the uniformity of the stability constants with respect to the parameter a. We address the comment in detail below.

read point-by-point responses

Referee: [§4] §4, stability lemma for near-extremal digraphs: the claimed o(n²) edit-distance bound to the balanced complete r-partite construction with T_2^t-free parts must be shown to hold with constants independent of a as a↓3/2. If the implicit o(1) term or the stability constant deteriorates near the lower endpoint, the supersaturation supplied by the hypergraph containers (used in §5) may no longer force every typical member to admit the asserted r-partition, rendering the typical-structure statement false for part of the parameter range.

Authors: We appreciate the referee's careful attention to the stability lemma in Section 4. Upon re-examining the proof, we confirm that the o(n²) edit-distance bound holds with constants that are independent of a for a ∈ (3/2, 2]. The argument relies on a weighted Erdős-Stone theorem whose error terms are uniform over this closed interval away from the lower endpoint, combined with a stability analysis whose quantitative bounds depend only on r and t. As a ↓ 3/2, the constants remain bounded because the underlying supersaturation inequalities do not degenerate in this range. To make this explicit, we will insert a short paragraph in the revised Section 4 stating the uniformity of all constants with respect to a. This clarification will ensure that the application in Section 5 via the hypergraph container method proceeds uniformly for all a in the stated interval. revision: yes

Circularity Check

0 steps flagged

Derivation combines external methods and independent stability analysis without self-referential reduction

full rationale

The paper derives the typical structure result by combining the hypergraph container method, a weighted Erdős-Stone theorem, and a stability analysis for near-extremal T_{r+1}^t-free digraphs. The abstract explicitly states that the proof uses these tools to establish the r-partition property for almost every T_{r+1}^t-free oriented graph or digraph, with the t=1 case recovering an external 2017 result. No quoted step reduces a prediction or central claim to a fitted input, self-definition, or load-bearing self-citation chain; the stability analysis is presented as part of the proof rather than presupposing the final partition statement. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper invokes standard combinatorial theorems without introducing new free parameters, ad-hoc axioms, or postulated entities.

axioms (1)

standard math Hypergraph container method and weighted Erdős-Stone theorem apply to the family of T_{r+1}^t-free digraphs.
Cited in the abstract as part of the proof strategy.

pith-pipeline@v0.9.0 · 5858 in / 1292 out tokens · 47757 ms · 2026-05-20T09:12:06.868494+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

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.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.