{"id":"2c277d21-f07b-4e5b-8563-19b97c2bc886","arxiv_id":"1908.03733","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every tournament with minimum out-degree (2+o(1))k^2 contains a subdivision of the complete digraph on k vertices, and every tournament on C k^2 log^3 k vertices contains a 1-subdivision of the transitive tournament on k vertices.","lead":"This paper proves that any tournament whose vertices all have out-degree about 2k^2 contains a subdivision of the complete directed graph on k vertices, and that this bound is tight up to a factor of 8. It also gives nearly tight bounds for embedding subdivisions of transitive tournaments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.4's iteration never proves the balanced k-set lies in T_i' or stays balanced after deleting R, so Lemma 2.3 may have no valid input.","rationale":"I read the full paper and the reader's verdict. The central theorem is the quadratic upper bound for subdivisions of complete digraphs, and the reader's weakest assumption points at Lemma 2.3's dichotomy and the expansion property. My stress-test found the more fundamental weak spot one step earlier: in the iteration, the balanced branch set B_i is produced by Lemma 2.2 applied to T_i, but Lemma 2.3 is applied to T_i'. The proof does not show that B_i is contained in T_i', nor that the in-degree interval property is preserved after deleting R. This is load-bearing because every iteration of the main construction depends on it. I have not found circularity, parameter fitting, or independent-support problems: the lower bound via random tournaments is sound, the overall strategy is coherent, and the theorem is likely repairable. The Lemma 3.2 issue flagged by the reader (removing L_k instead of the small level L_{k'}) is also real and should be fixed, but it affects Theorem 1.3 and is secondary to the main claim. Because the concern I identify is a missing sub-lemma rather than a demonstrated false statement, the appropriate verdict remains CONDITIONAL, matching the reader's verdict; I do not see grounds to accept or reject outright.","tokens_in":89,"tokens_out":38453,"duration_ms":446113,"concrete_test":"Prove or disprove the corrected sub-lemma: for every admissible k and r=|R|<k with δ+(T_i \\ R) ≥ k^2 + 12k^{7/4}, the tournament T_i \\ R contains k vertices whose in-degrees in T_i \\ R all lie in a common interval of length k^{7/4} and are at least α' k^2 + 2k^{7/4}, where α' is defined by |T_i \\ R| = 2α' k^2 + (20α' + 4)k^{7/4}. Then re-derive the final inequalities of Theorem 2.4 with α' in place of α, in particular α' ≤ 7 and d+_{T_{t+1}}(v) ≤ m + 141k^{7/4}. If this adjusted lemma holds for all admissible k and r, the proof can be repaired by a short explicit amendment; if it fails, the iterative construction in Theorem 2.4 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in the iterative step of Theorem 2.4. After deleting the set R of vertices with d+_{T_i'}(v) < k^2 + 12k^{7/4} from T_i, the proof chooses α by |T_i| = 2αk^2 + (20α+4)k^{7/4}, applies Lemma 2.2 to T_i, and asserts that the resulting (α,m,k)-balanced k-set B_i lies in V(T_i'). Two unsupported facts are needed. First, Lemma 2.2 only controls in-degrees in T_i; the deleted vertices, having small out-degree in T_i', can have very large in-degree in T_i, so they may be selected into B_i. If B_i meets R, Lemma 2.3 cannot be applied to T_i'. Second, even if B_i is disjoint from R, the balance condition was computed in T_i, not in T_i'. Deleting R removes |N^-(v) ∩ R| in-neighbours from each v, and this quantity varies with v, so the common interval of length k^{7/4} need not survive. Lemma 2.3 is then applied to T_i' and requires B to be balanced in that tournament; without these two facts the dichotomy and the expansion property of Claim 2 have no guaranteed starting set. This is a genuine missing justification in the main proof, not a localized typo. The likely repair is to apply Lemma 2.2 directly to T_i' with a suitably adjusted α, but that argument and the resulting constant checks are absent from the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1933,"tokens_out":6313,"duration_ms":409146,"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":[{"comment":"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":"Section 2, proof of Theorem 2.4"},{"comment":"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":"Section 3, Lemma 3.2"},{"comment":"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.","section":"Section 3, Lemma 3.3"}],"minor_comments":[{"comment":"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":"Section 2, Lemma 2.2 and Lemma 2.3"},{"comment":"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":"Section 2, Lemma 2.5"},{"comment":"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":"Section 2, Claim 1 in Theorem 2.4"},{"comment":"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":"Section 3, Theorem 1.2"},{"comment":"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.","section":"Section 3, Lemma 3.2"}],"recommendation":"major_revision","confidential_remarks":"This is a promising paper with a likely correct main result, but the proofs as written contain load-bearing gaps that need to be repaired. The balance issue in the proof of Theorem 2.4 is the most serious; if the authors can fix it, the paper would be a strong contribution. The problems with Lemmas 3.2 and 3.3 also need attention, but they appear to be more local in nature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nSeparately, 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.\n\nBottom 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.","headline":"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.","tokens_in":15775,"tokens_out":7819,"would_cite":true,"duration_ms":72271,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["tournaments","subdivisions","complete digraph","minimum out-degree","transitive tournament","1-subdivision","extremal graph theory","directed graphs"],"falsifier":"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.","tokens_in":14633,"feed_emoji":"","tokens_out":7435,"duration_ms":64033,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quadratic out-degree forces full subdivisions in tournaments","feed_subtitle":"Any tournament whose every vertex has out-degree at least ~2k^2 contains a subdivided complete digraph on k vertices—tight up to a factor…","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"the previous existence result for subdivisions of complete digraphs in tournaments, which this paper improves from a doubly exponential bound to a quadratic one","marker":"[5]"},{"why":"one of the two independent proofs of the undirected theorem that average degree ck^2 forces a clique subdivision, the analogue being transferred to tournaments","marker":"[2]"},{"why":"the other independent proof of the undirected clique-subdivision theorem, supplying the benchmark quadratic bound","marker":"[7]"},{"why":"shows minimum out-degree alone does not force subdivisions in general digraphs, motivating the restriction to tournaments","marker":"[14]"},{"why":"gives the best general-digraph subdivision bound, the context that the tournament-specific quadratic result improves","marker":"[8]"},{"why":"provides the bound on the size of a transitive subtournament used to initialize the induction in Theorem 1.2","marker":"[4]"},{"why":"the undirected 1-subdivision result that Theorem 1.3 is a partial directed analogue of","marker":"[1]"}],"fun_headline_variants":["Quadratic out-degree forces complete digraph subdivisions","Tournaments: quadratic out-degree yields all subdivisions","2k^2 out-degree forces a complete digraph subdivision","Quadratic out-degree threshold for tournament subdivisions","Transitive subdivisions in tournaments need near-quadratic vertices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic out-degree forces complete digraph subdivisions","Tournaments: quadratic out-degree yields all subdivisions","2k^2 out-degree forces a complete digraph subdivision","Quadratic out-degree threshold for tournament subdivisions","Transitive subdivisions in tournaments need near-quadratic vertices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001096,"raw_usage":{"total_tokens":4552,"prompt_tokens":899,"completion_tokens":3653,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":3578}},"tokens_in":515,"tokens_out":3653,"duration_ms":28270,"temperature":1.0,"reasoning_tokens":3578,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:04:28.796003+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Gir˜ ao and R","cited_arxiv_id":null,"evidence_quote":"the previous existence result for subdivisions of complete digraphs in tournaments, which this paper improves from a doubly exponential bound to a quadratic one"},{"cited_title":"Bollob´ as and A","cited_arxiv_id":null,"evidence_quote":"one of the two independent proofs of the undirected theorem that average degree ck^2 forces a clique subdivision, the analogue being transferred to tournaments"},{"cited_title":"Koml´ os and E","cited_arxiv_id":null,"evidence_quote":"the other independent proof of the undirected clique-subdivision theorem, supplying the benchmark quadratic bound"},{"cited_title":"Thomassen, Even cycles in directed graphs , European J","cited_arxiv_id":null,"evidence_quote":"shows minimum out-degree alone does not force subdivisions in general digraphs, motivating the restriction to tournaments"},{"cited_title":"K¨ uhn, D","cited_arxiv_id":null,"evidence_quote":"gives the best general-digraph subdivision bound, the context that the tournament-specific quadratic result improves"},{"cited_title":"Erd˝ os and L","cited_arxiv_id":null,"evidence_quote":"provides the bound on the size of a transitive subtournament used to initialize the induction in Theorem 1.2"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"the undirected 1-subdivision result that Theorem 1.3 is a partial directed analogue of"}],"review_version":1}