Oriented Trees in Digraphs without Oriented $4$-cycles

Ana Trujillo-Negrete; Maya Stein

REVIEW 2 major objections 4 minor 1 cited by

Oriented Trees in Digraphs without Oriented $4$-cycles

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper proves that forbidding all oriented 4-cycles in a digraph makes minimum semidegree k/2 plus a vertex with indegree and outdegree at least k sufficient to contain every oriented tree with k arcs.

desk verdict A solid, genuinely new digraph analogue of the C4-free tree embedding theorem; the main proof holds up, secondary theorems are abbreviated but worth refereeing. read the letter →

arxiv 2411.13483 v1 pith:NICA2G5X submitted 2024-11-20 math.CO

Maya Stein , Ana Trujillo-Negrete This is my paper · ORCID

classification math.CO MSC 05C2005C0505C35

keywords orientedtreesdigraphembedding4-cycle-freedigraphsminimumsemidegreeantidirectedarborescencesErdős–Sósconjecture

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

The paper establishes a degree threshold for embedding oriented trees in digraphs. It proves that a digraph with minimum semidegree at least k/2, having both a vertex of outdegree at least k and a vertex of indegree at least k, and containing no oriented 4-cycle as a subgraph must contain every oriented tree with k arcs. This lowers the naive greedy threshold from minimum semidegree k to k/2 by adding a single short-cycle exclusion. The same proof strategy yields stronger statements for antidirected trees and for out-arborescences, where only one side of the degree condition is needed.

What carries the argument

The argument proceeds by building the tree in reverse: start with a maximal subtree T1 of diameter at most four containing a maximum-total-degree vertex t and its neighbours, embed it, then undo a pruning sequence in which each next tree is obtained by deleting the leaf neighbours of a minimum-degree penultimate vertex. The load-bearing step is double-counting over the sets Na of unused out- or in-neighbours of vertices a in Q = N⋄(v̂) \ f(V(T')); inequality (5) uses C4-freeness to conclude that every already-embedded vertex outside a tiny exceptional set lies in at most one Na and that v̂2 is exceptional, yielding q ≤ 2. The remainder splits into q=2 and q=1 cases, each forced into contradictions by the structure of the tree and the forbidden 4-cycles.

What would settle it

A concrete counterexample would be a digraph D with minimum semidegree exactly ⌈k/2⌉, a vertex of outdegree at least k and a vertex of indegree at least k, no oriented 4-cycle, together with a k-arc oriented tree T not contained in D. A small exhaustive computer search over such digraphs for k ≤ 6, checking all oriented trees on k arcs, would settle the corollary; alternatively, constructing a C*4-free host satisfying the degree conditions but omitting some k-arc tree would show the proof's stronger C4-free assumption is not needed for the theorem.

Watch

Extended reading notes

Core claim

Theorem 1 states that if T is an oriented tree with k arcs and D is a digraph with δ0(D) ≥ k/2 and no oriented 4-cycles, then Δ±(D) > Δtot(T) suffices for T to embed in D. Since Δtot(T) can equal k only for stars, and stars embed as soon as Δ±(D) ≥ k with δ0(D) ≥ k/2, the corollary follows: every digraph with δ0(D) ≥ k/2, Δ±(D) ≥ k, and no oriented 4-cycles contains each k-arc oriented tree. The proof also gives Theorem 3, replacing minimum semidegree by minimum pseudo-semidegree and forbidding only non-directed 4-cycles when T is antidirected, and Theorem 4, where an out-arborescence needs only an outdegree condition on the host.

Load-bearing premise

The proof's double-counting inequality (5) assumes that forbidding 4-cycles forces each embedded vertex outside a small set to be seen by at most one of the candidate vertices a, and that one particular vertex v̂2 is seen by none; if the host had more orientations of 4-cycles, that bound could break.

Editorial extensions

If this is right

Every oriented tree with k arcs appears in any C4-free digraph meeting the degree conditions, so stars, paths, caterpillars, and arbitrary branching patterns are all forced.
For antidirected trees, the host may contain directed 4-cycles, and the semidegree condition may be relaxed to pseudo-semidegree, widening the class of admissible hosts.
A dense digraph with more than (k−1)n arcs whose 4-cycles are all directed contains every antidirected k-arc tree whose maximum total degree is at most k/2, a special case of the Addario-Berry et al. conjecture.
For out-arborescences rooted at a maximum-total-degree vertex, only an outdegree bound and a slightly lower outdegree minimum are needed, and for oriented hosts the outdegree minimum can be k/2 − 1.

Reading between the lines

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

Because most of the proof runs under the weaker assumption that only non-directed 4-cycles are forbidden, a natural next test is whether Theorem 1 remains true with directed 4-cycles allowed; the paper leaves this as Problem 6.2.
The undirected analogue suggests a family of forbidden complete bipartite orientations may work as well; Question 6.3 asks exactly this for K2,s-free digraphs.
The density-based Corollary 7 is evidence for the full conjecture on antidirected trees in digraphs with more than (k−1)n arcs, since forbidding non-directed 4-cycles is one way to rule out the known extremal obstruction.

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

Main takeaway: this is a real result, not a repackaging. The theorem extends Saclé-Woźniak's C4-free undirected result to digraphs with one-sided degree conditions, and Corollary 7 gives a new special case of the Addario-Berry et al. conjecture. The proof is a long counting argument, but I re-read the steps the reader flagged and they hold. The derivation of Eq. (7) uses an implicit fact about the pruning sequence that is true; the justification could be expanded but it's not a gap. The C4-free double-counting in (5) is sound. The stress-test note confirms these points, and I agree: no fatal flaw in the central argument.

What's new: Theorem 1 and Corollary 2 are a genuine directed analogue. The refinements for antidirected trees and arborescences are new. The proof is self-contained; external results only for context. No fitted parameters, no circularity. The paper is honest about what it doesn't know, e.g., whether all orientations of 4-cycles need to be forbidden (Section 6.3).

Soft spots: The proofs of Theorems 3 and 4 are abbreviated. Several passages say 'straightforward to verify' covering statements (15)-(19) and the exclusion of q=2 in the oriented arborescence case. This is the main weakness: it's likely fixable, but as written it leaves the advertised improvements less secure than the main theorem. Also, the justification around Eq. (7) is terse; the reader had to supply an implicit argument. Minor. The self-citations are appropriate: they cite their own prior special cases and the companion paper, and the cited results are external or previously established.

Citation pattern: fine. The paper builds on [14] and extends [19], no red flags. The discussion of Conjecture 6 is accurate, and the deduction of Corollary 7 via the known lemma from [10] is clean.

Who is this for: extremal digraph theorists, anyone working on tree embedding problems, Erdős-Sós type questions. The paper deserves a serious referee; the central theorem is significant enough to be sent to review, though the referee should push for fuller proofs of Theorems 3 and 4.

Recommendation: send to peer review, with a request that the authors expand the abbreviated sections. I'd take the main theorem as correct with moderate to high confidence.

Referee Report

2 major / 4 minor

Summary. The paper proves that every oriented tree with k arcs embeds into any digraph D with no oriented 4-cycles, minimum semidegree at least k/2, and maximum outdegree/indegree at least k (Corollary 2, derived from the stronger Theorem 1). The proof embeds a diameter-at-most-four subtree, then uses a pruning sequence and a maximal-embedding contradiction argument with a double-counting inequality over neighbourhoods in the host. The paper also states and proves variants for antidirected trees (Theorem 3, allowing directed 4-cycles and weakening the minimum-semidegree condition to pseudo-semidegree) and for out-arborescences (Theorem 4, weakening the degree requirement when the host is oriented), and derives a partial case of a conjecture of Addario-Berry et al. (Corollary 7).

Significance. If the proof is correct, Theorem 1 gives a natural digraph analogue of the Saclé–Woźniak result for graphs without C4, and Corollary 2 is a clean, sharp-looking degree condition guaranteeing all oriented k-edge trees. The proof is self-contained and parameter-free: it uses only combinatorial counting over the pruning sequence, with no fitted constants or numerical search. Theorems 3 and 4 are meaningful extensions, and Corollary 7 is a genuine step toward a known conjecture on antidirected trees in dense digraphs. The main weakness is not the overall strategy but the level of detail in several load-bearing verification steps, especially in the oriented-arborescence case and in the justification of the degree bound used to pass from inequality (6) to q ≤ 2 in Theorem 1.

major comments (2)

[§3, Eq. (7)] The inference "du + 1 = deg(u) < k/2 (as deg(u) ≤ deg(t) and T has diameter at least five)" is not justified by the text as written. A diameter-5 tree can have a vertex of maximum total degree larger than k/2 (for example, a broom with many leaves at t and a path of length three), so deg(u) ≤ deg(t) alone does not give the stated bound. The intended argument must use that u was chosen as a minimum-degree penultimate vertex in the pruning sequence, and that a diameter-5 tree has at least two penultimate vertices, so not all of them can have degree at least k/2. This argument should be written out because the bound is load-bearing for the transition from (6) to q ≤ 2.
[§5, Proposition 5, oriented case] Two key assertions in the oriented case are only labelled "straightforward to verify": the claim that q ≤ 2, and the claim that statements (15)–(19) hold for the redefined vertex sets (with pu and pv). These are not merely cosmetic omissions. In the oriented case the minimum outdegree is k/2 − 1, not k/2, so the analogue of inequality (3) has a different constant and the derivation of q ≤ 2 from (5)–(7) requires a modified calculation. Likewise, the structural statements (15)–(19) are proved in Theorem 1 using the specific definitions of u, v, w, x, and y; the arborescence proof changes the definitions of Y and x, so those arguments need to be rechecked in detail. Since Theorem 4 is advertised in the abstract and is one of the paper's main contributions, these omissions leave a load-bearing part of the proof incomplete.

minor comments (4)

[§1, last paragraph] The phrase "or a a different family" appears to contain a typo; it should presumably read "or a different family."
[§3, after Eq. (3)] The text "Th is means that for all a ∈ Q" should read "This means that for all a ∈ Q."
[§3, displayed equation (5) and following paragraph] The notation f(V(T′)) is used both for the image of T′ and for the union R ∪ Ŵ ∪ {v̂}; the explanation that f(V(T′)) = R ∪ Ŵ ∪ {v̂} is clear, but the phrase "the fact that D is C∗4-free" appears in the middle of the inequality verification and would be easier to follow if the sentence were split.
[References [6] and [8]] The entries contain LaTeX artifacts "/suppress" (e.g., "T. /suppress Luczak") that should be removed before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a self-contained combinatorial derivation.

full rationale

The paper's central result (Theorem 1, and hence Corollary 2) is proved by a direct embedding argument: it constructs an initial embedding of a diameter-at-most-four subtree, applies a pruning sequence, and reaches a contradiction using double-counting and the C4-free hypothesis. The conclusion that T embeds is not used as an assumption anywhere; the only external inputs are standard degree-counting facts and the paper's own notation. The inequalities (3)–(6) and the case analysis are derived from the definitions of the embedding and the host digraph conditions, not from a fitted parameter or from the target statement. The authors' citations to their own prior work ([18], [19]) are used only for context, open problems, or as alternative results, and are not load-bearing for Theorem 1 or Corollary 2. The abbreviated parts, such as the 'straightforward to verify' passages in Theorems 3 and 4, represent omitted details rather than circular reasoning. Thus no step reduces, by the paper's own equations or by self-citation, to its own inputs.

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

No free parameters are introduced. The paper postulates no new mathematical objects. It relies on standard graph-theoretic background and one external lemma from the literature for a corollary. The third axiom is an implicit fact used in the proof that should be stated explicitly.

assumptions (3)

standard math Lemma 9 of Klimošová and Stein [10]: every n-vertex digraph with more than (k-1)n arcs has a subdigraph of minimum pseudo-semidegree at least k/2.
Used in Section 6.1 to derive Corollary 7 from Theorem 3. Not needed for the proof of the main theorem.
standard math The undirected tree containment result of Saclé and Woźniak [14] for graphs without C4.
Motivates the digraph analogue. It is not used as a logical input in the proof of Theorem 1.
standard math In any tree with at least five edges, there exists a penultimate vertex with degree less than k/2, where k is the number of edges.
Used implicitly around Eq. (7) in Section 3 to conclude d_u + 1 < k/2. The argument requires the minimum-degree choice in the pruning sequence, not just deg(u) <= deg(t).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Oriented Trees in Digraphs without Oriented $4$-cycles." pith.science (2026). https://pith.science/paper/NICA2G5X

@misc{pith2026241113483,
  author       = {Pith},
  title        = {Pith review of: Oriented Trees in Digraphs without Oriented $4$-cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NICA2G5X}},
  note         = {Machine review of arXiv:2411.13483}
}

abstract

We prove that if $D$ is a digraph of maximum outdegree and indegree at least $k$, and minimum semidegree at least $k/2$ that contains no oriented $4$-cycles, then $D$ contains each oriented tree $T$ with~$k$ arcs. This can be slightly improved if $T$ is either antidirected or an arborescence.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Antidirected trees in directed graphs
math.CO 2025-01 conditional novelty 7.0 of 10

A digraph with minimum semidegree above ℓ/(2ℓ−1) times the tree size and with vertices of large out- and indegree contains every balanced antidirected bounded-degree tree of that size.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages · cited by 1 Pith paper

[14]

Sacl´ e and M

J.-F. Sacl´ e and M. Wo´ zniak. The Erd˝ os–S´ os conjecture for graphs without C4. J. Combin. Theory Ser. B , 70(2):367–372, 1997

work page 1997
[19]

Antidirected trees in dense digraphs

M. Stein and A. Trujillo-Negrete. Antidirected trees i n dense digraphs. arXiv preprint arXiv:2404.10750, 2024

work page Pith review arXiv 2024
[10]

Klimoˇ sov´ a and M

T. Klimoˇ sov´ a and M. Stein. Antipaths in oriented graphs. Discrete Math., 346(9):113515, 2023

work page 2023
[1]

Addario-Berry, F

L. Addario-Berry, F. Havet, C. L. Sales, B. Reed, and S. Th omass´ e. Oriented trees in digraphs. Discrete Math., 313(8):967–974, 2013

work page 2013
[2]

Besomi, M

G. Besomi, M. Pavez-Sign´ e, and M. Stein. Degree conditi ons for embedding trees. SIAM J. Discrete Math., 33(3):1521–1555, 2019. 8

work page 2019
[3]

Brandt and E

S. Brandt and E. Dobson. The Erd˝ os-S´ os conjecture for graphs of girth 5. Discrete Math., 150 (1-3):411–414, 1996

work page 1996
[4]

S. A. Burr. Subtrees of directed graphs and hypergraphs. In Proceedings of the Eleventh South- eastern Conference on Combinatorics, Graph Theory a nd Combinatorics (Florida At- lantic Univ., Boca Raton, Fla. , volume I,28, pages 227–239, 1980

work page 1980
[5]

B. Chen, X. Hou, and H. Zhou. Long antipaths and anticycle s in oriented graphs. arXiv preprint arXiv:2401.05205, 2024

work page Pith review arXiv 2024

Show all 21 references

[6]

E. Dobson. Some problems in extremal and algebraic graph theory . Ph.d. dissertation, Louisiana State University, Baton Rouge, 1995

1995
[7]

Havet, B

F. Havet, B. Reed, M. Stein, and D. R. Wood. A variant of the Erd˝ os-S´ os conjecture.Journal of Graph Theory , 94(1):131–158, 2020

2020
[8]

P. E. Haxell and T. /suppress Luczak. Embedding trees into graphs of large girth. Discrete Math. , 216 (1-3):273–278, 2000

2000
[9]

T. Jiang. On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B , 83 (2):221–232, 2001

2001
[11]

Kontogeorgiou, G

G. Kontogeorgiou, G. Santos, and M. Stein. Antidirecte d trees in directed graphs. In prepara- tion
[12]

Reed and M

B. Reed and M. Stein. Spanning trees in graphs of high min imum degree with a universal vertex I: An asymptotic result. J. Graph Theory , 102(4):737–783, 2023

2023
[13]

Reed and M

B. Reed and M. Stein. Spanning trees in graphs of high min imum degree with a universal vertex II: A tight result. J. Graph Theory , 102(4):797–821, 2023

2023
[15]

Skokan and M

J. Skokan and M. Tyomkyn. Alternating paths in oriented graphs with large semidegree. arXiv preprint arXiv:2406.03166, 2024

2024 arXiv
[16]

M. Stein. Degree conditions for trees in undirected and directed graphs. In Women in Mathe- matics in Latin America , Trends in Mathematics. Springer-Birkh¨ auser. To appear
[17]

M. Stein. Tree containment and degree conditions. In A. Raigoroskii and M. Rassias, editors, Discrete Math. Appl. , volume 165 of Springer Optim. Appl. , pages 459–486. Springer, Cham, 2021

2021
[18]

M. Stein. Oriented trees and paths in digraphs. In F. Fis cher and R. Johnson, editors, Surveys in Combinatorics 2024 , volume 493 of London Math. Soc. Lecture Note Ser. , pages 271–295. Cambridge Univ. Press, Cambridge, 2024

2024
[20]

Stein and C

M. Stein and C. Z´ arate-Guer´ en. Antidirected subgraphs of oriented graphs. Combin. Probab. Comput., 33(4):446–466, 2024

2024
[21]

Sudakov and J

B. Sudakov and J. Vondr´ ak. A randomized embedding algorithm for trees. Combinatorica, 30: 445–470, 2010. 9

2010

Pith tools

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

[1] [14]

Sacl´ e and M

J.-F. Sacl´ e and M. Wo´ zniak. The Erd˝ os–S´ os conjecture for graphs without C4. J. Combin. Theory Ser. B , 70(2):367–372, 1997

work page 1997

[2] [19]

Antidirected trees in dense digraphs

M. Stein and A. Trujillo-Negrete. Antidirected trees i n dense digraphs. arXiv preprint arXiv:2404.10750, 2024

work page Pith review arXiv 2024

[3] [10]

Klimoˇ sov´ a and M

T. Klimoˇ sov´ a and M. Stein. Antipaths in oriented graphs. Discrete Math., 346(9):113515, 2023

work page 2023

[4] [1]

Addario-Berry, F

L. Addario-Berry, F. Havet, C. L. Sales, B. Reed, and S. Th omass´ e. Oriented trees in digraphs. Discrete Math., 313(8):967–974, 2013

work page 2013

[5] [2]

Besomi, M

G. Besomi, M. Pavez-Sign´ e, and M. Stein. Degree conditi ons for embedding trees. SIAM J. Discrete Math., 33(3):1521–1555, 2019. 8

work page 2019

[6] [3]

Brandt and E

S. Brandt and E. Dobson. The Erd˝ os-S´ os conjecture for graphs of girth 5. Discrete Math., 150 (1-3):411–414, 1996

work page 1996

[7] [4]

S. A. Burr. Subtrees of directed graphs and hypergraphs. In Proceedings of the Eleventh South- eastern Conference on Combinatorics, Graph Theory a nd Combinatorics (Florida At- lantic Univ., Boca Raton, Fla. , volume I,28, pages 227–239, 1980

work page 1980

[8] [5]

B. Chen, X. Hou, and H. Zhou. Long antipaths and anticycle s in oriented graphs. arXiv preprint arXiv:2401.05205, 2024

work page Pith review arXiv 2024