A container theorem for general digraphs
with forbidden subdigraphs
March 19, 2026
Abstract
In a seminal work, Kühn, Osthus, Townsend, and Zhao used the hypergraph container method to determine the typical structure of oriented graphs and digraphs avoiding a fixed tournament or cycle. Their main tool, a container theorem for oriented graphs, does not directly extend to all digraphs due to the existence of counterexamples such as the double triangle \(DK_3\). In this paper we prove a container theorem for general digraphs under a natural sparsity condition. For the edge-weight parameter \(a=2\), this condition permits digraphs with \(2\)-cycles (density at most \(1\)) but excludes denser obstructions like \(DK_3\); for larger \(a\) it allows digraphs with a controlled density of \(2\)-cycles. As applications, we obtain asymptotic counting results for \(H\)-free digraphs and describe the typical structure of digraphs avoiding a fixed digraph \(H\) satisfying our condition. Our results unify and extend several previous results in the area.
Keywords: container method, digraph, forbidden subgraph, typical structure, extremal combinatorics.
2020 Mathematics Subject Classification: 05C20, 05C35, 05C30, 05C65.
1 Introduction↩︎
The problem of enumerating and describing the typical structure of graphs with forbidden subgraphs has a long history, starting with the classical work of Erdős, Kleitman and Rothschild [1] on \(K_k\)-free graphs. They proved that almost all \(K_k\)-free graphs are \((k-1)\)-partite, and more generally, for many graphs \(H\), almost all \(H\)-free graphs have a structure close to the extremal \(H\)-free graph. These results have been extended to hypergraphs and to various other settings.
For directed graphs (digraphs) the picture is far less complete. The only results of this type for oriented graphs (digraphs with no 2-cycles) were obtained by Kühn, Osthus, Townsend and Zhao [2] (hereafter referred to as KOTZ), who used the hypergraph container method, which was developed independently and simultaneously by Saxton and Thomason [3] and Balogh, Morris and Samotij [4], to answer questions of Cherlin [5] about the typical structure of \(T_3\)-free and \(C_3\)-free oriented graphs. Among other results, they proved the following container theorem for oriented graphs.
Theorem 1 (KOTZ, Theorem 3.3). Let \(H\) be an oriented graph with \(h=v(H)\) and \(e(H)\ge 2\), and let \(a\ge 1\). For every \(\varepsilon>0\) there exists \(c>0\) such that for all sufficiently large \(N\) there exists a collection \(\mathcal{C}\) of digraphs on \([N]\) with the following properties.
Every \(H\)-free oriented graph \(I\) on \([N]\) is contained in some \(G\in\mathcal{C}\).
Every \(G\in\mathcal{C}\) contains at most \(\varepsilon N^h\) copies of \(H\), and \(e_a(G)\le \mathop{\mathrm{ex}}_a(N,H)+\varepsilon N^2\).
\(\log|\mathcal{C}|\le c N^{2-1/m(H)}\log N\), where \(m(H)=\max_{H'\subseteq H,\,e(H')>1}\frac{e(H')-1}{v(H')-2}\).
Here \([N]=\{1,\dots,N\}\), and for a digraph \(G\) we denote by \(f_2(G)\) the number of unordered pairs \(\{u,v\}\) with both \(uv\) and \(vu\) present, and by \(f_1(G)\) the number of unordered pairs with exactly one directed edge. The weighted size \(e_a(G)=a\cdot f_2(G)+f_1(G)\) is introduced to unify the treatment of digraphs (\(a=2\)) and oriented graphs (\(a=\log_23\), since each 2-cycle can be oriented in three ways when considering oriented subgraphs). \(\mathop{\mathrm{ex}}_a(n,H)\) is the maximum of \(e_a(G)\) over all \(H\)-free digraphs on \(n\) vertices.
As noted in [2], this theorem cannot be extended to all digraphs \(H\) without additional assumptions. The double triangle \(DK_3\) (the complete digraph on three vertices) provides a counterexample: there exist families of \(DK_3\)-free digraphs whose number is far larger than \(2^{\mathop{\mathrm{ex}}_2(n,DK_3)}\), violating the natural counting corollary that would follow from a container theorem. The obstruction comes from the high density of \(DK_3\) (six edges on three vertices), which allows many sparse \(DK_3\)-free digraphs that are not captured by a small number of containers with near-extremal edge count. An illustration of \(DK_3\) is given in Figure 1.
In this paper we prove a container theorem for general digraphs under a natural sparsity condition that excludes such dense counterexamples. Our condition is:
- Condition A (sparsity). For every subgraph \(H'\subseteq H\) with \(e(H')>1\), \[\frac{e(H')}{v(H')}\le \frac{a}{2},\] where \(a\) is the same parameter as in the definition of \(e_a\).
When \(a=2\), Condition A reads \(e(H')/v(H')\le 1\). This does not forbid \(2\)-cycles—a single \(2\)-cycle has two edges and two vertices, so its density is exactly \(1\). It does, however, rule out denser configurations such as the double triangle \(DK_3\) (density \(2\)). Thus our theorem genuinely extends the container method beyond oriented graphs: for \(a>2\) it permits digraphs with a controlled number of \(2\)-cycles, while for \(a=2\) it includes all digraphs whose subgraphs have density at most \(1\). For an illustration, Figure 2 shows a digraph on five vertices that satisfies Condition A with \(a=2\): it contains one \(2\)-cycle yet its overall density is \(1\).
Theorem 2. Let \(H\) be a digraph satisfying Condition A with respect to \(a\ge 1\), let \(h=v(H)\) and \(e(H)\ge2\). For every \(\varepsilon>0\) there exists \(c>0\) such that for all sufficiently large \(N\) there exists a collection \(\mathcal{C}\) of digraphs on \([N]\) with the following properties.
Every \(H\)-free digraph \(I\) on \([N]\) is contained in some \(G\in\mathcal{C}\).
Every \(G\in\mathcal{C}\) contains at most \(\varepsilon N^h\) copies of \(H\), and \[e_a(G)\le \mathop{\mathrm{ex}}_a(N,H)+\varepsilon N^2.\]
\(\displaystyle \log|\mathcal{C}|\le c N^{2-1/m(H)}\log N\), where \(m(H)=\max_{H'\subseteq H,\,e(H')>1}\frac{e(H')-1}{v(H')-2}\).
As an immediate corollary we obtain an asymptotic counting result.
Corollary 1. Let \(H\) satisfy Condition A and \(e(H)\ge2\). Then \[f^*(n,H)=2^{\mathop{\mathrm{ex}}_2(n,H)+o(n^2)},\] where \(f^*(n,H)\) denotes the number of labelled \(H\)-free digraphs on \(n\) vertices.
2 Notation and preliminaries↩︎
2.1 Digraphs and weighted edges↩︎
For a digraph \(G=(V,E)\) we write \(f_2(G)\) for the number of unordered pairs \(\{u,v\}\) such that both \(uv\) and \(vu\) belong to \(E\), and \(f_1(G)\) for the number of unordered pairs with exactly one directed edge. A \(2\)-cycle (or double edge) is a pair of opposite directed edges between two vertices, i.e., both \(uv\) and \(vu\) are present. Thus \(f_2(G)\) counts the number of \(2\)-cycles.
For a real number \(a\ge1\) define the weighted size \[e_a(G)=a\cdot f_2(G)+f_1(G).\] For \(a=2\) this is simply the total number of directed edges, and for \(a=\log_23\) it counts oriented subgraphs (each \(2\)-cycle contributes \(3\) choices, each \(1\)-edge contributes \(2\)). Denote by \(\mathop{\mathrm{ex}}_a(n,H)\) the maximum of \(e_a(G)\) over all \(H\)-free digraphs on \(n\) vertices.
2.2 The hypergraph container theorem↩︎
We need the following version of the container theorem due to Saxton and Thomason [3]. For an \(r\)-uniform hypergraph \(\mathcal{H}\) with vertex set \([n]\), let \(\Delta_j(\mathcal{H})\) be the maximum number of edges containing a given set of \(j\) vertices. For \(\tau>0\), define \(\delta_j\) by \[\delta_j\tau^{j-1}n\Delta_1 = \sum_{v\in V(\mathcal{H})}\Delta_j(\{v\}).\] Then the co-degree function is \(\delta(\mathcal{H},\tau)=2^{\binom{r}{2}-1}\sum_{j=2}^r2^{-(j-1)}\delta_j\).
Theorem 3 (Saxton–Thomason [3], Corollary 2.7). Let \(0<\varepsilon<1/2\) and \(\tau\le 1/(144 r^2 r!)\). Suppose \(\mathcal{H}\) is an \(r\)-graph on \([n]\) satisfying \(\delta(\mathcal{H},\tau)\le \frac{\varepsilon}{12\tau}\). Then there exists a collection \(\mathcal{C}\) of subsets of \([n]\) with
every independent set of \(\mathcal{H}\) is contained in some \(C\in\mathcal{C}\);
\(e(\mathcal{H}[C])\le\varepsilon e(\mathcal{H})\) for all \(C\in\mathcal{C}\);
\(\log|\mathcal{C}|\le c(r) n\tau\log(1/\tau)\).
2.3 The auxiliary hypergraph↩︎
For a fixed digraph \(H\) with \(r=e(H)\), define an \(r\)-uniform hypergraph \(\mathcal{D}(N,H)\) as follows. Its vertex set is \[U=\{(i,j):i,j\in[N],\;i\neq j\},\] the set of all ordered pairs of distinct vertices. A set of \(r\) such pairs forms an edge if they constitute a copy of \(H\) in the labelled sense: there exists an injective map \(\phi:V(H)\to[N]\) such that the \(r\) ordered pairs are exactly \(\{(\phi(u),\phi(v)):uv\in E(H)\}\).
3 Key lemmas↩︎
3.1 Degree estimate↩︎
The following lemma is the crucial estimate that allows us to apply the container theorem. Its proof follows the same lines as the proof of Lemma 9.2 in [3], with modifications to handle \(2\)-cycles via Condition A. We give a self‑contained derivation of the required bounds.
Lemma 1. Let \(H\) be a digraph satisfying Condition A, with \(r=e(H)\ge2\). For any \(\gamma\le1\) and sufficiently large \(N\), \[\delta\bigl(\mathcal{D}(N,H),\,\gamma^{-1}N^{-1/m(H)}\bigr)\le C(H)\gamma,\] where \(C(H)=r2^{r^2}v(H)!^2\).
Proof. Let \(\mathcal{D}=\mathcal{D}(N,H)\) and let \(n=|U|=N^2-N\). The number of edges of \(\mathcal{D}\) is \((N)_h\), the falling factorial, which satisfies \((N)_h\sim N^h\). Hence the average degree \(d\) of \(\mathcal{D}\) is \[d = \frac{r e(\mathcal{D})}{n} \sim \frac{r N^h}{N^2}=rN^{h-2}.\]
For a set \(\sigma\subseteq U\), denote by \(d(\sigma)\) the number of edges of \(\mathcal{D}\) containing \(\sigma\). For a vertex \(v\in U\), define \[d^{(j)}(v)=\max\{d(\sigma):v\in\sigma,\;|\sigma|=j\}.\]
Recall the definition of \(\delta_j\): \[\delta_j\tau^{j-1}nd = \sum_{v\in U} d^{(j)}(v).\]
Step 1: A crude bound↩︎
Fix a \(j\)-set \(\sigma\subseteq U\) and let \(s\) be the number of distinct vertices of \([N]\) occurring in \(\sigma\); clearly \(s\le 2j\). The number of ways to extend \(\sigma\) to a full copy of \(H\) is at most \(C_1 N^{h-s}\) for some constant \(C_1\) depending on \(H\). Hence \(d(\sigma)\le C_1 N^{h-s}\). Summing over all \(\sigma\) containing a fixed \(v\), there are at most \(N^{2(j-1)}\) such \(\sigma\), so \[\sum_{\sigma\ni v} d(\sigma) \le C_1 N^{2(j-1)} N^{h} = C_1 N^{h+2j-2}.\] This gives \(d^{(j)}(v)\le C_1 N^{h+2j-2}\) and summing over \(v\) yields \(\sum_v d^{(j)}(v)\le C_1 n N^{h+2j-2}\), which is too weak because the exponent is positive. We need a bound that decreases with \(j\).
Step 2: Using the structure of \(H\)↩︎
Let \(H_0\) be a subgraph of \(H\) attaining the maximum in the definition of \(m(H)\), i.e. \[m(H)=\frac{e(H_0)-1}{v(H_0)-2}.\] Set \(h_0=v(H_0)\), \(r_0=e(H_0)\). Then \(m(H)=m(H_0)\).
For a \(j\)-set \(\sigma\), consider the subgraph \(F\) of \(H\) induced by the edges corresponding to \(\sigma\) (after identifying vertices appropriately). Let \(s=v(F)\) and \(e(F)=j\). By definition of \(m(H)\), for any subgraph \(F\) with \(j=e(F)>1\) we have \(e(F)-1\le m(H)(s-2)\), i.e. \[s \ge \frac{j-1}{m(H)}+2. \]
If \(\sigma\) can be extended to a copy of \(H\), then after placing the \(s\) vertices of \(F\), we need to add \(h-s\) new vertices to complete \(H\). Hence the number of extensions is at most \(C_2 N^{h-s}\) for some \(C_2\) depending on \(H\). Consequently, \[d(\sigma) \le C_2 N^{h-s} \le C_2 N^{h-2-(j-1)/m(H)}. \]
Step 3: Uniform bound and summation↩︎
The estimate (2.2) holds for every \(j\)-set \(\sigma\) with \(j\ge 2\). (For \(j=1\) we simply use the trivial bound \(d(\{v\})\le r N^{h-2}\) which is compatible with the shape above.) The constant \(C_2\) can be taken as \(v(H)!\,2^{r^2}\), where the factorial accounts for the ordering of the \(h\) vertices and \(2^{r^2}\) absorbs any overcounting from the fact that a \(2\)-cycle contributes two distinct ordered pairs to \(U\). Crucially, Condition A guarantees that (2.1) holds for every \(F\) that can appear, so the exponent of \(N\) is correct regardless of the presence of \(2\)-cycles.
Now, by definition, \(d^{(j)}(v)=\max\{d(\sigma):v\in\sigma,\;|\sigma|=j\}\). For each \(v\) we may choose a maximizer \(\sigma_v\); applying (2.2) yields \[d^{(j)}(v) \le C_2 N^{h-2-(j-1)/m(H)}.\] Summing over all \(v\in U\) and using \(n=|U|\le N^2\) we obtain \[\sum_{v\in U} d^{(j)}(v) \le n\,C_2 N^{h-2-(j-1)/m(H)}.\] This is exactly inequality (1) announced in the sketch, with \(C_5=C_2(1+o(1))\). For simplicity we may use the generous constant \(C_5 = r2^{r^2}v(H)!^2\), which certainly bounds \(C_2\) from above.
Step 4: Deriving the bound on \(\delta_j\)↩︎
From the definition of \(\delta_j\) and the average degree \(d\) we have \[\delta_j\tau^{j-1}nd \le \sum_{v\in U} d^{(j)}(v) \le C_5 n N^{h-2-(j-1)/m(H)}.\] Substitute \(\tau = \gamma^{-1}N^{-1/m(H)}\) and the asymptotic lower bound \(d \ge \frac{1}{2} rN^{h-2}\) (valid for large \(N\)): \[\delta_j \le \frac{C_5 N^{h-2-(j-1)/m(H)}}{\tau^{j-1} n d} \le \frac{C_5 N^{h-2-(j-1)/m(H)}}{\gamma^{-(j-1)}N^{-(j-1)/m(H)} \cdot N^2 \cdot \frac{1}{2} rN^{h-2}} = \frac{2C_5}{r}\,\gamma^{\,j-1}.\]
Step 5: Computing \(\delta(\mathcal{D},\tau)\)↩︎
Finally, \[\begin{align} \delta(\mathcal{D},\tau) &= 2^{\binom{r}{2}-1}\sum_{j=2}^r 2^{-(j-1)}\delta_j \\ &\le 2^{\binom{r}{2}-1}\sum_{j=2}^r 2^{-(j-1)}\frac{2C_5}{r}\gamma^{\,j-1} \\ &= \frac{2C_5}{r}2^{\binom{r}{2}-1}\gamma\sum_{j=2}^r (2^{-1}\gamma)^{j-2}. \end{align}\] Since \(\gamma\le1\), the geometric series is bounded by \(2\), so \[\delta(\mathcal{D},\tau) \le \frac{4C_5}{r}2^{\binom{r}{2}-1}\gamma.\] Using \(C_5 = r2^{r^2}v(H)!^2\) and \(2^{\binom{r}{2}}\le 2^{r^2}\), we see that \[\delta(\mathcal{D},\tau) \le r2^{r^2}v(H)!^2\,\gamma =: C(H)\,\gamma,\] which completes the proof. ◻
3.2 Supersaturation↩︎
The following supersaturation lemma is a standard consequence of the Erdős–Simonovits supersaturation theorem; we state it without proof.
Lemma 2. Let \(H\) be any digraph with \(h\) vertices and let \(a\ge1\). For every \(\varepsilon>0\) there exists \(\delta>0\) such that for all sufficiently large \(n\), any digraph \(G\) on \(n\) vertices containing at most \(\delta n^h\) copies of \(H\) satisfies \[e_a(G)\le \mathop{\mathrm{ex}}_a(n,H)+\varepsilon n^2.\]
4 Proof of Theorem 2↩︎
Proof. Fix \(H\) satisfying Condition A with respect to \(a\), and let \(\varepsilon>0\) be given. Choose \(\delta\) from Lemma 2 corresponding to \(\varepsilon\). Set \(m=m(H)\) and \[\tau = N^{-1/m},\qquad \gamma = 1.\] (The choice \(\gamma=1\) is harmless; any fixed \(\gamma>0\) would lead to the same asymptotic.) By Lemma 1 we have \[\delta\bigl(\mathcal{D}(N,H),\tau\bigr) \le C(H)\,\gamma = C(H).\] To apply the container theorem (Theorem 3), we need \(\delta(\mathcal{D},\tau)\le \frac{\varepsilon}{12\tau}\). Notice that \[\frac{\varepsilon}{12\tau} = \frac{\varepsilon}{12} N^{1/m},\] which grows without bound as \(N\) increases. Since \(C(H)\) depends only on \(H\), we can choose \(N\) large enough so that \(C(H) \le \frac{\varepsilon}{12} N^{1/m}\), thereby satisfying the hypothesis of Theorem 3.
Thus we obtain a family \(\mathcal{C}_0\) of subsets of \(U\) (the containers) with the properties:
every independent set of \(\mathcal{D}\) is contained in some \(C\in\mathcal{C}_0\);
\(e(\mathcal{D}[C])\le \varepsilon\,e(\mathcal{D})\) for all \(C\in\mathcal{C}_0\);
\(\log|\mathcal{C}_0|\le c(r) N^{2-1/m}\log N\), where \(c(r)\) depends only on \(r\).
Interpret each container \(C\) as the edge set of a digraph \(G_C\) on \([N]\). Because \(e(\mathcal{D})\sim N^h\), after possibly shrinking \(\varepsilon\) by a constant factor we may assume that \(G_C\) contains at most \(\varepsilon N^h\) copies of \(H\). Lemma 2 then yields \(e_a(G_C)\le \mathop{\mathrm{ex}}_a(N,H)+\varepsilon N^2\).
Define \(\mathcal{C}=\{G_C:C\in\mathcal{C}_0\}\). Then \(|\mathcal{C}|=|\mathcal{C}_0|\) and properties (a)–(c) of Theorem 2 are exactly the ones listed above. This completes the proof. ◻
5 Discussion: necessity of the condition and open problems↩︎
The double triangle \(DK_3\) fails Condition A for \(a=2\) because \(e/v=2>1\), so it is correctly excluded. This explains why it serves as a counterexample: its density is too high, causing the degree estimate to break down. For \(a>2\), Condition A allows digraphs with density up to \(a/2\), which includes many graphs containing \(2\)-cycles. Characterising precisely those digraphs for which a container theorem holds remains an interesting open problem. Possible directions include imposing bounds on \(m(H)\) or on the maximum multiplicity of \(2\)-cycles. We leave these investigations for future work.
References↩︎
Email: jxliu@gdufs.edu.cn. Corresponding author.↩︎