{"id":"69f862f2-a7d5-4365-8b6a-a60685eb5d5f","arxiv_id":"2412.19756","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every fixed epsilon, with high probability the random d-regular graph contains a vertex-partition into copies of any prescribed tree of size at most (1-epsilon)d/ln d.","lead":"This paper proves that random d-regular graphs almost surely contain a T-factor (a partition of the vertices into identical tree copies) for every tree T with up to about d/ln d vertices. This is optimal, and the proof yields a near-linear-time randomized algorithm to find such a factor.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The LLL-to-uniform-partition coupling in Proposition 4.1 is incomplete: vertices moved into high classes are never removed from their original low classes, so P1 and the transfer to Claim 5.2 are not established as written.","rationale":"The reader identified the closeness of the LLL-produced partition to the initial random partition (P1) and the subsequent transfer of expansion as the weakest assumption. I agree that this is the load-bearing step, but I found a more specific, textually verifiable problem: the coupling in Proposition 4.1 does not remove the N^+_2 vertices from the low classes, so the constructed S' is not a partition and the claimed distributional equality fails as written. This is an internal gap rather than a disagreement with external consensus. The rest of the proof — Claim 5.1, Claim 5.2, the Hall argument, and the algorithmic claims — appears coherent, and the gap is plausibly repaired by the explicit low-class rule and a conditional-uniformity check. Because the central claim depends on this repaired coupling, the appropriate verdict is CONDITIONAL acceptance pending that check, rather than outright rejection or unqualified acceptance.","tokens_in":37406,"tokens_out":40263,"duration_ms":386243,"concrete_test":"Re-derive the coupling in the final paragraph of Section 4.4 with the explicit rule S'_i := (tilde-S_i \\ N^+_2) ∪ S''_i for i > h, where S'' is a uniform partition of N1 ∪ N^-_2 \\ N^+_2. Then prove that, conditional on the high-stage randomness, the labels of vertices in the low pool are i.i.d. uniform on {h+1,...,k}, so (S'_1,...,S'_k) has the claimed distribution. After the repair, re-verify the medium-size Hall step in Section 5.2: for A = W ∩ S_i and d ≥ d0(η, ε2), confirm |N_{S_j}(A) ∩ V_j| ≥ (1 + ε2/2)|A| using the corrected P1 bound; if this inequality fails, the matching step is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central theorem rests on Proposition 4.1's P1: the partition V1,...,Vk produced after five LLL rounds is o_d(n/k)-close to the initial uniform partition S. P1 is justified only by the coupling in the final paragraph of Section 4.4. As written, that coupling starts with a uniform partition tilde-S, thins the first h classes to form S'_1,...,S'_h, runs the first two LLL rounds, and then defines the low classes by S'_i := S'_i ∪ S''_i for i > h, where S'' is a uniform partition of N1 ∪ N^-_2 \\ N^+_2. The text never removes the vertices N^+_2 — the vertices moved into high classes during the LLL rounds — from the original low classes tilde-S_i. Hence the resulting S'_1,...,S'_k is not a partition: vertices in N^+_2 lie simultaneously in a high class and in their old low class. Consequently the asserted distributional equality (S'_1,...,S'_k) = (S_1,...,S_k) is not justified. This matters because Section 5.2 transfers Claim 5.2's expansion from the random partition S to V precisely through P1: the medium-size Hall step applies Claim 5.2 to A = W ∩ S_i and then subtracts |V_i \\ S_i| and |V_j \\ S_j|. If P1 is not rigorously established, the Hall argument for medium-size W collapses. The gap is likely repairable by defining low classes as (tilde-S_i \\ N^+_2) ∪ S''_i and verifying the conditional law of the surviving low labels, but that repair is a necessary step in the proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every ε>0 and all sufficiently large d, the random d-regular graph G(n,d) with high probability contains a T-factor for every tree T on at most (1−ε)d/log d vertices, and it shows that the logarithmic factor is best possible by a star-factor obstruction. The proof constructs a balanced partition V_1,…,V_k of V(G) using five rounds of the algorithmic Lovász Local Lemma, starting from a random partition and keeping the final sets close to it, with each v∈V_i having Θ(d/k) neighbours in V_j for every tree edge {i,j}. It then proves Hall’s condition between the relevant parts using edge-distribution estimates for random graphs with prescribed degree sequences. The method also yields a randomised algorithm with expected running time n^{1+o(1)} and a deterministic polynomial-time counterpart. Most of the argument is detailed and the overall strategy is coherent, but one load-bearing coupling step in Section 4.4 is not written correctly.","tokens_in":37686,"tokens_out":13999,"duration_ms":136589,"significance":"If the proof is completed, this is a strong and natural result: it determines the typical tree-factor threshold in random regular graphs up to the (1−ε) factor, matches the known domination-number obstruction for stars, and gives an efficient algorithm, including a quantitative failure probability 1−n^{−Θ_d(1)}. The five-round LLL construction and the transfer of expansion properties from a random partition to the constructed partition are interesting and likely to be useful beyond this paper. The paper is careful with constants and gives explicit probability estimates. The main caveat is the coupling gap in Section 4.4; it is local and plausibly repairable, but until it is fixed the key property P1 of Proposition 4.1 is not established.","major_comments":[{"comment":"The coupling used to prove (S′_1,…,S′_k) d= (S_1,…,S_k) does not produce a partition. After the first two LLL rounds the text defines N2+ as the set of vertices moved into the high classes and N2− as the set moved out; it then partitions N1 ∪ (N2− \\ N2+) uniformly into S′′_{h+1},…,S′′_k and sets S′_i := S′_i ∪ S′′_i for i>h, with S′_i initially equal to the uniform class tilde S_i. Vertices of N2+ are never removed from their old low classes, so they lie simultaneously in a high class and in a low class. Hence (S′_1,…,S′_k) is not a partition and cannot have the same distribution as the true random partition (S_1,…,S_k). This is load-bearing: property P1 is exactly what allows Section 5.2 to transfer Claim 5.2’s expansion estimates from the uniform partition to the constructed sets V_i, and the medium-size Hall step uses |V_i∖S_i| and |V_j∖S_j| being o_d(n/k). The gap appears repairable by defining the low classes as (tilde S_i \\ N2+) ∪ S′′_i with S′′ partitioning N1 ∪ N2−, and by verifying the conditional law of these low labels given the high-round resampling; this must be written out explicitly.","section":"§4.4, Proof of Proposition 4.1, final coupling paragraphs"},{"comment":"The displayed chain in the medium-size case, |N_{V_j}(W)| ≥ |N_{S_j}(W∩S_i)∩V_j| ≥ (1+ǫ2)|W∩S_i| − |V_j∖S_j| > |W|, is valid only if P1 supplies |V_i∖S_i|,|V_j∖S_j| = o_d(n/k). Since P1’s proof currently contains the coupling flaw described above, this step is not justified as written. I am not treating this as an independent error, but rather as the concrete point where the missing P1 is used; after the Section 4.4 coupling is fixed, the authors should re-check that the P1 error term is indeed small enough for the inequality |W∩S_i| ≥ η2 n/k to hold uniformly.","section":"§5.2, medium-size Hall step"}],"minor_comments":[{"comment":"“Bernouli” should be “Bernoulli”.","section":"§3, Lemma 3.1"},{"comment":"The condition for the difficult regime is stated as “k ≥ log d/(10d)”, but it should be k ≥ d/(10 log d), which is the assumption used in Sections 4.1–4.4 and in Section 4.5.","section":"§2, proof outline"},{"comment":"The notation S′_i := S′_i ∪ S′′_i for i>h is confusing because S′_i appears on both sides; the right-hand side is the initial coupled low class while the left-hand side is the final coupled class. This should be clarified, especially in the corrected coupling.","section":"§4.4, final paragraph"},{"comment":"The statement that each event is determined by Δ1 := 1+d² random variables is conservative; the listed events appear to depend on at most d variables. The larger bound is harmless for the estimates, but the discrepancy should be noted so the reader does not think a dependency is being hidden.","section":"§4.2, Lemma 4.10"},{"comment":"The name “/suppress Luczak” in the historical discussion should be “T. Łuczak”.","section":"§1.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within scope for math.CO and the main theorem is very likely correct. I recommend major revision rather than rejection: the Section 4.4 coupling is a genuine gap in the written proof, but it is local and the suggested repair (delete N2+ from the low classes before adding S′′) is natural and consistent with the rest of the construction. I would be willing to accept once the corrected coupling and the verification of P1 are supplied and the Section 5.2 Hall step is re-checked with the corrected error terms."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is a real advance. The paper proves that G(n,d) contains a T-factor for every tree T on at most (1−ε)d/log d vertices, matching the best possible star-factor bound, and it does so simultaneously for all trees. Prior work only covered non-uniform star factors or specific small stars, so the theorem is genuinely new. The proof idea—five rounds of the algorithmic Lovász Local Lemma to build a near-random balanced partition with controlled cross-degrees—is a substantive contribution, and the algorithmic version is a bonus.\n\nThe paper is mostly careful and detailed. The Hall argument in Section 5 is coherent, and the use of the Gao–Ohapkin edge-distribution result is appropriate. The small-tree case is handled cleanly. The few issues I found are local. The stress-test note is right: the coupling in the final paragraph of Section 4.4 has a genuine omission. The construction there never removes the vertices N_2^+ (which moved into the high classes) from the original low classes tilde-S_i. So the resulting tuple S' is not a partition, and the claimed distributional equality (S'_1,...,S'_k) d= (S_1,...,S_k) is not justified. This matters because the proposition is stated for a uniformly random partition while the body of the proof uses a biased partition; the coupling is what transfers the conclusion. The fix is simple: define the low classes as (tilde-S_i \\ N_2^+) ∪ S''_i and verify the conditional law of the surviving low labels. As written, the step is incomplete, but I do not see it as load-bearing: the repair is direct and the rest of the proof does not depend on anything fragile.\n\nOther soft spots are minor. Lemma 4.10 overestimates the number of determining variables (1+d^2 vs d), but that only makes the LLL bound more conservative. The large-set Hall step in Section 5.2 is terse, but the previous small/medium cases do cover the set B it invokes.\n\nWho gets value from this: researchers working on factors in random graphs, algorithmic LLL, and tree embeddings. I would send it to peer review; the referee should ask for the coupling fix, but I would not reject over it. I would also cite it.","headline":"New and likely optimal tree-factor theorem for random regular graphs; the proof is convincing modulo a small, repairable gap in the coupling at the end of Section 4.4.","tokens_in":38312,"tokens_out":12344,"would_cite":true,"duration_ms":403938,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C70","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random d-regular graphs tile by every tree of size up to (1−ε)d/ln d, and the bound is sharp.","keywords":["tree factors","random d-regular graphs","algorithmic Lovász Local Lemma","perfect matchings","Hall's condition","random partitions","degree-sequence random graphs","star factors"],"falsifier":"Take ε=0.05 and k=⌊(1−ε)d/ln d⌋, and compute the lower-tail probability P(Bin(d,1/k)≤δ ln d) for small δ; the five-round construction requires the equation in Lemma 4.2 to have a solution c∈[ε/4,5] and requires the Moser–Tardos resampling to keep |Vi△Si|=o_d(n/k). A numerical check that either the equation has no root or the resampled partition deviates by more than o_d(n/k) for this k would show the partition step fails, and a direct search for a tree T of this size with no T-factor in a random d-regular graph (for example, by exhaustive matching on moderately large d) would falsify the theorem.","tokens_in":37138,"feed_emoji":"🌳","tokens_out":9272,"duration_ms":76692,"temperature":0.7,"pith_summary":"The paper proves that a random d-regular graph on n vertices contains, with high probability, a spanning collection of vertex-disjoint copies of any fixed tree T whose number of vertices is at most (1−ε)d/ln d. This is the largest size that can be guaranteed: for larger trees of star shape, with about (1+ε)d/ln d vertices, the graph typically has no such factor. The proof splits the vertex set into k nearly equal parts that stay close to a uniformly random partition and are arranged along the edges of T, then shows each adjacent pair of parts is joined by a perfect matching via Hall's condition. The same construction yields a randomized algorithm that finds the factor in expected time $n^{{1+o(1)}}$. The result matters because it pins down the largest tree size for which a universal tiling theorem can hold in random regular graphs.","feed_headline":"Every tree up to d/log d vertices tiles a random regular graph","feed_subtitle":"A new proof shows the threshold is d/ln d, matches a star obstruction, and comes with an n^{1+o(1)} algorithm.","key_machinery":"The central mechanism is a two-stage decomposition. First, a 'nice' balanced partition V1,…,Vk of the vertex set, one part per vertex of T, is constructed by five rounds of the algorithmic Lovász Local Lemma so that each part is within o_d(n/k) of a uniformly random part (Property P1) and every vertex in Vi has degree between δd/k and Cd/k into each adjacent part Vj (Property P2). Second, the edge-distribution bound for random graphs with a specified degree sequence, in the form of Corollary 3.4 and Lemma 3.5, is used to show that whp a random regular graph has expansion between parts: small sets have few edges to equal-sized sets (Claim 5.1) and mid-size subsets of a part have neighbourhood growth (1+ε2)|A| in an adjacent part (Claim 5.2). Together these guarantee Hall's condition between every pair of parts joined by a tree edge, so each such pair admits a perfect matching; matching the parts according to E(T) assembles the T-factor.","core_discovery":"The central claim is a sharp universal tiling theorem: for every ε>0 there is d0 such that for every d≥d0, with probability tending to 1 as n→∞, the random d-regular graph G(n,d) contains a T-factor for every tree T on at most (1−ε)d/ln d vertices, and this is best possible because with high probability there is no factor by stars of size (1+ε)d/ln d. The proof establishes that, with probability 1/4−o(1) over a uniformly random partition, one can resample a small fraction of vertices through five rounds of the algorithmic Lovász Local Lemma to obtain sets V1,…,Vk of size n/k that stay within o_d(n/k) symmetric difference of the random partition and have every vertex in Vi sending between δd/k and Cd/k edges to each Vj with {i,j}∈E(T). For such a 'nice' partition, typical expansion of random regular graphs, derived from degree-sequence edge-distribution bounds, implies Hall's condition between every adjacent pair of parts, yielding a perfect matching for each tree edge and hence a T-factor. The same argument runs in near-linear expected time by using an almost-linear max-flow algorithm for the matchings.","pith_inferences":["A natural next question, not settled here, is whether the d/ln d barrier is the only obstruction: the star counterexample suggests that trees with maximum degree o(d/log d) may admit factors at the same threshold, and the method's expansion step should be checkable for such trees.","Because the proof only needs constant LLL rounds, the five-round resampling scheme may serve as a template for constructing near-random partitions for other spanning subgraph problems in random regular graphs, such as factors by bounded-degree small graphs.","The near-linear algorithm hints that the factor can be found in quasilinear time by direct random partition plus matching; a concrete testable extension is to check whether the LLL resampling can be replaced by a single random partition with a sprinkling step, which would simplify the algorithm at the cost of losing the worst-case probability bounds.","Since the proof works for degree sequences in [d,(1+δ)d], the result should carry over to the configuration model and to random graphs with prescribed degrees; this is directly verifiable by repeating the same argument in that model."],"forward_implications":["For every fixed ε>0 and all sufficiently large d, with high probability G(n,d) contains a T-factor for every tree T on at most (1−ε)d/ln d vertices.","The probability of success is 1−n^{−Θ_d(1)}, and this decay rate is essentially tight, since a fixed set of 10d vertices can fail to host a T-factor.","The d/ln d threshold is sharp: for stars on (1+ε)d/ln d vertices, a first-moment calculation shows whp no factor exists.","A randomized algorithm finds the T-factor whp in expected time n^{1+o(1)}, and a deterministic polynomial-time version exists.","The arguments extend to uniformly random graphs with a given degree sequence whose degrees all lie in [d,(1+δ)d]."],"supporting_citations":[{"why":"Supplies the algorithmic Lovász Local Lemma used in all five resampling rounds to construct the nice partition.","marker":"[23]"},{"why":"Gives the subgraph probability bound for random graphs with specified degrees (Corollary 8) that underpins Claims 5.1 and 5.2.","marker":"[12]"},{"why":"Earlier degree-sequence edge-distribution result cited alongside [12] for the same expansion estimates.","marker":"[22]"},{"why":"Provides random-regular-graph model facts used to ensure G(n,d) typically has no two short cycles close together.","marker":"[30]"},{"why":"Almost-linear maximum-flow algorithm used to find the perfect matchings between parts, giving the n^{1+o(1)} running time.","marker":"[9]"},{"why":"Shows large-star factors and the dominating-set lower bound that motivate the optimality of the d/log d threshold.","marker":"[2]"},{"why":"Bounds the number of trees on k vertices, used to pass from a fixed tree T to every tree via the union bound.","marker":"[24]"}],"fun_headline_variants":["Random d-regular graphs tile every tree up to d/ln d","Optimal tree tiling threshold in random d-regular graphs","All small trees tile random regular graphs at optimal density","Near-linear algorithm finds tree factors in random d-regulars","Exact tiling threshold for trees in random regular graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the partition obtained after the five resampling rounds staying close enough to the initial uniformly random partition (within o_d(n/k) symmetric difference per part) that the expansion properties proved for random partitions transfer to the actual parts; if that closeness fails at tree size k, the Hall-condition argument for perfect matchings between parts collapses.","fun_headline_variants_meta":{"raw":{"variants":["Random d-regular graphs tile every tree up to d/ln d","Optimal tree tiling threshold in random d-regular graphs","All small trees tile random regular graphs at optimal density","Near-linear algorithm finds tree factors in random d-regulars","Exact tiling threshold for trees in random regular graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001847,"raw_usage":{"total_tokens":7251,"prompt_tokens":933,"completion_tokens":6318,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":6233}},"tokens_in":549,"tokens_out":6318,"duration_ms":47611,"temperature":1.0,"reasoning_tokens":6233,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:54:48.558922+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take ε=0.05 and k=⌊(1−ε)d/ln d⌋, and compute the lower-tail probability P(Bin(d,1/k)≤δ ln d) for small δ; the five-round construction requires the equation in Lemma 4.2 to have a solution c∈[ε/4,5] and requires the Moser–Tardos resampling to keep |Vi△Si|=o_d(n/k). A numerical check that either the equation has no root or the resampled partition deviates by more than o_d(n/k) for this k would show the partition step fails, and a direct search for a tree T of this size with no T-factor in a random d-regular graph (for example, by exhaustive matching on moderately large d) would falsify the theorem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the algorithmic Lovász Local Lemma used in all five resampling rounds to construct the nice partition."},{"cited_title":"Gao and Y","cited_arxiv_id":null,"evidence_quote":"Gives the subgraph probability bound for random graphs with specified degrees (Corollary 8) that underpins Claims 5.1 and 5.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier degree-sequence edge-distribution result cited alongside [12] for the same expansion estimates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides random-regular-graph model facts used to ensure G(n,d) typically has no two short cycles close together."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Almost-linear maximum-flow algorithm used to find the perfect matchings between parts, giving the n^{1+o(1)} running time."},{"cited_title":"Alon and N","cited_arxiv_id":null,"evidence_quote":"Shows large-star factors and the dominating-set lower bound that motivate the optimality of the d/log d threshold."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Bounds the number of trees on k vertices, used to pass from a fixed tree T to every tree via the union bound."}],"review_version":1}