{"id":"e2073ed5-a4e8-4b64-a9d5-1d7d9a76a4ce","arxiv_id":"2012.09201","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Proves that bounded-degree oriented trees and limited tree-like structures (few disjoint cycles, small subdivided graphs) embed as spanning subdigraphs in digraphs with minimum semidegree n/2 + o(n).","lead":"The authors prove that any oriented tree of bounded maximum degree on n vertices embeds as a spanning subdigraph in every digraph on n vertices whose minimum semidegree is at least n/2 + o(n). A smart generalist might read it to see how embedding theorems from undirected graphs extend to directed settings that model real networks with one-way connections.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption restates the explicit hypotheses of the theorem rather than identifying an implicit condition whose failure would invalidate the central claim. Because the statement already restricts to bounded-degree trees and the stated quantitative classes, the scope is not a soft spot but part of what must be true for the claim to hold. With the full manuscript available, no further load-bearing gap appears in the argument structure.","tokens_in":1658,"tokens_out":316,"duration_ms":21464,"concrete_test":"Extract the precise statement of the main tree-embedding theorem (likely Theorem 1.1 or 1.2) and confirm that the o(n) term is permitted to depend on the fixed degree bound Δ; if the proof sketch in §2 or the absorption/embedding lemma in §4 shows the dependence is only on Δ, the claim holds as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the asymptotic embedding of every bounded-maximum-degree oriented tree on n vertices as a spanning subdigraph of any n-vertex digraph with minimum semidegree n/2 + o(n). This is stated explicitly with the bounded-degree and o(n) hypotheses; the more general results on O(n^{0.99}) disjoint cycles and small subdivided graphs are presented as extensions with their quantitative restrictions likewise explicit. No internal inconsistency, hidden assumption on uniformity of the o(n) term, or unsupported step is visible in the claim itself.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1756,"tokens_out":375,"duration_ms":12969,"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.","major_comments":[],"minor_comments":[{"comment":"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).","section":"Abstract and §1"},{"comment":"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.","section":"§1"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[],"tokens_in":1186,"tokens_out":88,"duration_ms":11063,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The central claim is that every oriented tree on n vertices with bounded maximum degree embeds as a spanning subdigraph in any n-vertex digraph whose minimum semidegree is at least n/2 + o(n). The same argument yields embeddings for collections of O(n^0.99) vertex-disjoint cycles and for subdivisions of graphs H with |H| smaller than exp(sqrt(O(log n))), each edge subdivided at least once. This is new: the undirected KSS theorem does not supply the directed version, and the abstract treats the result as a genuine extension rather than a routine translation. The paper does well by stating the quantitative restrictions up front and by deriving the tree case from a single more general embedding statement; that structure makes the bounds usable as a black-box tool in other arguments. The o(n) error term and the explicit size cutoffs on the target structures are presented without hidden assumptions, which keeps the claim honest. The soft spots are limited. The o(n) term is the standard one in this area and the listed restrictions on cycles and subdivisions are necessary for the statement to be true; removing them would likely break the result even under the semidegree hypothesis. Without the full proof text in front of me I cannot check the technical steps, but the claim itself shows no circularity or internal contradiction. This paper is aimed at people who need spanning embeddings in dense digraphs, whether for algorithmic applications or for further extremal work. Anyone already citing the undirected KSS theorem will find the directed version directly relevant. It deserves a serious referee because the question is natural, the statement is clean, and the approach appears to rest on established undirected machinery rather than ad-hoc fitting.","headline":"The paper gives the first explicit directed analogue of the Komlós–Sárközy–Szemerédi theorem for bounded-degree oriented trees and a few other tree-like spanning structures under the natural semidegree condition.","tokens_in":2233,"tokens_out":433,"would_cite":true,"duration_ms":34784,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Pure extremal digraph embedding theorem; no RS contact","alignment":"orthogonal","rationale":"The paper proves asymptotic embedding of bounded-degree oriented trees (and limited tree-like structures with cycles or subdivisions) as spanning subdigraphs of n-vertex digraphs with δ⁰(G) ≥ n/2 + o(n), via regularity, allocation homomorphisms, and greedy embedding. This is classical extremal graph theory (Komlós–Sárközy–Szemerédi analogue) with no reference to cost functions, ratio symmetry, golden-ratio identities, 8-tick periodicity, J-cost forcing, or parameter-free constant derivations. No RS theorem (e.g., reality_from_one_distinction, Jcost uniqueness, phi-ladder, AlexanderDuality D=3) is paralleled or contradicted.","tokens_in":66966,"confidence":"high","tokens_out":189,"duration_ms":5264,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"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).","keywords":["oriented trees","digraph embeddings","minimum semidegree","spanning subdigraphs","tree-like structures","directed graphs","cycle collections","subdivided graphs"],"falsifier":"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.","tokens_in":2550,"feed_emoji":"","tokens_out":806,"duration_ms":24510,"temperature":0.7,"pith_summary":"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.","feed_headline":"Bounded-degree oriented trees span every semidegree n/2 digraph","feed_subtitle":"The embedding holds in every n-vertex digraph whose minimum semidegree reaches n/2 + o(n), extending the undirected Komlós–Sárközy–Szemerédi","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Oriented bounded-degree trees span semidegree n/2 digraphs","Dense digraphs contain bounded-degree oriented trees","Semidegree n/2 digraphs host tree-like spanning structures","Bounded degree oriented trees embed in n/2 semidegree digraphs"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The tree-like structures being embedded must obey the stated quantitative restrictions on degree, number of cycles, or size of the base graph H.","fun_headline_variants_meta":{"raw":{"variants":["Oriented bounded-degree trees span semidegree n/2 digraphs","Dense digraphs contain bounded-degree oriented trees","Semidegree n/2 digraphs host tree-like spanning structures","Bounded degree oriented trees embed in n/2 semidegree digraphs"]},"model":"grok-4.3","cost_usd":0.010667,"raw_usage":{"total_tokens":4709,"prompt_tokens":669,"num_sources_used":0,"completion_tokens":61,"cost_in_usd_ticks":106674500,"prompt_tokens_details":{"text_tokens":669,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3979,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":669,"tokens_out":61,"duration_ms":24366,"temperature":1.0,"reasoning_tokens":3979,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-24T14:21:16.840384+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}