Subdivisions of digraphs in tournaments

Ant\'onio Gir\~ao; Kamil Popielarz; Richard Snyder

REVIEW 3 major objections 5 minor 14 references

Subdivisions of digraphs in tournaments

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read A tournament with minimum out-degree at least (2+o(1))k^2 always contains a subdivision of the complete directed graph on k vertices, and this is best possible up to a factor of 8.

desk verdict The quadratic bound for complete digraph subdivisions is a real advance, but the proof of Theorem 2.4 has a load-bearing gap in its iterative step that the stress-test correctly identifies; the Lemma 3.2 issue is a minor typo by comparison. read the letter →

arxiv 1908.03733 v1 pith:2Q5IGWZB submitted 2019-08-10 math.CO

António Girão , Kamil Popielarz , Richard Snyder This is my paper · ORCID

classification math.CO MSC 05C2005C35

keywords tournamentssubdivisionscompletedigraphminimumout-degreetransitivetournament1-subdivisionextremalgraphtheorydirectedgraphs

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 establishes a directed analogue of the classical graph subdivision theorem: a tournament whose minimum out-degree is at least (2+o(1))$k^{2}$ must contain a subdivision of the complete directed graph on k vertices. The bound is shown to be tight up to a factor of 8, since there are tournaments with minimum out-degree about $k^{2}$/4 that contain no such subdivision. The proof gives an explicit quantitative version: minimum out-degree $2k^{2}$ + $147k^{{7/4}}$ suffices, and the subdivision can be realized with each edge replaced by a directed path of length at most 3. Using the same ideas, the paper also proves that any tournament on O($k^{2}$) vertices contains a subdivision of the transitive tournament on k vertices with paths of length at most 3, and any tournament on O($k^{2}$ $log^{3}$ k) vertices contains a 1-subdivision of the transitive tournament.

What carries the argument

The load-bearing object is an (α,m,k)-balanced set: k vertices whose in-degrees all lie in an interval of length $k^{{7/4}}$, with each in-degree at least $αk^{2}$ + $2k^{{7/4}}$; Lemma 2.2 finds such a set whenever the tournament is large enough. Lemma 2.3 then supplies a dichotomy: relative to this balanced branch set, either a partial subdivision T_→K_k(ℓ1,ℓ2) exists whose number of length-2 and length-3 paths satisfies 4(ℓ1+ℓ2)+$6k^{{7/4}}$ > m, or the tournament has a cut set U whose source component S has |S| ≥ |U|+k and whose sink has size at least k. Iterating the dichotomy, Claim 2 gives the expansion property that every nonempty X ⊆ U_i has |N^+(X) ∩ S_i| ≥ |X|/2; a Hall-type matching lemma (Proposition 2.6) converts this into two disjoint matchings from the cut into the source components, and Lemma 2.5 routes the remaining paths of length 3. The argument closes by showing that either the remaining branch vertices have many out-neighbours outside the final subtournament (Case 2 of Claim 1) or the partial subdivision already has so many paths that the remainder can be embedded greedily.

What would settle it

Find even one infinite family of tournaments with minimum out-degree strictly above (2+o(1))$k^{2}$ that contains no subdivision of the complete digraph on k vertices; this would disprove Theorem 1.1. More concretely, one can try to build a tournament where for every balanced k-set B the dichotomy of Lemma 2.3 fails — no partial subdivision with 4(ℓ1+ℓ2)+$6k^{{7/4}}$ > m and no cut set with |S| ≥ |U|+k — which would break the iteration and show the main construction cannot work.

Watch

Extended reading notes

Core claim

The central discovery is that the threshold d(k) for forcing a subdivision of the complete digraph in a tournament is quadratic in k, specifically $k^{2}$/4 ≤ d(k) ≤ (2+o(1))$k^{2}$. The upper bound is proved by the quantitative statement that δ+(T) ≥ $2k^{2}$ + $147k^{{7/4}}$ suffices, and moreover the subdivision can be chosen so that every one of the віΔκ(k choose 2) directed paths between branch vertices has length 2 or 3. The same framework yields tight-up-to-constants vertex-number thresholds for subdivisions of the transitive tournament: $Ck^{2}$ vertices force a transitive subdivision with paths of length at most 3, and $Ck^{2}$ $log^{3}$ k vertices force a 1-subdivision. A further consequence is that every digraph with m edges and no isolated vertices admits a subdivision (with each edge subdivided at most twice) inside any tournament with minimum out-degree at least Cm.

Load-bearing premise

The argument rests on the dichotomy in Lemma 2.3: at each stage, either a partial subdivision with enough short paths has appeared, or the tournament admits a cut set whose source component is at least as large as the cut; if that dichotomy or the derived expansion property failed, the disjoint routing paths could not be assembled.

Editorial extensions

If this is right

The threshold d(k) for forcing a subdivision of the complete digraph is now known to be between k^2/4 and (2+o(1))k^2, so it is determined up to a factor of 8.
Every such subdivision can be taken with each edge replaced by a directed path of length at most 3, meaning each edge of the complete digraph is subdivided at most twice.
Any tournament on Ck^2 vertices contains a subdivision of the transitive tournament on k vertices with paths of length at most 3, and this vertex bound is tight up to a constant factor.
Any tournament on Ck^2 log^3 k vertices contains a 1-subdivision of the transitive tournament on k vertices, where every directed path has length 2.
Every digraph with m edges and no isolated vertices can be subdivided inside any tournament whose minimum out-degree is at least Cm, with each edge subdivided at most twice.

Reading between the lines

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

A natural next step, not taken in the paper, is whether the factor 8 can be removed by improving the routing claim: if the dichotomy in Lemma 2.3 can be iterated with a smaller path-counting penalty, the upper bound may approach k^2/4, matching the conjectured value in Question 4.2.
The method of Theorem 1.3 — defining an auxiliary graph whose edges mark pairs with nearly identical out-neighbourhoods and then splitting it into small components — looks transferable to other embedding problems in tournaments where one needs many disjoint length-2 paths, and might be the route to proving Conjecture 4.3 (1-subdivisions in O(k^2) vertices) by sharpening the component partition.
The general subdivision result (Theorem 4.1) suggests that for any fixed digraph D, the minimum out-degree needed to force a subdivision in a tournament is linear in the number of edges of D; if that is true for arbitrary D, then the complete digraph is essentially the worst case up to constants.

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, and a circularity audit.

Desk Editor's Note

read the letter

I read the full manuscript. The main result is a genuine improvement: it takes the threshold for containing a subdivision of the complete digraph from doubly exponential in k^2 down to (2+o(1))k^2, with a matching lower bound up to a factor of 8. The transitive tournament results (Theorem 1.2 and the 1-subdivision theorem) are new and the proofs are detailed. The lower bound by counting vertices in a regular tournament is fine. The cut-set dichotomy in Lemma 2.3 and the Hall matching argument in Lemma 2.5 are natural and mostly well executed; the expansion claim (Claim 2) is a nice minimal-cut argument.

The soft spot is in the iteration of Theorem 2.4. After building the set R of vertices with small out-degree in T_i', the proof chooses α from |T_i|, applies Lemma 2.2 to T_i, and asserts the resulting balanced k-set B_i lies in T_i'. That does not follow: Lemma 2.2 hunts for vertices of large in-degree in T_i, and a vertex in R can have arbitrarily large in-degree in T_i, so it may be selected. Even if B_i avoids R, the balance interval [m - k^{7/4}, m + k^{7/4}] was computed in T_i; deleting R removes an edge-dependent number of in-neighbours from each vertex, so the common interval need not survive in T_i'. Lemma 2.3 requires a set balanced in the tournament to which it is applied, so without these two facts the iteration has no valid input. This is not a localized typo; it is a missing justification in the core proof. The likely fix is to apply Lemma 2.2 directly to T_i' with an adjusted α, but the constants in the final inequality would then need rechecking, and that argument is not in the paper.

Separately, Lemma 3.2 says 'remove L_k' where it clearly means the small level L_{k'}; that one looks like a typo. There are also a few implicit rounding and ordering steps, but those are minor.

Bottom line: the theorem is important and probably true, and the paper deserves a serious referee who will insist on a repair of the iterative step before it is accepted. I would not rely on the proof as written.

Referee Report

3 major / 5 minor

Summary. This paper studies forced subdivisions of directed graphs in tournaments with large minimum out-degree. The main result (Theorem 1.1) states that for every k, any tournament with minimum out-degree at least (2+o(1))k^2 contains a subdivision of the complete directed graph on k vertices, and that k^2/4 is a lower bound, determining d(k) up to a factor of 8. The quantitative version (Theorem 2.4) gives the explicit threshold 2k^2+147k^(7/4) with all paths of length at most 3. The paper also proves that any tournament on O(k^2 log^3 k) vertices contains a 1-subdivision of the transitive tournament on k vertices (Theorem 1.3), and that O(k^2) vertices suffice when paths of length at most 3 are allowed (Theorem 1.2). The proofs use iterative cut arguments, balanced branch sets, and Hall-type matching lemmas.

Significance. If the proofs are correct, the paper gives the first quadratic bound for subdivisions of complete digraphs in tournaments, improving on the previous doubly-exponential bound of Girao and Snyder, and it is best possible up to a constant factor. The transitive-tournament results are also new and are tight up to logarithmic factors. The proof strategy is elegant: the main dichotomy (Lemma 2.3), the expansion property for cuts (Claim 2), and the matching lemma (Lemma 2.5) are clean and likely adaptable. However, several gaps in the write-up, detailed below, currently prevent the claims from being fully established.

major comments (3)

[Section 2, proof of Theorem 2.4] After choosing alpha so that |T_i| = 2 alpha k^2 + (20 alpha + 4) k^(7/4), the proof applies Lemma 2.2 to T_i and then asserts that the resulting (alpha,m,k)-balanced set B_i lies in V(T_i'). This is not justified: Lemma 2.2 returns a set inside the tournament to which it is applied, namely T_i, and there is no reason that this set avoids the deleted set R. Moreover, even if B_i avoided R, the balance condition is computed with respect to in-degrees in T_i; after deleting R, the in-degrees of the remaining vertices change by |N^-(v) intersect R|, which varies with v, so the common interval of length k^(7/4) need not survive in T_i'. Lemma 2.3 is then applied to T_i' with B_i, so B_i must be balanced in T_i' and must be a subset of V(T_i'). As written, Lemma 2.3 may have no valid input, and the iterative construction of the chain of subtournaments, which is the core of the proof of Theorem 2.4, collapses. A repair is likely possible by applying Lemma 2.2 directly to T_i' with a suitably adjusted alpha and verifying the constants, but this argument is absent.
[Section 3, Lemma 3.2] In the proof of Lemma 3.2, after choosing k' < 10 log^2 n with |L_{k'}| < |B_{k'-1}(x)|/(5 log n), the text says 'remove L_k from G'. This should almost certainly read 'remove L_{k\'}' (or 'remove the chosen level'). As written, the bound |S| <= n/(5 log n) on the union of removed sets does not follow, because the level L_k can have large size; the argument depends on each removed level being the small level L_{k'} whose size is bounded by |B_{k'-1}(x)|/(5 log n) <= n/(5 log n)^2. This typo affects the proof of Theorem 1.3, which relies on Lemma 3.2.
[Section 3, Lemma 3.3] The case analysis in the proof of Lemma 3.3 is incomplete and contains an unsupported assertion. The proof first checks whether |union_{i<=t'} C^1_i| >= m/4 and |union_{i>t'} C^2_i| >= m/4; if both hold, it takes X = {C_i : i<=t'} and Y = {C_i : i>t'}. If the first condition fails, the proof handles it. But the first case can fail because the second condition fails even when the first holds, and this symmetric case is not treated. Furthermore, in the middle of the construction the proof states 'by assumption we must have that |union_{j in {t'+1,...,t} excluding B} C^2_j| >= m/4', but no preceding statement implies this bound; it is exactly the kind of lower bound that needs to be proved. As a result, the lemma is not established as written, and Theorem 1.3, which depends on it, is not fully proven.

minor comments (5)

[Section 2, Lemma 2.2 and Lemma 2.3] The definition of (alpha,m,k)-balanced in Lemma 2.2 gives d^-(v) in [m-k^(7/4), m+k^(7/4)], which permits in-degrees differing by up to 2k^(7/4). The proof of Lemma 2.3 uses the stronger fact that the in-degrees of B differ by at most k^(7/4), which is true for the set produced by Lemma 2.2 because it comes from a single interval of length k^(7/4), but it is not part of the stated balanced definition. Please clarify this in the statements.
[Section 2, Lemma 2.5] In Lemma 2.5 the proof uses that S dominates T_{t+1} to conclude that |N^+(x_i) intersect U| >= 2*ell from the assumption that x_i has many out-neighbours in T outside T_{t+1}. This is only valid if x_i is in V(T_{t+1}), because otherwise x_i may have out-neighbours in S. Please state explicitly that the vertices of B lie in T_{t+1} (or that each x_i is in V(T_{t+1})).
[Section 2, Claim 1 in Theorem 2.4] The indexing in Claim 1 is confusing: if condition (1) of Lemma 2.3 fires at step i, the procedure terminates and no T_{i+1} is defined, yet the claim refers to T_{t+1}. Please clarify the indexing so that the termination case is unambiguous.
[Section 3, Theorem 1.2] The induction in the proof of Theorem 1.2 uses parameters 2k/5 and 3k/5, which are not integers. Please specify whether these are floors or ceilings, or provide a separate argument for small k.
[Section 3, Lemma 3.2] After correcting the typo, the proof that the union of the removed sets has size at most n/(5 log n) is very terse. A few sentences explaining why the removed levels have sizes that sum to the required bound would significantly improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper derives its bounds from independent combinatorial lemmas; the only self-citation is contextual and not load-bearing.

full rationale

The main results are self-contained derivations from explicit hypotheses. Theorem 1.1 is proved via the quantitative Theorem 2.4, whose proof builds on Lemma 2.2 (a pigeonhole/degree balancing lemma) and Lemma 2.3 (a dichotomy between finding a partial subdivision and finding a large source component). No parameter appearing in the conclusion is fitted to the object being predicted, and no quantity is renamed from an input. The lower bound d(k) >= k^2/4 comes from counting vertices in a random tournament, not from the upper-bound argument. The citation to Girão and Snyder [5] is used only to provide historical context that the existence question was previously resolved with a doubly exponential bound; the present proof does not invoke [5] as a premise. Similarly, other cited works (Mader, Bollobás–Thomason, Komlós–Szemerédi, Erdős–Moser, etc.) are used as background or as undirected analogues, not as inputs to the tournament subdivision argument. The paper's own equations are not used to define a target quantity in terms of itself. Although a careful reader may find an internal proof gap in the iterative step of Theorem 2.4 (e.g., ensuring the balanced set from Lemma 2.2 lies in T_i'), that is a correctness concern about missing justification, not a circularity: it does not reduce a claimed prediction to a fitted input or to a self-citation chain. Therefore the appropriate circularity score is 0.

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

The central claims rest only on standard combinatorial tools and on the paper's own lemmas. No empirical fitting parameters, new physical entities, or ad hoc postulates are introduced. The explicit constants such as 147, 150, and 10^7 are chosen to satisfy inequalities and are not free parameters in the empirical sense.

assumptions (3)

standard math Hall's marriage theorem
Used in Proposition 2.6 and Lemma 2.5 to obtain the matchings from cut sets into source components that route internally disjoint paths.
standard math Erdős-Moser theorem on transitive subtournaments
Invoked in the base case of Theorem 1.3 to ensure a sufficiently large transitive subtournament in a tournament on C k^2 log^3 k vertices.
standard math Pigeonhole principle and standard tournament degree counts
Used in Fact 2.1 and Lemma 2.2 to find branch vertex sets with balanced in-degrees, and throughout the iterative arguments.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Subdivisions of digraphs in tournaments." pith.science (2026). https://pith.science/paper/2Q5IGWZB

@misc{pith2026190803733,
  author       = {Pith},
  title        = {Pith review of: Subdivisions of digraphs in tournaments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2Q5IGWZB}},
  note         = {Machine review of arXiv:1908.03733}
}

abstract

We show that for every positive integer $k$, any tournament with minimum out-degree at least $(2+o(1))k^2$ contains a subdivision of the complete directed graph on $k$ vertices, which is best possible up to a factor of $8$. This may be viewed as a directed analogue of a theorem proved by Bollob\'as and Thomason, and independently by Koml\'os and Szemer\'edi, concerning subdivisions of cliques in graphs with sufficiently high average degree. We also consider the following problem: given $k$, what is the smallest positive integer $f(k)$ such that any $f(k)$-vertex tournament contains a $1$-subdivision of the transitive tournament on $k$ vertices? We show that $f(k)= O\left (k^2\log^3 k\right)$ which is best possible up to the logarithmic factors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

N. Alon, M. Krivelevich, and B. Sudakov, Tur´ an numbers of bipartite graphs and related Ramsey-type ques- tions, Combin. Probab. Comput. 12 (2003), 477–494

work page 2003
[2]

Bollob´ as and A

B. Bollob´ as and A. Thomason, Highly linked graphs , Combinatorica 16 (1996), no. 3, 313–320

work page 1996
[3]

Erd˝ os and A

P. Erd˝ os and A. Hajnal, On complete topological subgraphs of certain graphs , Ann. Univ. Sci. Budapest 7 (1969), 193–199

work page 1969
[4]

Erd˝ os and L

P. Erd˝ os and L. Moser, On the representation of directed graphs as unions of orderi ngs, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964), 125–132

work page 1964
[5]

Gir˜ ao and R

A. Gir˜ ao and R. Snyder, Highly linked tournaments with large minimum out-degree , J. Combin. Theory Ser. B (2019), https://doi.org/10.1016/j.jctb.2019.02.009

work page doi:10.1016/j.jctb.2019.02.009 2019
[6]

Jagger, Extremal digraph results for topological complete subgrap hs, European J

C. Jagger, Extremal digraph results for topological complete subgrap hs, European J. Combin. 19 (1998), 687– 694

work page 1998
[7]

Koml´ os and E

J. Koml´ os and E. Szemer´ edi,Topological cliques in graphs II , Combin. Probab. and Comput. 5 (1996), 79–90

work page 1996
[8]

K¨ uhn, D

D. K¨ uhn, D. Osthus, and A. Young, A note on complete subdivisions in digraphs of large outdegr ee, J. Graph Theory 57 (2008)

work page 2008

Show all 14 references

[9]

Mader, Homomorphieeigenschaften und mittlere Kantendichte von G raphen, Math

W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von G raphen, Math. Ann. 174 (1967), 265–268

1967
[10]

, Hinreichende bedingungen f¨ ur die existenz von Teilgraphe n, die zu einem vollst¨ aindigen Graphen homomorph sind , Math. Nachr. 53 (1972), 145–150

1972
[11]

Graph Theory 21 (1996), no

, On topological tournaments of order 4 in digraphs of outdegr ee 3 , J. Graph Theory 21 (1996), no. 4, 371–376

1996
[12]

Pokrovskiy, Highly linked tournaments , J

A. Pokrovskiy, Highly linked tournaments , J. Combin. Theory Ser. B 115 (2015), 339–347

2015
[13]

Scott, Subdivisions of transitive tournaments , European J

A.D. Scott, Subdivisions of transitive tournaments , European J. Combin. 21 (2000), 1067–1071

2000
[14]

Thomassen, Even cycles in directed graphs , European J

C. Thomassen, Even cycles in directed graphs , European J. Combin. 6 (1985), no. 1, 85–89

1985

Pith tools

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

[1] [1]

N. Alon, M. Krivelevich, and B. Sudakov, Tur´ an numbers of bipartite graphs and related Ramsey-type ques- tions, Combin. Probab. Comput. 12 (2003), 477–494

work page 2003

[2] [2]

Bollob´ as and A

B. Bollob´ as and A. Thomason, Highly linked graphs , Combinatorica 16 (1996), no. 3, 313–320

work page 1996

[3] [3]

Erd˝ os and A

P. Erd˝ os and A. Hajnal, On complete topological subgraphs of certain graphs , Ann. Univ. Sci. Budapest 7 (1969), 193–199

work page 1969

[4] [4]

Erd˝ os and L

P. Erd˝ os and L. Moser, On the representation of directed graphs as unions of orderi ngs, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964), 125–132

work page 1964

[5] [5]

Gir˜ ao and R

A. Gir˜ ao and R. Snyder, Highly linked tournaments with large minimum out-degree , J. Combin. Theory Ser. B (2019), https://doi.org/10.1016/j.jctb.2019.02.009

work page doi:10.1016/j.jctb.2019.02.009 2019

[6] [6]

Jagger, Extremal digraph results for topological complete subgrap hs, European J

C. Jagger, Extremal digraph results for topological complete subgrap hs, European J. Combin. 19 (1998), 687– 694

work page 1998

[7] [7]

Koml´ os and E

J. Koml´ os and E. Szemer´ edi,Topological cliques in graphs II , Combin. Probab. and Comput. 5 (1996), 79–90

work page 1996

[8] [8]

K¨ uhn, D

D. K¨ uhn, D. Osthus, and A. Young, A note on complete subdivisions in digraphs of large outdegr ee, J. Graph Theory 57 (2008)

work page 2008