{"id":"638c5a76-4b65-4005-9daf-95605aead79e","arxiv_id":"2411.13483","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"If a digraph has no oriented 4-cycles, minimum semidegree at least k/2, and at least one vertex with outdegree and indegree at least k, then it contains every oriented tree with k arcs.","lead":"Mathematicians proved a precise condition under which a large digraph with no small cycle-like patterns is guaranteed to contain every oriented tree of a given size. The result is a directed analogue of a known theorem for ordinary graphs and settles a special case of a 2013 conjecture about antidirected trees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's verdict is CONDITIONAL, and I agree that the paper should be accepted only after the abbreviated secondary proofs are filled in. However, the reader's weakest_assumption points to Eq. (7) and the pruning sequence, and on close inspection that step is true by a standard reduced-tree argument; it is an omitted justification rather than a correctness risk. The main counting argument of Theorem 1 also survives scrutiny: the claims about disjoint embedding, the small-neighbourhood obstruction, and the uniqueness of membership in the N_a sets are all consequences of the C4-free condition as stated. Thus the central result (Theorem 1 and Corollary 2) appears sound. The one genuine concern is Theorem 4, where the oriented case departs from the Theorem 1 proof and several crucial claims are delegated to 'straightforward to verify'. Since the abstract advertises an improvement for arborescences, this is a completeness issue worth fixing, but it does not change the assessment of the central claim. I therefore recommend keeping the verdict unchanged rather than moving it.","tokens_in":12625,"tokens_out":46752,"duration_ms":483875,"concrete_test":"Write out a complete verification of the 'straightforward' steps in the oriented case of Proposition 5, especially statements (15)-(19) and the q=2 exclusion; if any claimed C4-free contradiction does not go through, Theorem 4's improvement needs correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified for the central claim. I re-read the proof of Theorem 1 and the implicit steps flagged by the reader hold. The degree bound at Eq. (7) is true: if every penultimate vertex of a diameter-5 tree had degree at least k/2, two leaves of the reduced tree would need at least k-2 pendant leaves, leaving too few edges for the reduced tree to have diameter three. The earlier assertion that any already embedded z with f(z) in N(f(u)) is either w or a neighbour of w is also justified: a vertex at distance two from w together with u and w would form an oriented 4-cycle. The disjoint-embedding obstruction before Eq. (3) is sound because if both unused out- and in-neighbourhoods had size at least du, the union would have size at least du, making disjoint choices possible. Inequality (5) is valid: any common neighbour of two different N_a would create a non-directed 4-cycle, so each vertex is counted at most once. The only real weakness is that Theorem 4's oriented case is abbreviated, with 'straightforward to verify' passages covering statements (15)-(19) and the exclusion of q=2. This does not undermine Corollary 2, but it leaves the advertised arborescence improvement less secure than the main theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":12802,"tokens_out":7983,"duration_ms":86555,"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":[{"comment":"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.","section":"§3, Eq. (7)"},{"comment":"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.","section":"§5, Proposition 5, oriented case"}],"minor_comments":[{"comment":"The phrase \"or a a different family\" appears to contain a typo; it should presumably read \"or a different family.\"","section":"§1, last paragraph"},{"comment":"The text \"Th is means that for all a ∈ Q\" should read \"This means that for all a ∈ Q.\"","section":"§3, after Eq. (3)"},{"comment":"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.","section":"§3, displayed equation (5) and following paragraph"},{"comment":"The entries contain LaTeX artifacts \"/suppress\" (e.g., \"T. /suppress Luczak\") that should be removed before publication.","section":"References [6] and [8]"}],"recommendation":"major_revision","confidential_remarks":"The central theorem (Theorem 1 / Corollary 2) appears sound and the proof strategy is convincing, but the version of Theorem 4 in the manuscript leaves essential verification steps to the reader. If the authors supply the missing details for the oriented case of Proposition 5 and expand the justification of Eq. (7), the paper would be suitable for publication. The paper otherwise reads as a solid contribution to extremal digraph theory."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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).\n\nSoft 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.\n\nCitation 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.\n\nWho 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.\n\nRecommendation: 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.","headline":"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.","tokens_in":13378,"tokens_out":2297,"would_cite":true,"duration_ms":20397,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C05","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["oriented trees","digraph embedding","4-cycle-free digraphs","minimum semidegree","antidirected trees","arborescences","Erdős–Sós conjecture"],"falsifier":"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.","tokens_in":12393,"feed_emoji":"🌳","tokens_out":4702,"duration_ms":47241,"temperature":0.7,"pith_summary":"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.","feed_headline":"C4-free digraphs contain every oriented tree at semidegree k/2","feed_subtitle":"Forbidding all oriented 4-cycles makes degree k/2 plus max degree k sufficient.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the undirected C4-free tree-embedding result whose ideas the proof extends to digraphs.","marker":"[14]"},{"why":"Provides the girth-five graph result that motivates the degree conditions used here.","marker":"[3]"},{"why":"States the conjecture on antidirected trees in dense digraphs that Theorem 3 and Corollary 7 address in a special case.","marker":"[1]"},{"why":"Supplies Lemma 9, used to pass from arc density to minimum pseudo-semidegree in the proof of Corollary 7.","marker":"[10]"},{"why":"Prior work by the same authors on antidirected trees in dense digraphs, whose special cases are compared with Corollary 7.","marker":"[19]"}],"fun_headline_variants":["Semidegree k/2, no oriented C4: all k-arc trees embed","No oriented 4-cycles, semidegree k/2 -> all k-arc trees","Half semidegree and no oriented C4 embed every k-arc tree","Forbidding oriented C4: semidegree k/2 embeds all k-arc oriented trees","Avoid oriented C4, get every k-arc tree at semidegree k/2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Semidegree k/2, no oriented C4: all k-arc trees embed","No oriented 4-cycles, semidegree k/2 -> all k-arc trees","Half semidegree and no oriented C4 embed every k-arc tree","Forbidding oriented C4: semidegree k/2 embeds all k-arc oriented trees","Avoid oriented C4, get every k-arc tree at semidegree k/2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001502,"raw_usage":{"total_tokens":5945,"prompt_tokens":787,"completion_tokens":5158,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":403,"completion_tokens_details":{"reasoning_tokens":5041}},"tokens_in":403,"tokens_out":5158,"duration_ms":34076,"temperature":1.0,"reasoning_tokens":5041,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:21:34.212823+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Sacl´ e and M","cited_arxiv_id":null,"evidence_quote":"Supplies the undirected C4-free tree-embedding result whose ideas the proof extends to digraphs."},{"cited_title":"Brandt and E","cited_arxiv_id":null,"evidence_quote":"Provides the girth-five graph result that motivates the degree conditions used here."},{"cited_title":"Addario-Berry, F","cited_arxiv_id":null,"evidence_quote":"States the conjecture on antidirected trees in dense digraphs that Theorem 3 and Corollary 7 address in a special case."},{"cited_title":"Klimoˇ sov´ a and M","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 9, used to pass from arc density to minimum pseudo-semidegree in the proof of Corollary 7."},{"cited_title":"Antidirected trees in dense digraphs","cited_arxiv_id":"2404.10750","evidence_quote":"Prior work by the same authors on antidirected trees in dense digraphs, whose special cases are compared with Corollary 7."}],"review_version":1}