Antidirected trees in directed graphs

George Kontogeorgiou; Giovanne Santos; Maya Stein

REVIEW 1 major objections 4 minor 15 references

Antidirected trees in directed graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A dense digraph with one vertex of very large out-degree and one of very large in-degree contains every bounded-degree balanced antidirected tree of comparable size.

desk verdict A genuine new result with a real but repairable gap in Lemma 5.2(a); worth sending to peer review. read the letter →

arxiv 2501.11726 v2 pith:NTE47JXB submitted 2025-01-20 math.CO

George Kontogeorgiou , Giovanne Santos , Maya Stein This is my paper · ORCID

classification math.CO MSC 05C2005C0705C35

keywords treeembeddingdirectedgraphsantidirectedtreesbalancedminimumsemidegreeregularitylemmaanticonnectedcomponentsKSStheorem

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves a directed analogue of recent smaller-tree versions of the classical spanning-tree theorem for dense graphs (the KSS theorem). It shows that if a large digraph $D$ has minimum semidegree at least $\left(\frac{\ell}{2\ell-1}+\gamma\right)k$ and has a vertex of outdegree and a vertex of indegree at least $(1+\gamma)(\ell-1)k$, then $D$ contains every balanced antidirected tree with $k$ arcs and bounded maximum degree, for $k \geq \gamma n$. Setting $\ell=3$ yields the clean statement that minimum semidegree above $3k/5$ plus vertices of outdegree and indegree above $2k$ forces every such tree; setting $\ell=2$ yields semidegree above $2k/3$ with maximum degree above $k$. These thresholds mirror the asymptotically best possible bounds known for undirected graphs, so the result transfers the shape of the KSS theorem to directed hosts for a natural class of trees.

What carries the argument

The argument runs through the digraph regularity lemma, compressing the host $D-u$ into a reduced digraph $R$ whose vertices are regular clusters. The embedding is governed by the anticonnected components of $R$: maximal subdigraphs in which any two vertices are joined by an antiwalk, a walk whose arcs alternate direction. The load-bearing objects are anticonnected matchings, or antimatchings, disjoint arcs of $R$ that can be connected by antiwalks; Lemma 4.3 produces a large antimatching in any large anticonnected component under the semidegree bound, and Lemma 5.2 embeds a bounded-degree antidirected forest into the regular pairs corresponding to such an antimatching, using short connecting paths between arcs. The theorem then chooses a vertex $u$ of maximum outdegree, cuts the target tree at a vertex $z$ whose removal splits it into $\ell$ forests of controlled sizes, and embeds $z$ at $u$ while distributing the forests among $\ell$ anticonnected components of $R$ that $u$ sees with high degree. The degree-form diregularity lemma for digraphs transfers the original degree assumptions into this reduced setting.

What would settle it

Inspect Step 3 of Lemma 5.2(a): take $C$ to be a bidirected clique on $(1+\gamma)k_R$ clusters in the reduced digraph, so $|V(C)|=(1+\gamma)k_R < 2\left(\frac12+\gamma\right)k_R$, and check whether an antimatching of size $\left(\frac12+\gamma\right)k_R$ still exists; if $C$ can arise as an anticonnected component of a digraph meeting the theorem's degree bounds, the proof's key estimate fails and the argument must be repaired.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.5: for every $\gamma>0$, $c\in\mathbb{R}$, and $\ell\in\mathbb{N}$ with $\ell\geq 2$, there exists $n_0$ such that for every $n\geq n_0$ and $k\geq \gamma n$, every digraph $D$ on $n$ vertices with $\delta^0(D) \geq \left(\frac{\ell}{2\ell-1}+\gamma\right)k$ and $\Delta(D) \geq (1+\gamma)(\ell-1)k$ contains every balanced antidirected tree $T$ with $k$ arcs and $\Delta(T) \leq (\log n)^c$. Here $\delta^0(D)$ is the minimum semidegree, the smaller of a vertex's in- and out-degree, and $\Delta(D)$ is the largest $m$ such that $D$ has a vertex of outdegree at least $m$ and a vertex of indegree at least $m$. A balanced antidirected tree is an oriented tree in which every vertex is a source or a sink, so directions alternate along every path, and the numbers of sources and sinks are equal. The theorem is a smaller-tree version of the directed analogue of the KSS theorem, and it asymptotically reproduces the known optimal degree thresholds from the graph setting.

Load-bearing premise

The proof needs every anticonnected component $C$ of the reduced digraph to contain at least $2\left(\frac12+\gamma\right)k_R$ vertices, so that Lemma 4.3 yields an antimatching of size $\left(\frac12+\gamma\right)k_R$; this bound is asserted without proof and is false for a bidirected clique on $(1+\gamma)k_R$ clusters, which satisfies the degree hypotheses.

Editorial extensions

If this is right

With $\ell=3$, every large digraph with minimum semidegree at least $(1+\gamma)3k/5$ and vertices of outdegree and indegree at least $2(1+\gamma)k$ contains every balanced antidirected tree with $k$ arcs and bounded degree.
With $\ell=2$, minimum semidegree at least $(1+\gamma)2k/3$ plus maximum degree at least $(1+\gamma)k$ suffices, and the semidegree bound cannot be improved because the analogous graph example blocks any weaker threshold.
Sending $\ell$ to infinity gives an asymptotic digraph version of the Hyde--Reed theorem: for every $\varepsilon>0$, minimum semidegree above $(1+\varepsilon)k/2$ plus maximum degree at least $k/\varepsilon$ forces every such tree.
The result asymptotically solves, for balanced antidirected bounded-degree trees, a problem about oriented trees in digraphs that was open in this generality.
The same machinery reproves the earlier oriented-graph theorem that minimum semidegree above $(1+\gamma)k/2$ suffices for balanced antidirected bounded-degree trees.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof's component-by-component strategy suggests the result may extend to oriented trees that are not necessarily balanced, if the size condition on the anticonnected components can be adjusted to match the two colour classes of the tree.
Because the extremal graph examples that force the semidegree threshold use bidirected complete bipartite structures, the true threshold for the $\ell=3$ case may be close to $k/2$ rather than $3k/5$; the paper leaves this open.
A testable refinement would be to replace the maximum-degree bound $k/\varepsilon$ in the asymptotic corollary by a constant multiple $Ck$, checking whether the component-counting argument still yields $\ell$ usable components.
The embedding lemma is stated for bounded-degree trees with $\Delta(T)\leq (\log n)^c$, but the same anticonnected-matching framework would likely tolerate slightly larger degrees if the connecting antiwalks can be kept short.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear [Colleague],

Here's my read on the Kontogeorgiou–Santos–Stein paper.

The short version: this is a real result, and the high-level argument is sound, but there's a genuine gap in Lemma 5.2(a) that needs to be fixed before the proof is complete. The gap is not fatal—it looks patchable—but as written, the proof is incomplete.

What's new: the theorem extends the KSS embedding theorem to digraphs for balanced bounded-degree antidirected trees of size proportional to n, with combined min- and max-degree conditions. This is not a routine translation, because digraphs admit 2-cycles, which break the oriented-graph arguments from Stein–Zárate-Guerén. The anticonnected-components machinery is a sensible way to handle that. The bounds match the essentially best-possible bounds from the undirected and oriented settings, and the result asymptotically resolves Problem 6.13 for this class. The paper is clearly written, and the reliance on external lemmas is honest; no circularity concern.

The soft spot is real. In Lemma 5.2(a), Step 3, the proof needs an antimatching of size (1/2+γ)k_R and asserts |V(C)| ≥ 2(1/2+γ)k_R to apply Lemma 4.3. That inequality is not proved and is false: a bidirected clique on (1+γ)k_R clusters satisfies the degree hypotheses but has |V(C)| ≤ (1+γ)k_R < (1+2γ)k_R, so no antimatching of that size exists. This is load-bearing, since the antimatching carries the pieces of the tree.

But the repair is straightforward. Take t = (1/2+γ/2)k_R. Then |V(C)| ≥ (1+γ)k_R ≥ 2t, and δ0(R) ≥ (1/2+γ)k_R ≥ t, so Lemma 4.3 applies. The antimatching is still larger than k/2, which is all the embedding needs. The constants in Lemma 3.4 need a small adjustment, but nothing structural changes. I also noticed a few typos, e.g., a garbled inequality in Lemma 4.2(ii) and an undefined m in Lemma 3.4; those are minor.

Bottom line: this paper is for the extremal graph theory crowd—anyone working on tree embeddings or the regularity method will want to know it. It deserves a serious referee. I'd send it to review, asking the authors to fix Lemma 5.2(a) before acceptance. If the repair checks out, it's a solid addition to the literature.

Referee Report

1 major / 4 minor

Summary. The paper proves a directed analogue of the Komlós-Sárközy-Szemerédi tree-embedding theorem for smaller bounded-degree balanced antidirected trees. Theorem 1.5 asserts that for every γ>0, c∈R, ℓ≥2, any sufficiently large digraph D with minimum semidegree δ0(D) ≥ (ℓ/(2ℓ−1)+γ)k and with some vertex of outdegree and some vertex of indegree at least (1+γ)(ℓ−1)k contains every balanced antidirected tree T with k arcs and maximum total degree at most (log n)^c, for all k ≥ γn. The proof combines the directed regularity lemma, tree-decomposition lemmas (Lemmas 3.2 and 3.3), a partitioning lemma (Lemma 3.4), and a matching lemma for anticonnected components (Lemma 4.3). The main embedding step (Lemma 5.2) first finds a large antimatching in a large anticonnected component of the reduced digraph and then embeds the tree pieces into the corresponding regular pairs, with connections established via antiwalks in the reduced digraph. The final section uses a vertex of large outdegree to split the tree into ℓ forests and embeds each forest into one of ℓ anticonnected components seen by that vertex, yielding the theorem.

Significance. If the proof is completed, the result is a significant extension of the KSS framework to digraphs for a natural class of oriented trees. The degree bounds are shown to be essentially best possible in several regimes via existing examples, and the corollaries (Corollaries 1.2 and 1.3) give clean, interpretable statements that relate to known graph and oriented-graph results. The proof is built entirely from published regularity and embedding lemmas, and it contains no fitted parameters, which makes the overall structure transparent. The paper also quickly reproduces a recent result on antidirected trees in oriented graphs (Corollary 5.3), demonstrating the reach of the method.

major comments (1)

[Lemma 5.2(a), Step 3 (also used in Corollary 5.3 and Theorem 1.5)] The proof asserts |V(C)| ≥ 2(1/2+γ)k_R and then invokes Lemma 4.3 with t = (1/2+γ)k_R. This inequality does not follow from the preceding degree condition. Lemma 4.2(i) gives min{|Out(C)|, |In(C)|} ≥ δ0(R) ≥ (1/2+γ)k_R, but Out(C) and In(C) need not be disjoint, so |V(C)| ≥ 2(1/2+γ)k_R can fail. For example, a bidirected clique on m = ⌊(1+γ)k_R⌋ clusters is anticonnected and satisfies δ0(R) = m−1 ≥ (1/2+γ)k_R, yet |V(C)| = m < (1+2γ)k_R; since every vertex lies in Out(C) ∩ In(C), the underlying graph has matching number at most ⌊m/2⌋ < (1/2+γ)k_R, so no antimatching of the required size exists. This gap is load-bearing because the antimatching is the structure into which the pieces of T are partitioned via Lemma 3.4 and then embedded via Lemma 5.1. A repair appears feasible by taking t = ⌊|V(C)|/2⌋, which is at least about ((1+γ)/2)k_R and still large enough to meet the capacity condition max{∑p, ∑q} < (1−10√ε)st in Lemma 3.4 after adjusting the constants; the authors should supply a written proof of this modified step.

minor comments (4)

[Abstract and Section 3.1] The minimum semidegree is denoted δ^0(D) in the abstract and δ0(D) in the main text and Theorem 1.5; please unify the notation.
[Section 2.1] The example of two anticonnected components intersecting at a single vertex refers to a figure that is missing from the text; include the figure in the final version.
[Corollary 5.3] The proof of the claim 'So C has the desired size' is very terse; expanding the inequality that uses the orientedness of D to show the component is large would improve readability.
[Section 6, around equation (11)] The inequality verification ends with 'as the reader can check'; a short derivation of that elementary inequality would make the paper more self-contained.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: Theorem 1.5 is derived from external regularity and embedding lemmas; self-citations to [2] and [14] are ordinary published tools, not assumptions of the theorem.

full rationale

The paper does not fit parameters, rename a known result, or import a uniqueness theorem. Its derivation chain is: apply the Alon--Shapira diregularity lemma and Fact 3.7 to pass to the reduced digraph; decompose T via Lemma 3.2; embed pieces through the anticonnected-matching Lemma 4.3 and the embedding Lemmas 5.1/5.2. Lemmas 3.3 and 3.4 are quoted from [2] and [14] (co-authored by Stein), but they are independent published statements about tree decomposition and partitioning, not consequences of Theorem 1.5; the same holds for Lemma 5.1, whose small d-generalization is footnoted as an easy verification. The central claim is therefore not equivalent to its inputs by construction and no fitted quantity is relabelled as a prediction. The serious issue raised by the skeptic is a proof gap, not circularity: in Lemma 5.2(a), Step 3, the inequality |V(C)| ≥ 2(1/2+γ)k_R is asserted without proof and can fail, e.g. for a bidirected clique on about (1+γ)k_R clusters; the antimatching size then need not exist. That gap affects correctness of the written proof but does not make the argument circular, since Lemma 4.3 is an independent combinatorial tool rather than an assumption of the target theorem. The paper itself also flags its restrictions to balanced antidirected bounded-degree trees as limitations of the proof method, not as circular definitions. Score 2 reflects only the presence of several non-load-bearing self-citations in the toolchain.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theorem is proved from published regularity and tree-embedding tools; no free parameters are fitted, and no new entities are postulated. Several inputs are co-authored by one of the present authors ([2], [3], [14]), but they are independent published results.

assumptions (5)

standard math Degree form of the diregularity lemma for digraphs (Alon-Shapira, Lemma 3.6)
Used to pass from D to a bounded-size reduced digraph R with regular pairs.
standard math Fact 3.7: minimum semidegree of D transfers to reduced digraph R
Used in Lemma 5.2 and Section 6 to lower-bound δ0(R).
standard math Tree decomposition lemmas (Lemma 3.3 from [2], Lemma 3.4 from [14])
Used to cut T into seeds, parts, links and pieces with controlled source and sink counts.
standard math Lemma 5.1 from [14] embedding antidirected trees into regular antiwalks
Core embedding step inside anticonnected components.
standard math Lemma 3.1 from [3]: existence of a vertex splitting a tree into balanced components
Used to find z and partition T-z into forests J_1,...,J_l.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Antidirected trees in directed graphs." pith.science (2026). https://pith.science/paper/NTE47JXB

@misc{pith2026250111726,
  author       = {Pith},
  title        = {Pith review of: Antidirected trees in directed graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NTE47JXB}},
  note         = {Machine review of arXiv:2501.11726}
}

abstract

The Koml\'os-S\'ark\"ozy-Szemer\'edi (KSS) theorem establishes that a certain bound on the minimum degree of a graph guarantees it contains all bounded degree trees of the same order. Recently several authors put forward variants of this result, where the tree is of smaller order than the host graph, and the host graph also obeys a maximum degree condition. Also, Kathapurkar and Montgomery extended the KSS theorem to digraphs. We bring these two directions together by establishing minimum and maximum degree bounds for digraphs that ensure the containment of oriented trees of smaller order. Our result is restricted to balanced antidirected trees of bounded degree. More precisely, we show that for every $\gamma > 0$, $c\in\mathbb{R}$, $\ell\geq 2$ sufficiently large $n$ and all $k\geq\gamma n$, the following holds for every $n$-vertex digraph $D$ and every balanced antidirected tree $T$ with $k$ arcs whose total maximum degree is bounded by $(\log n)^c$. If $D$ has a vertex of outdegree at least $(1+\gamma)(\ell -1)k$, a vertex of indegree at least $(1+\gamma)(\ell -1)k$ and minimum semidegree $\delta^0(D)\geq\left(\frac{\ell}{2\ell -1}+\gamma\right)k$, then $D$ contains $T$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Testing subgraphs in directed graphs

Noga Alon and Asaf Shapira. Testing subgraphs in directed graphs. InProceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 700–709, 2003

work page 2003
[2]

Degree conditions for embedding trees.SIAM Journal on Discrete Mathematics, 33(3):1521–1555, 2019

Guido Besomi, Matías Pavez-Signé, and Maya Stein. Degree conditions for embedding trees.SIAM Journal on Discrete Mathematics, 33(3):1521–1555, 2019

work page 2019
[3]

Frédéric Havet, Bruce Reed, Maya Stein, and David R. Wood. A variant of the Erdős-Sós conjecture.J. Graph Theory, 94(1):131–158, 2020

work page 2020
[4]

Graphs of minimum degree at least⌊d/2⌋ and large enough maximum degree embed every tree with d vertices.Procedia Computer Science, 223:217–222, 2023

Joseph Hyde and Bruce Reed. Graphs of minimum degree at least⌊d/2⌋ and large enough maximum degree embed every tree with d vertices.Procedia Computer Science, 223:217–222, 2023

work page 2023
[5]

Spanning trees in dense directed graphs.Journal of Com- binatorial Theory, Series B, 156:223–249, 2022

Amarja Kathapurkar and Richard Montgomery. Spanning trees in dense directed graphs.Journal of Com- binatorial Theory, Series B, 156:223–249, 2022

work page 2022
[6]

Cycles of given length in oriented graphs.Journal of Combi- natorial Theory, Series B, 100(3):251–264, 2010

Luke Kelly, Daniela Kühn, and Deryk Osthus. Cycles of given length in oriented graphs.Journal of Combi- natorial Theory, Series B, 100(3):251–264, 2010

work page 2010
[7]

Sárközy, and Endre Szemerédi

János Komlós, Gábor N. Sárközy, and Endre Szemerédi. Spanning trees in dense graphs.Combinatorics, Probability and Computing, 10(5):397–416, 2001

work page 2001
[8]

The regularity lemma and its applications in graph theory.Summer school on theoretical aspects of computer science, pages 84–112, 2000

János Komlós, Ali Shokoufandeh, Miklós Simonovits, and Endre Szemerédi. The regularity lemma and its applications in graph theory.Summer school on theoretical aspects of computer science, pages 84–112, 2000

work page 2000

Show all 15 references

[9]

Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result.Journal of Graph Theory, 102(4):737–783, 2023

Bruce Reed and Maya Stein. Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result.Journal of Graph Theory, 102(4):737–783, 2023

2023
[10]

Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result.Journal of Graph Theory, 102(4):797–821, 2023

Bruce Reed and Maya Stein. Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result.Journal of Graph Theory, 102(4):797–821, 2023

2023
[11]

Women in Mathematics in Latin America,

Maya Stein. Degree conditions for trees in undirected and directed graphs. To appear in the volume "Women in Mathematics in Latin America," part of the Springer-Birkhäuser Trends in Mathematics Series, 2024

2024
[12]

Oriented trees and paths in digraphs.Fischer, F., Johnson, R

Maya Stein. Oriented trees and paths in digraphs.Fischer, F., Johnson, R. eds, Surveys in Combinatorics. London Mathematical Society Lecture Note Series. Cambridge University Press, 2024

2024
[13]

Oriented trees in digraphs without oriented 4-cycles, 2024

Maya Stein and Ana Trujillo-Negrete. Oriented trees in digraphs without oriented 4-cycles, 2024. arXiv:2411.13483

2024 arXiv
[14]

Antidirected subgraphs of oriented graphs.Combinatorics, Proba- bility and Computing, 33(4):446–466, 2024

Maya Stein and Camila Zárate-Guerén. Antidirected subgraphs of oriented graphs.Combinatorics, Proba- bility and Computing, 33(4):446–466, 2024

2024
[15]

Regular partitions of graphs

Endre Szemerédi. Regular partitions of graphs. Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No. 260, 399-401, 1978. Centro de Modelamiento Matemático (CNRS IRL2807), Universidad de Chile, Santiago, Chile Email address: gkontogeorgiou@dim.uchile...

1976

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Testing subgraphs in directed graphs

Noga Alon and Asaf Shapira. Testing subgraphs in directed graphs. InProceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 700–709, 2003

work page 2003

[2] [2]

Degree conditions for embedding trees.SIAM Journal on Discrete Mathematics, 33(3):1521–1555, 2019

Guido Besomi, Matías Pavez-Signé, and Maya Stein. Degree conditions for embedding trees.SIAM Journal on Discrete Mathematics, 33(3):1521–1555, 2019

work page 2019

[3] [3]

Frédéric Havet, Bruce Reed, Maya Stein, and David R. Wood. A variant of the Erdős-Sós conjecture.J. Graph Theory, 94(1):131–158, 2020

work page 2020

[4] [4]

Graphs of minimum degree at least⌊d/2⌋ and large enough maximum degree embed every tree with d vertices.Procedia Computer Science, 223:217–222, 2023

Joseph Hyde and Bruce Reed. Graphs of minimum degree at least⌊d/2⌋ and large enough maximum degree embed every tree with d vertices.Procedia Computer Science, 223:217–222, 2023

work page 2023

[5] [5]

Spanning trees in dense directed graphs.Journal of Com- binatorial Theory, Series B, 156:223–249, 2022

Amarja Kathapurkar and Richard Montgomery. Spanning trees in dense directed graphs.Journal of Com- binatorial Theory, Series B, 156:223–249, 2022

work page 2022

[6] [6]

Cycles of given length in oriented graphs.Journal of Combi- natorial Theory, Series B, 100(3):251–264, 2010

Luke Kelly, Daniela Kühn, and Deryk Osthus. Cycles of given length in oriented graphs.Journal of Combi- natorial Theory, Series B, 100(3):251–264, 2010

work page 2010

[7] [7]

Sárközy, and Endre Szemerédi

János Komlós, Gábor N. Sárközy, and Endre Szemerédi. Spanning trees in dense graphs.Combinatorics, Probability and Computing, 10(5):397–416, 2001

work page 2001

[8] [8]

The regularity lemma and its applications in graph theory.Summer school on theoretical aspects of computer science, pages 84–112, 2000

János Komlós, Ali Shokoufandeh, Miklós Simonovits, and Endre Szemerédi. The regularity lemma and its applications in graph theory.Summer school on theoretical aspects of computer science, pages 84–112, 2000

work page 2000