pith. sign in

arxiv: 2012.09201 · v2 · pith:SCV4EEE3new · submitted 2020-12-16 · 🧮 math.CO

Trees and treelike structures in dense digraphs

Richard Mycroft , T\'assio Naia This is my paper

Pith reviewed 2026-05-24 14:21 UTC · model grok-4.3

classification 🧮 math.CO
keywords oriented treesdigraph embeddingsminimum semidegreespanning subdigraphstree-like structuresdirected graphscycle collectionssubdivided graphs
0
0 comments X

The pith

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).

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

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.

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.

Figures

Figures reproduced from arXiv: 2012.09201 by Richard Mycroft, T\'assio Naia.

Figure 1
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 … view at source ↗
Figure 2
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. 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 α, … view at source ↗
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) ϕ maps precisely one vertex of Q to each v ∈ V0; (iv) ϕ maps at least λ 0n/k centres of paths in P H to each i ∈ [k]; (v) For each i ∈ [k] we ha… view at source ↗
read the original 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.

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.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 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.

axioms (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.

pith-pipeline@v0.9.0 · 5656 in / 1325 out tokens · 27119 ms · 2026-05-24T14:21:16.840384+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  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

  9. [9]

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

    work page 1997

  10. [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

    work page 1960

  11. [11]

    Janson, T

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

    work page 2000

  12. [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

    work page 1995

  13. [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

    work page 2001

  14. [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

    work page 2017

  15. [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

    work page 2011

  16. [16]

    McDiarmid

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

    work page 1998

  17. [17]

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

    work page 1970

  18. [18]

    Mycroft and T

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

    work page 2018

  19. [19]

    Sudakov and J

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

    work page 2010

  20. [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

    work page 1975

  21. [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.mycroft@bham.ac.uk Tássio Naia, Instituto de Matemática e Estatística, Universida...

    work page 1976