{"id":"0a9aba94-5334-4777-8de7-52313d83067f","arxiv_id":"2501.11726","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A digraph with minimum semidegree above ℓ/(2ℓ−1) times the tree size and with vertices of large out- and indegree contains every balanced antidirected bounded-degree tree of that size.","lead":"This paper proves new minimum and maximum degree conditions under which any large directed graph is guaranteed to contain every large balanced antidirected tree of bounded degree. It extends recent tree-embedding theorems from undirected graphs and oriented graphs to general digraphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.2(a) Step 3 asserts |V(C)| ≥ 2(1/2+γ)k_R without justification; a bidirected clique of size (1+γ)k_R satisfies the degree hypotheses but admits no antimatching of size (1/2+γ)k_R, so the proof as written has a genuine gap.","rationale":"The reader's weakest assumption correctly identifies the most serious gap in the proof of the central theorem: Lemma 5.2(a) requires an antimatching of size (1/2+γ)k_R, but the asserted lower bound on |V(C)| does not follow from the stated hypotheses and is in fact false, as the bidirected clique example shows. This is not a mere technicality: the antimatching is the backbone of the embedding argument, and without it the proof of Theorem 1.5 cannot proceed. I checked whether Lemma 4.2(ii) could supply the missing bound; it cannot, because δ+(B) is generally positive and the inequality only gives |V(C)| + δ+(B) ≥ 2δ0(R). I also considered the possibility that the component size assumption |C| ≥ (1+γ)k_R might implicitly force B to be empty; it does not, since the bidirected clique on (1+γ)k_R clusters satisfies all degree assumptions. The proposed repair of taking t about |C|/2 appears viable: for balanced antidirected trees the total number of sources and sinks is about k/2, and |C|/2 ≥ (1+γ)k_R/2, which still leaves enough capacity in the regular pairs to host the pieces. The constants in Lemma 3.4 and in the final embedding step would need to be rechecked, but no fundamental obstacle is apparent. The paper contains a genuine new result and the overall strategy is sound, so a conditional acceptance with a request to fix Lemma 5.2(a) remains the appropriate verdict. I am not raising objections about the authors' integrity or the novelty of the work; the concern is purely about a specific unproved estimate in the proof.","tokens_in":15201,"tokens_out":16288,"duration_ms":146862,"concrete_test":"Re-derive Step 3 of Lemma 5.2(a) with t = floor(|V(C)|/2) instead of t = (1/2+γ)k_R. Check whether Lemma 3.4 conditions (a)–(c) hold for a balanced antidirected tree T: in particular, condition (c) requires max(∑p, ∑q) ≈ k/2 < (1−10√ε) s t, which becomes k/2 < (1−10√ε) s · |V(C)|/2 ≈ (1−10√ε)(1+γ)k/2. If this inequality holds for the given ε, γ, then the repair works and the proof can be fixed; if it fails for some allowed parameter regime, a different construction of the antimatching is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 5.2(a), Step 3, the proof claims that because δ0(R) ≥ (1/2+γ)k_R, the anticonnected component C satisfies |V(C)| ≥ 2(1/2+γ)k_R, and then applies Lemma 4.3 with t = (1/2+γ)k_R to obtain an antimatching of size t. This implication is not proved and is false: Lemma 4.2 only gives min{|Out(C)|, |In(C)|} ≥ δ0(R) and δ+(B) ≥ 2δ0(R) − |V(C)|, where B = In(C) ∩ Out(C). The latter inequality yields |V(C)| + δ+(B) ≥ 2δ0(R), not |V(C)| ≥ 2δ0(R). A concrete counterexample is a bidirected clique on m = ⌊(1+γ)k_R⌋ clusters: it is anticonnected, δ0(R) = m−1 ≥ (1/2+γ)k_R for k_R large, and |V(C)| = m ≈ (1+γ)k_R < 2(1/2+γ)k_R. In this component every vertex lies in In(C) ∩ Out(C), so δ+(B) is large and Lemma 4.2(ii) is satisfied, yet the underlying graph has matching number at most m/2 ≈ (1+γ)/2 k_R < (1/2+γ)k_R. Thus no antimatching of the required size exists. This is load-bearing because the antimatching is the structure into which the pieces of T are partitioned and embedded via Lemma 3.4 and Lemma 5.1; without it, the embedding of the whole tree cannot be completed. The gap appears repairable by choosing t = floor(|V(C)|/2), which is at least about (1+γ)/2 k_R and still large enough to accommodate the roughly k/2 sources and sinks of a balanced antidirected tree, provided the constants in Lemma 3.4 are adjusted. However, the written proof as it stands is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a directed analogue of the Komlós-Sárközy-Szemerédi tree-embedding theorem for smaller bounded-degree balanced antidirected trees. Theorem 1.5 asserts that for every γ>0, c∈R, ℓ≥2, any sufficiently large digraph D with minimum semidegree δ0(D) ≥ (ℓ/(2ℓ−1)+γ)k and with some vertex of outdegree and some vertex of indegree at least (1+γ)(ℓ−1)k contains every balanced antidirected tree T with k arcs and maximum total degree at most (log n)^c, for all k ≥ γn. The proof combines the directed regularity lemma, tree-decomposition lemmas (Lemmas 3.2 and 3.3), a partitioning lemma (Lemma 3.4), and a matching lemma for anticonnected components (Lemma 4.3). The main embedding step (Lemma 5.2) first finds a large antimatching in a large anticonnected component of the reduced digraph and then embeds the tree pieces into the corresponding regular pairs, with connections established via antiwalks in the reduced digraph. The final section uses a vertex of large outdegree to split the tree into ℓ forests and embeds each forest into one of ℓ anticonnected components seen by that vertex, yielding the theorem.","tokens_in":15673,"tokens_out":9536,"duration_ms":88827,"significance":"If the proof is completed, the result is a significant extension of the KSS framework to digraphs for a natural class of oriented trees. The degree bounds are shown to be essentially best possible in several regimes via existing examples, and the corollaries (Corollaries 1.2 and 1.3) give clean, interpretable statements that relate to known graph and oriented-graph results. The proof is built entirely from published regularity and embedding lemmas, and it contains no fitted parameters, which makes the overall structure transparent. The paper also quickly reproduces a recent result on antidirected trees in oriented graphs (Corollary 5.3), demonstrating the reach of the method.","major_comments":[{"comment":"The proof asserts |V(C)| ≥ 2(1/2+γ)k_R and then invokes Lemma 4.3 with t = (1/2+γ)k_R. This inequality does not follow from the preceding degree condition. Lemma 4.2(i) gives min{|Out(C)|, |In(C)|} ≥ δ0(R) ≥ (1/2+γ)k_R, but Out(C) and In(C) need not be disjoint, so |V(C)| ≥ 2(1/2+γ)k_R can fail. For example, a bidirected clique on m = ⌊(1+γ)k_R⌋ clusters is anticonnected and satisfies δ0(R) = m−1 ≥ (1/2+γ)k_R, yet |V(C)| = m < (1+2γ)k_R; since every vertex lies in Out(C) ∩ In(C), the underlying graph has matching number at most ⌊m/2⌋ < (1/2+γ)k_R, so no antimatching of the required size exists. This gap is load-bearing because the antimatching is the structure into which the pieces of T are partitioned via Lemma 3.4 and then embedded via Lemma 5.1. A repair appears feasible by taking t = ⌊|V(C)|/2⌋, which is at least about ((1+γ)/2)k_R and still large enough to meet the capacity condition max{∑p, ∑q} < (1−10√ε)st in Lemma 3.4 after adjusting the constants; the authors should supply a written proof of this modified step.","section":"Lemma 5.2(a), Step 3 (also used in Corollary 5.3 and Theorem 1.5)"}],"minor_comments":[{"comment":"The minimum semidegree is denoted δ^0(D) in the abstract and δ0(D) in the main text and Theorem 1.5; please unify the notation.","section":"Abstract and Section 3.1"},{"comment":"The example of two anticonnected components intersecting at a single vertex refers to a figure that is missing from the text; include the figure in the final version.","section":"Section 2.1"},{"comment":"The proof of the claim 'So C has the desired size' is very terse; expanding the inequality that uses the orientedness of D to show the component is large would improve readability.","section":"Corollary 5.3"},{"comment":"The inequality verification ends with 'as the reader can check'; a short derivation of that elementary inequality would make the paper more self-contained.","section":"Section 6, around equation (11)"}],"recommendation":"major_revision","confidential_remarks":"The gap in Lemma 5.2(a) Step 3 is local and appears repairable without changing the overall proof strategy, so I recommend major revision rather than rejection. Once the antimatching argument is corrected, the paper should be a solid contribution to the extremal theory of directed trees. I would also ask the authors to verify that the same issue does not affect the application of Lemma 4.3 in the oriented-graph corollary, even though the orientedness may rule out the problematic bidirected example."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nHere's my read on the Kontogeorgiou–Santos–Stein paper.\n\nThe short version: this is a real result, and the high-level argument is sound, but there's a genuine gap in Lemma 5.2(a) that needs to be fixed before the proof is complete. The gap is not fatal—it looks patchable—but as written, the proof is incomplete.\n\nWhat's new: the theorem extends the KSS embedding theorem to digraphs for balanced bounded-degree antidirected trees of size proportional to n, with combined min- and max-degree conditions. This is not a routine translation, because digraphs admit 2-cycles, which break the oriented-graph arguments from Stein–Zárate-Guerén. The anticonnected-components machinery is a sensible way to handle that. The bounds match the essentially best-possible bounds from the undirected and oriented settings, and the result asymptotically resolves Problem 6.13 for this class. The paper is clearly written, and the reliance on external lemmas is honest; no circularity concern.\n\nThe soft spot is real. In Lemma 5.2(a), Step 3, the proof needs an antimatching of size (1/2+γ)k_R and asserts |V(C)| ≥ 2(1/2+γ)k_R to apply Lemma 4.3. That inequality is not proved and is false: a bidirected clique on (1+γ)k_R clusters satisfies the degree hypotheses but has |V(C)| ≤ (1+γ)k_R < (1+2γ)k_R, so no antimatching of that size exists. This is load-bearing, since the antimatching carries the pieces of the tree.\n\nBut the repair is straightforward. Take t = (1/2+γ/2)k_R. Then |V(C)| ≥ (1+γ)k_R ≥ 2t, and δ0(R) ≥ (1/2+γ)k_R ≥ t, so Lemma 4.3 applies. The antimatching is still larger than k/2, which is all the embedding needs. The constants in Lemma 3.4 need a small adjustment, but nothing structural changes. I also noticed a few typos, e.g., a garbled inequality in Lemma 4.2(ii) and an undefined m in Lemma 3.4; those are minor.\n\nBottom line: this paper is for the extremal graph theory crowd—anyone working on tree embeddings or the regularity method will want to know it. It deserves a serious referee. I'd send it to review, asking the authors to fix Lemma 5.2(a) before acceptance. If the repair checks out, it's a solid addition to the literature.","headline":"A genuine new result with a real but repairable gap in Lemma 5.2(a); worth sending to peer review.","tokens_in":16203,"tokens_out":9101,"would_cite":true,"duration_ms":79982,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C07","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"A dense digraph with one vertex of very large out-degree and one of very large in-degree contains every bounded-degree balanced antidirected tree of comparable size.","keywords":["tree embedding","directed graphs","antidirected trees","balanced trees","minimum semidegree","regularity lemma","anticonnected components","KSS theorem"],"falsifier":"Inspect Step 3 of Lemma 5.2(a): take $C$ to be a bidirected clique on $(1+\\gamma)k_R$ clusters in the reduced digraph, so $|V(C)|=(1+\\gamma)k_R < 2\\left(\\frac12+\\gamma\\right)k_R$, and check whether an antimatching of size $\\left(\\frac12+\\gamma\\right)k_R$ still exists; if $C$ can arise as an anticonnected component of a digraph meeting the theorem's degree bounds, the proof's key estimate fails and the argument must be repaired.","tokens_in":15002,"feed_emoji":"🌳","tokens_out":18588,"duration_ms":161498,"temperature":0.7,"pith_summary":"This paper proves a directed analogue of recent smaller-tree versions of the classical spanning-tree theorem for dense graphs (the KSS theorem). It shows that if a large digraph $D$ has minimum semidegree at least $\\left(\\frac{\\ell}{2\\ell-1}+\\gamma\\right)k$ and has a vertex of outdegree and a vertex of indegree at least $(1+\\gamma)(\\ell-1)k$, then $D$ contains every balanced antidirected tree with $k$ arcs and bounded maximum degree, for $k \\geq \\gamma n$. Setting $\\ell=3$ yields the clean statement that minimum semidegree above $3k/5$ plus vertices of outdegree and indegree above $2k$ forces every such tree; setting $\\ell=2$ yields semidegree above $2k/3$ with maximum degree above $k$. These thresholds mirror the asymptotically best possible bounds known for undirected graphs, so the result transfers the shape of the KSS theorem to directed hosts for a natural class of trees.","feed_headline":"Balanced antidirected trees appear in dense digraphs with a high-degree vertex","feed_subtitle":"A semidegree bound plus one large out- and in-degree guarantees every bounded-degree balanced antidirected k-arc tree.","key_machinery":"The argument runs through the digraph regularity lemma, compressing the host $D-u$ into a reduced digraph $R$ whose vertices are regular clusters. The embedding is governed by the anticonnected components of $R$: maximal subdigraphs in which any two vertices are joined by an antiwalk, a walk whose arcs alternate direction. The load-bearing objects are anticonnected matchings, or antimatchings, disjoint arcs of $R$ that can be connected by antiwalks; Lemma 4.3 produces a large antimatching in any large anticonnected component under the semidegree bound, and Lemma 5.2 embeds a bounded-degree antidirected forest into the regular pairs corresponding to such an antimatching, using short connecting paths between arcs. The theorem then chooses a vertex $u$ of maximum outdegree, cuts the target tree at a vertex $z$ whose removal splits it into $\\ell$ forests of controlled sizes, and embeds $z$ at $u$ while distributing the forests among $\\ell$ anticonnected components of $R$ that $u$ sees with high degree. The degree-form diregularity lemma for digraphs transfers the original degree assumptions into this reduced setting.","core_discovery":"The paper's central claim is Theorem 1.5: for every $\\gamma>0$, $c\\in\\mathbb{R}$, and $\\ell\\in\\mathbb{N}$ with $\\ell\\geq 2$, there exists $n_0$ such that for every $n\\geq n_0$ and $k\\geq \\gamma n$, every digraph $D$ on $n$ vertices with $\\delta^0(D) \\geq \\left(\\frac{\\ell}{2\\ell-1}+\\gamma\\right)k$ and $\\Delta(D) \\geq (1+\\gamma)(\\ell-1)k$ contains every balanced antidirected tree $T$ with $k$ arcs and $\\Delta(T) \\leq (\\log n)^c$. Here $\\delta^0(D)$ is the minimum semidegree, the smaller of a vertex's in- and out-degree, and $\\Delta(D)$ is the largest $m$ such that $D$ has a vertex of outdegree at least $m$ and a vertex of indegree at least $m$. A balanced antidirected tree is an oriented tree in which every vertex is a source or a sink, so directions alternate along every path, and the numbers of sources and sinks are equal. The theorem is a smaller-tree version of the directed analogue of the KSS theorem, and it asymptotically reproduces the known optimal degree thresholds from the graph setting.","pith_inferences":["The proof's component-by-component strategy suggests the result may extend to oriented trees that are not necessarily balanced, if the size condition on the anticonnected components can be adjusted to match the two colour classes of the tree.","Because the extremal graph examples that force the semidegree threshold use bidirected complete bipartite structures, the true threshold for the $\\ell=3$ case may be close to $k/2$ rather than $3k/5$; the paper leaves this open.","A testable refinement would be to replace the maximum-degree bound $k/\\varepsilon$ in the asymptotic corollary by a constant multiple $Ck$, checking whether the component-counting argument still yields $\\ell$ usable components.","The embedding lemma is stated for bounded-degree trees with $\\Delta(T)\\leq (\\log n)^c$, but the same anticonnected-matching framework would likely tolerate slightly larger degrees if the connecting antiwalks can be kept short."],"forward_implications":["With $\\ell=3$, every large digraph with minimum semidegree at least $(1+\\gamma)3k/5$ and vertices of outdegree and indegree at least $2(1+\\gamma)k$ contains every balanced antidirected tree with $k$ arcs and bounded degree.","With $\\ell=2$, minimum semidegree at least $(1+\\gamma)2k/3$ plus maximum degree at least $(1+\\gamma)k$ suffices, and the semidegree bound cannot be improved because the analogous graph example blocks any weaker threshold.","Sending $\\ell$ to infinity gives an asymptotic digraph version of the Hyde--Reed theorem: for every $\\varepsilon>0$, minimum semidegree above $(1+\\varepsilon)k/2$ plus maximum degree at least $k/\\varepsilon$ forces every such tree.","The result asymptotically solves, for balanced antidirected bounded-degree trees, a problem about oriented trees in digraphs that was open in this generality.","The same machinery reproves the earlier oriented-graph theorem that minimum semidegree above $(1+\\gamma)k/2$ suffices for balanced antidirected bounded-degree trees."],"supporting_citations":[{"why":"Supplies the degree-form diregularity lemma for digraphs, which produces the reduced digraph $R$ used throughout the proof.","marker":"[1]"},{"why":"Provides the degree-condition template and tree-decomposition method for embedding smaller bounded-degree trees in graphs, which the paper adapts to digraphs.","marker":"[2]"},{"why":"Supplies the tree-cutting lemma (Lemma 3.1) that locates the vertex $z$ whose removal balances the components, and the conjecture behind the semidegree threshold.","marker":"[3]"},{"why":"Establishes the digraph version of the KSS theorem for spanning trees, the result that the present theorem extends to smaller trees.","marker":"[5]"},{"why":"Is the original KSS spanning-tree theorem whose minimum-degree threshold and bounded-degree condition the paper mirrors.","marker":"[7]"},{"why":"Provides the fact on typical vertices in regular pairs (Fact 3.5) used when embedding tree vertices into the regular clusters.","marker":"[8]"},{"why":"Supplies the antiwalk embedding lemma (Lemma 5.1) and the oriented-graph antecedent that is reproved as Corollary 5.3.","marker":"[14]"}],"fun_headline_variants":["Dense digraphs with a large out and in vertex contain every balanced antidirected tree","High semidegree plus one large out and one large in forces all antidirected trees","Semidegree bound plus a large out/in vertex guarantees balanced antidirected trees","Large out and in degrees plus semidegree force balanced antidirected trees","Semidegree plus one large out and one large in yields all balanced antidirected trees"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof needs every anticonnected component $C$ of the reduced digraph to contain at least $2\\left(\\frac12+\\gamma\\right)k_R$ vertices, so that Lemma 4.3 yields an antimatching of size $\\left(\\frac12+\\gamma\\right)k_R$; this bound is asserted without proof and is false for a bidirected clique on $(1+\\gamma)k_R$ clusters, which satisfies the degree hypotheses.","fun_headline_variants_meta":{"raw":{"variants":["Dense digraphs with a large out and in vertex contain every balanced antidirected tree","High semidegree plus one large out and one large in forces all antidirected trees","Semidegree bound plus a large out/in vertex guarantees balanced antidirected trees","Large out and in degrees plus semidegree force balanced antidirected trees","Semidegree plus one large out and one large in yields all balanced antidirected trees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002411,"raw_usage":{"total_tokens":9341,"prompt_tokens":1087,"completion_tokens":8254,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":703,"completion_tokens_details":{"reasoning_tokens":8147}},"tokens_in":703,"tokens_out":8254,"duration_ms":59173,"temperature":1.0,"reasoning_tokens":8147,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:57:40.539127+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect Step 3 of Lemma 5.2(a): take $C$ to be a bidirected clique on $(1+\\gamma)k_R$ clusters in the reduced digraph, so $|V(C)|=(1+\\gamma)k_R < 2\\left(\\frac12+\\gamma\\right)k_R$, and check whether an antimatching of size $\\left(\\frac12+\\gamma\\right)k_R$ still exists; if $C$ can arise as an anticonnected component of a digraph meeting the theorem's degree bounds, the proof's key estimate fails and the argument must be repaired.","supporting_citations":[{"cited_title":"Testing subgraphs in directed graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the degree-form diregularity lemma for digraphs, which produces the reduced digraph $R$ used throughout the proof."},{"cited_title":"Degree conditions for embedding trees.SIAM Journal on Discrete Mathematics, 33(3):1521–1555, 2019","cited_arxiv_id":null,"evidence_quote":"Provides the degree-condition template and tree-decomposition method for embedding smaller bounded-degree trees in graphs, which the paper adapts to digraphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the tree-cutting lemma (Lemma 3.1) that locates the vertex $z$ whose removal balances the components, and the conjecture behind the semidegree threshold."},{"cited_title":"Spanning trees in dense directed graphs.Journal of Com- binatorial Theory, Series B, 156:223–249, 2022","cited_arxiv_id":null,"evidence_quote":"Establishes the digraph version of the KSS theorem for spanning trees, the result that the present theorem extends to smaller trees."},{"cited_title":"Sárközy, and Endre Szemerédi","cited_arxiv_id":null,"evidence_quote":"Is the original KSS spanning-tree theorem whose minimum-degree threshold and bounded-degree condition the paper mirrors."},{"cited_title":"The regularity lemma and its applications in graph theory.Summer school on theoretical aspects of computer science, pages 84–112, 2000","cited_arxiv_id":null,"evidence_quote":"Provides the fact on typical vertices in regular pairs (Fact 3.5) used when embedding tree vertices into the regular clusters."},{"cited_title":"Antidirected subgraphs of oriented graphs.Combinatorics, Proba- bility and Computing, 33(4):446–466, 2024","cited_arxiv_id":null,"evidence_quote":"Supplies the antiwalk embedding lemma (Lemma 5.1) and the oriented-graph antecedent that is reproved as Corollary 5.3."}],"review_version":1}