Pith. sign in

REVIEW 2 minor 1 cited by

Trees and treelike structures in dense digraphs

T0 review · 0 major / 2 minor · reviewed 2026-05-24 · grok-4.3

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

Pith's one-line read Every oriented tree on n vertices with bounded maximum degree is a spanning subdigraph of every n-vertex digraph whose minimum semidegree is at least n/2 + o(n).

desk verdict The paper gives the first explicit directed analogue of the Komlós–Sárközy–Szemerédi theorem for bounded-degree oriented trees and a few other tree-like spanning structures under the natural semidegree condition. read the letter →

arxiv 2012.09201 v2 pith:SCV4EEE3 submitted 2020-12-16 math.CO

Richard Mycroft , Tássio Naia This is my paper · ORCID
classification math.CO
keywords orientedtreesdigraphembeddingsminimumsemidegreespanningsubdigraphstree-likestructuresdirectedgraphscyclecollectionssubdivided
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 shows that the minimum semidegree condition n/2 + o(n) in a directed graph on n vertices is enough to guarantee that every bounded-degree oriented tree on the same number of vertices appears as a spanning subdigraph. This mirrors a classical undirected embedding theorem and extends it to the directed setting. The main result is obtained by proving a broader statement that also covers arbitrary orientations of up to O(n^0.99) vertex-disjoint cycles and of subdivisions of graphs H whose order is smaller than exp(sqrt(O(log n))) with each edge subdivided at least once. A reader would care because the semidegree hypothesis now forces the existence of these spanning tree-like objects without further restrictions on the host digraph beyond its density.

What carries the argument

The minimum semidegree condition, which forces every vertex to have sufficiently many in-neighbors and out-neighbors to support inductive embedding of the oriented tree-like structures.

What would settle it

A single n-vertex digraph with minimum semidegree at least n/2 + o(n) that contains no spanning copy of some fixed bounded-degree oriented tree on n vertices.

Watch

Extended reading notes

Core claim

We prove that every oriented tree on n vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on n vertices with minimum semidegree at least n/2+o(n). This can be seen as a directed graph analogue of a well-known theorem of Komlós, Sárközy and Szemerédi. Our result for trees follows from a more general result, allowing the embedding of arbitrary orientations of a much wider class of spanning “tree-like” structures, such as collections of at most O(n^{0.99}) pairwise vertex-disjoint cycles and subdivisions of graphs H with |H| < exp (√O(log n)) in which each edge is subdivided at least once.

Load-bearing premise

The tree-like structures being embedded must obey the stated quantitative restrictions on degree, number of cycles, or size of the base graph H.

Editorial extensions

If this is right

  • Every bounded-degree oriented tree on n vertices embeds as a spanning subdigraph under the semidegree hypothesis.
  • Arbitrary orientations of any collection of at most O(n^{0.99}) vertex-disjoint cycles embed as spanning subdigraphs.
  • Arbitrary orientations of subdivisions of any H with |H| < exp(sqrt(O(log n))) and each edge subdivided at least once embed as spanning subdigraphs.

Reading between the lines

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

  • The same semidegree threshold may suffice for embedding other families of oriented graphs whose underlying undirected graphs have bounded treewidth.
  • The result supplies a uniform way to obtain directed analogues of many classical spanning-tree theorems once the appropriate degree or size bounds are verified.
  • In the special case of tournaments the same semidegree condition immediately yields the corresponding oriented-tree embeddings.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The manuscript proves that every oriented tree on n vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on n vertices with minimum semidegree at least n/2 + o(n). This is presented as a directed analogue of the Komlós–Sárközy–Szemerédi theorem. The tree result is derived from a more general theorem allowing embeddings of arbitrary orientations of collections of at most O(n^{0.99}) pairwise vertex-disjoint cycles and subdivisions of graphs H with |H| < exp(√O(log n)) in which each edge is subdivided at least once.

Significance. If the result holds, it supplies a combinatorial proof of an asymptotic directed embedding theorem for bounded-degree oriented trees and certain tree-like spanning structures in dense digraphs. The explicit quantitative restrictions on the number of cycles and the size of H are stated clearly, and the argument is framed as building on a cited undirected theorem without reduction to fitted parameters. This strengthens the toolkit for extremal problems in oriented graphs.

minor comments (2)
  1. [Abstract and §1] The o(n) error term in the semidegree hypothesis is stated in the abstract and introduction but would benefit from an explicit remark on whether the implicit constant depends on the maximum degree bound of the tree (or on the parameters of the general structures).
  2. [§1] Notation for semidegree (minimum of in- and out-degree) is used without a dedicated definition paragraph; a short preliminary section collecting all degree and embedding notation would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the recognition of the result as a directed analogue of the Komlós–Sárközy–Szemerédi theorem, and the recommendation of minor revision. The report highlights the combinatorial proof and the explicit quantitative bounds on cycles and subdivided graphs, which aligns with the framing in our manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper states a combinatorial embedding theorem for bounded-degree oriented trees (and extensions to limited cycles and small subdivided graphs) as spanning subdigraphs of dense digraphs, explicitly framed as an analogue of the external Komlós–Sárközy–Szemerédi theorem. The abstract and claim description contain no fitted parameters renamed as predictions, no self-definitional equations, and no load-bearing self-citations; the cited undirected result is by independent authors. The quantitative restrictions are stated explicitly rather than smuggled in, and the derivation is presented as an independent proof rather than a reduction to its own inputs.

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

The result rests on standard combinatorial embedding techniques and the cited undirected theorem; no free parameters, ad-hoc constants, or new postulated entities are introduced in the abstract.

assumptions (1)
  • domain assumption The undirected Komlós–Sárközy–Szemerédi theorem on spanning trees in dense graphs holds and can be adapted to the directed setting.
    The abstract explicitly frames the new result as a directed analogue of this known theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Trees and treelike structures in dense digraphs." pith.science (2026). https://pith.science/paper/SCV4EEE3

@misc{pith2026201209201,
  author       = {Pith},
  title        = {Pith review of: Trees and treelike structures in dense digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SCV4EEE3}},
  note         = {Machine review of arXiv:2012.09201}
}
abstract

We prove that every oriented tree on $n$ vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on $n$ vertices with minimum semidegree at least $n/2+o(n)$. This can be seen as a directed graph analogue of a well-known theorem of Koml\'os, S\'ark\"ozy and Szemer\'edi. Our result for trees follows from a more general result, allowing the embedding of arbitrary orientations of a much wider class of spanning ``tree-like'' structures, such as collections of at most $O(n^{0.99})$ pairwise vertex-disjoint cycles and subdivisions of graphs $H$ with $|H| < \exp (\sqrt{O(\log n)})$ in which each edge is subdivided at least once.

Figures

Figures reproduced from arXiv: 2012.09201 by the authors.

Figure 1
Figure 1. Left: a (◦→ • ←•)-diamond. Right: a (◦← • ←•)-diamond (◦ is the root of the path). in a digraph D is a sequence of P-diamonds ui vi v 0 i wi t i=0 such that vi = v 0 i−1 for each i ∈ [t]; we say that this path connects v0 and v 0 t . Finally, a graph G is P-connected if there exists a P-diamond path connecting each pair u, v ∈ G. Lemma 27 (P-connected subgraphs). Suppose 1 n α. Let D be a digraph with of order n su… view at source ↗
Figure 2
Figure 2. Weight-shifting from vertex u to vertex v using P-diamond. 12 of 33 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. The graph Q∗ := (Q − V (Q0)) − E∗ . Vertices in Q0 are crossed, edges in E ∗ are dashed, and vertices in R are circled. (Edges incident with V (Q0) are not present in Q∗ .) Each component of Q∗ is a tree (coloured black). Proof of Theorem 2. Let T be an oriented tree of order n with ∆(T) ≤ ∆ and let G be a digraph of order n with δ 0 (G) ≥ (1/2 + α)n. We introduce new constants λ and λ 0 with 1/n λ λ 0 α, ∆. If T co… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The digraph H4 ⊆ R? [[k]], with E(H4 ) = {1u, u1, u`, `1, 1r, ur}. Vertex 1 is marked. Every oriented path with at most 3 arcs admits a homomorphism to H4 mapping both of its leaves to 1. (ii) |P0 | = |V0| and for each P ∈ P0 the centre of P is mapped to V0; (iii) ϕ ma…

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

  1. Embedding loose trees in $k$-uniform hypergraphs

    math.CO 2025-02 conditional novelty 7.0 of 10

    For k at least 4, sufficiently large k-uniform hypergraphs with minimum (k-2)-degree at least (1/2+gamma) binom(n,k-2) contain every spanning loose tree of maximum degree at most Delta.

Reference graph

Works this paper leans on

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

  1. [1]

    N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster. The algorithmic aspects of the regularity lemma.Journal of Algorithms, 16(1):80–109, 1994

    work page 1994

  2. [2]

    Balogh, B

    J. Balogh, B. Csaba, and W. Samotij. Local resilience of almost spanning trees in random graphs.Random Structures & Algorithms, 38(1-2):121–139, 2011

    work page 2011

  3. [3]

    J. A. Bondy and U.S.R. Murty.Graph theory, volume 244 ofGraduate Texts in Mathematics . Springer-Verlag, New York, 2008

    work page 2008

  4. [4]

    Böttcher, J

    J. Böttcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk, and Y. Person. Universality for bounded degree spanning trees in randomly perturbed graphs.Random Structures & Algorithms , 55(4):854–864, 2019

    work page 2019

  5. [5]

    Böttcher, M

    J. Böttcher, M. Schacht, and A. Taraz. Proof of the bandwidth conjecture of Bollobás and Komlós.Mathematische Annalen, 343(1):175–205, 2009

    work page 2009

  6. [6]

    Clemens, A

    D. Clemens, A. Ferber, R. Glebov, D. Hefetz, and A. Liebenau. Building spanning trees quickly in maker-breaker games. SIAM Journal on Discrete Mathematics , 29(3):1683–1705, 2015

    work page 2015

  7. [7]

    DeBiasio, D

    L. DeBiasio, D. Kühn, T. Molla, T. Osthus, and A. Taylor. Arbitrary orientations of hamilton cycles in digraphs.SIAM Journal on Discrete Mathematics , 29(3):1553–1584, 2015

    work page 2015

  8. [8]

    DeBiasio and T

    L. DeBiasio and T. Molla. Semi-degree threshold for anti-directed Hamiltonian cycles.Electronic Journal of Combina- torics, 22(4), 2015

    work page 2015

Show all 21 references
  1. [9]

    R. Diestel. Graph theory, volume 173 ofGraduate Texts in Mathematics . Springer-Verlag, New York, 1997. Translated from the 1996 German original

    1997

  2. [10]

    Ghouila-Houri

    M.A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit Hamiltonien.Comptes Rendus de l’Académie des Sciences, 25:495–497, 1960

    1960

  3. [11]

    Janson, T

    S. Janson, T. Łuczak, and A. Ruciński.Random graphs. Wiley-Interscience, New York, 2000

    2000

  4. [12]

    Komlós, G.N

    J. Komlós, G.N. Sárközy, and E. Szemerédi. Proof of a packing conjecture of Bollobás.Combinatorics, Probability, and Computing, 4(3):241–255, 1995

    1995

  5. [13]

    Komlós, G.N

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

    2001

  6. [14]

    Krivelevich, M

    M. Krivelevich, M. Kwan, and B. Sudakov. Bounded-degree spanning trees in randomly perturbed graphs.SIAM J. Discrete Math., 31(1):155––171, 2017

    2017

  7. [15]

    D. Kühn, R. Mycroft, and D. Osthus. An approximate version of Sumner’s universal tournament conjecture.Journal of Combinatorial Theory, Series B , 101(6):415–447, 2011

    2011

  8. [16]

    McDiarmid

    C. McDiarmid. Concentration. InProbabilistic methods for algorithmic discrete mathematics , volume 16 ofAlgorithms Combin., pages 195–248. Springer, Berlin, 1998

    1998

  9. [17]

    J.W. Moon. Counting labelled trees . Number 1 in Canadian Mathematical Monographs. Canadian Mathematical Congress, 1970

    1970

  10. [18]

    Mycroft and T

    R. Mycroft and T. Naia. Unavoidable trees in tournaments.Random Structures & Algorithms , 53(2):352–385, 2018

    2018

  11. [19]

    Sudakov and J

    B. Sudakov and J. Vondrák. A randomized embedding algorithm for trees.Combinatorica, 30(4):445–470, 2010

    2010

  12. [20]

    Szemerédi

    E. Szemerédi. On sets of integers containing nok elements in arithmetic progression.Acta Arith., 27:199–245, 1975. Collection of articles in memory of Juri˘ ı VladimiroviŁ Linnik

    1975

  13. [21]

    Szemerédi

    E. Szemerédi. Regular partitions of graphs. InProblèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) , pages 399–401. CNRS, Paris, 1978. Richard Mycroft, University of Birmingham, Birmingham, B15 2TT, United Kingdom Email address: r.m...

    1976

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.