Tree tilings in random regular graphs

Ilay Hoshen; Maksim Zhukovskii; Sahar Diskin

REVIEW 2 major objections 5 minor 30 references

Tree tilings in random regular graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random d-regular graphs tile by every tree of size up to (1−ε)d/ln d, and the bound is sharp.

desk verdict 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. read the letter →

arxiv 2412.19756 v2 pith:SFZQOFE7 submitted 2024-12-27 math.CO math.PR

Sahar Diskin , Ilay Hoshen , Maksim Zhukovskii This is my paper · ORCID

classification math.COmath.PR MSC 05C8005C7005C05

keywords treefactorsrandomd-regulargraphsalgorithmicLovászLocalLemmaperfectmatchingsHall'sconditionpartitionsdegree-sequencestar

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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].

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Other 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.

Who 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[§4.4, Proof of Proposition 4.1, final coupling paragraphs] 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.
[§5.2, medium-size Hall step] 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.

minor comments (5)

[§3, Lemma 3.1] “Bernouli” should be “Bernoulli”.
[§2, proof outline] 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.
[§4.4, final paragraph] 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.
[§4.2, Lemma 4.10] 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.
[§1.1] The name “/suppress Luczak” in the historical discussion should be “T. Łuczak”.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the theorem is derived from an independent LLL partition construction and external edge-distribution bounds.

full rationale

Score 0. I traced the derivation chain of Theorem 1. The main work is Proposition 4.1, which constructs a balanced partition V_i from an i.i.d. uniform random label assignment using five rounds of the Moser–Tardos algorithmic LLL (Sections 4.1–4.4); the closeness property P1 is proved from the resampling bound of Corollary 3.3, and P2 is proved via degree-concentration estimates and LLL applications. Neither property assumes the existence of a T-factor, and no equation defining the partition is equivalent to the theorem statement. Section 5 then transfers expansion from uniformly random partitions to the constructed V_i using the external edge-distribution results of Gao–Ohapkin/McKay (Theorem 4, Corollary 3.4, Lemma 3.5) and proves Hall's condition directly. The optimality bound is supplied by the independent star-factor/dominating-set argument of Alon–Wormald and a first-moment calculation, not by fitting the main theorem. I found no self-citation chain, no fitted input renamed as a prediction, and no definitional equivalence. The reviewer-flagged concern about the Section 4.4 coupling is a potential gap in the proof of P1, not a circularity: the claimed distributional equality (S'_1,...,S'_k) d= (S_1,...,S_k) would need a repair of the partition construction, but even if the gap is real it does not make the theorem equivalent to its inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no invented entities or free parameters fitted to data. The only constants (δ, C, α, β, ξ, η, ε1, ε2) are internal proof parameters chosen to satisfy inequalities; they do not adapt the conclusion to data. The listed axioms are standard probabilistic tools, a cited edge-distribution theorem, the whp locally-tree-like property of random regular graphs, and the external domination-number bound used only for the optimality statement.

assumptions (5)

domain assumption G(n,d) belongs to the family G_d of d-regular graphs with no two cycles of length at most 10 within distance less than 10.
Used to bound dependencies in the LLL applications (Sections 4.1-4.4). It holds whp for random regular graphs (cited to [30]).
standard math Theorem 4 (Gao-Ohapkin, Corollary 8 of [12]): a uniform random graph with a given degree sequence has the stated upper bound on P(e(S1,S2) ≥ ℓ).
Used as a black box for edge distribution in random graphs with specified degrees (Section 3, Lemma 3.5, Claims 5.1 and 5.2).
standard math Lovász Local Lemma and its algorithmic version (Moser-Tardos), Theorem 3.
Core tool for constructing the near-random partition.
domain assumption The domination number lower bound for random regular graphs (Alon-Wormald [2]), implying no star-factor of size larger than (1+ε)d/log d.
Used for the optimality claim in the abstract and introduction; it is an external result.
standard math Otter's bound on the number of trees on k vertices (at most d^2 * 4^d for k ≤ (1-ε)d/log d).
Used to extend the result from a fixed tree T to all trees simultaneously via the union bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tree tilings in random regular graphs." pith.science (2026). https://pith.science/paper/SFZQOFE7

@misc{pith2026241219756,
  author       = {Pith},
  title        = {Pith review of: Tree tilings in random regular graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SFZQOFE7}},
  note         = {Machine review of arXiv:2412.19756}
}

abstract

We show that for every $\epsilon>0$ there exists a sufficiently large $d_0\in \mathbb{N}$ such that for every $d\ge d_0$, whp the random $d$-regular graph $G(n,d)$ contains a $T$-factor for every tree $T$ on at most $(1-\epsilon)d/\ln d$ vertices. This is best possible since, for large enough integer $d$, whp $G(n,d)$ does not contain a $\frac{(1+\epsilon)d}{\ln d}$-star-factor. Our method gives a randomised algorithm which whp finds said $T$-factor and whose expected running time is $O(n^{1+o(1)})$, as well as an efficient deterministic counterpart.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages

[1]

Alon and J

N. Alon and J. H. Spencer. The probabilistic method . Hoboken, NJ: John Wiley & Sons, fourth edition, 2016

work page 2016
[2]

Alon and N

N. Alon and N. Wormald. High degree graphs contain large- star factors. In Fete of Com- binatorics and Computer Science , pages 9–21. Springer, 2010

work page 2010
[3]

Alon and R

N. Alon and R. Yuster. Threshold functions for H-factors. Combinatorics, Probability and Computing, 2(2):137–144, 1993

work page 1993
[4]

Assiyatun and N

H. Assiyatun and N. Wormald. 3-star factors in random d-regular graphs. European Journal of Combinatorics , 27(8):1249–1262, 2006

work page 2006
[5]

Bollob´ as

B. Bollob´ as. Random graphs. In Combinatorics (Swansea, 1981) , volume 52 of London Math. Soc. Lecture Note Ser. , pages 80–102. Cambridge Univ. Press, Cambridge-New York, 1981

work page 1981
[6]

Bollob´ as.Random graphs

B. Bollob´ as.Random graphs. Cambridge University Press, 2nd edition, 2001

work page 2001
[7]

R. L. Burden and J. D. Faires. Numerical analysis. Boston, MA: PWS Publishing Company; London: ITP International Thomson Publishing, 5th ed. edit ion, 1993

work page 1993
[8]

Burghart, A

F. Burghart, A. Heckel, M. Kaufmann, N. M¨ uller, and M. Pa sch. Sharp thresholds for factors in random graphs. arXiv preprint, arXiv:2411.14138 , 2024. 31

arXiv 2024

Show all 30 references

[9]

L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, and S. Sachdeva. Maximum ﬂow and minimum-cost ﬂow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 612–623. IEEE, 2022

2022
[10]

Dragani´ c and M

N. Dragani´ c and M. Krivelevich. Disjoint connected do minating sets in pseudorandom graphs. Proceedings of the 57th Symposium on Theory of Computing (STOC’2 5), accepted
[11]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi. On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar. , 17:359–368, 1966

1966
[12]

Gao and Y

P. Gao and Y. Ohapkin. Subgraph probability of random gr aphs with speciﬁed degrees and applications to chromatic number and connectivity. Random Structures & Algorithms , 62(4):911–934, 2023

2023
[13]

A. Heckel. Random triangles in random graphs. Random Struct. Algorithms, 59(4):616–621, 2021

2021
[14]

Heckel, M

A. Heckel, M. Kaufmann, N. M¨ uller, and M. Pasch. The hit ting time of clique factors. Random Structures & Algorithms , 65:275–312, 2024

2024
[15]

J. Hyde, N. Morrison, A. M¨ uyesser, and M. Pavez-Sign´ e. Spanning trees in pseudorandom graphs via sorting networks. arXiv preprint arXiv:2311.03185 , 2023

2023 arXiv
[16]

S. Janson. Random regular graphs: asymptotic distribu tions and contiguity. Combin. Probab. Comput., 4:369–405, 1995

1995
[17]

Johansson, J

A. Johansson, J. Kahn, and V. Vu. Factors in random graph s. Random Structures & Algorithms, 33(1):1–28, 2008

2008
[18]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi. Proof ofa packing conjecture of Bollob´ as. Comb. Probab. Comput. , 4(3):241–255, 1995

1995
[19]

Krivelevich

M. Krivelevich. Crowns in pseudo-random graphs and ham ilton cycles in their squares. arXiv preprint arXiv:2305.08442 , 2023

2023 arXiv
[20]

Krivelevich and B

M. Krivelevich and B. Sudakov. Pseudo-random graphs. I n More sets, graphs and numbers , volume 15 of Bolyai Soc. Math. Stud. , pages 199–262. Springer, Berlin, 2006

2006
[21]

/suppress Luczak and A

T. /suppress Luczak and A. Ruci´ nski. Tree-matchings in graph processes. SIAM J. Discrete Math. , 4(1):107–120, 1991

1991
[22]

B. D. McKay. Subgraphs of random graphs with speciﬁed de grees. Congr. Numer., 33:213– 223, 1981

1981
[23]

R. A. Moser and G. Tardos. A constructive proof of the gen eral Lov´ asz local lemma. J. ACM, 57(2):15, 2010. Id/No 11

2010
[24]

R. Otter. The number of trees. Annals of Mathematics , 2(49):583–599, 1948

1948
[25]

Pavez-Sign´ e

M. Pavez-Sign´ e. Spanning trees in the square of pseudo random graphs. arXiv preprint arXiv:2307.00322, 2023

2023 arXiv
[26]

O. Riordan. Random cliques in random graphs and sharp thresholds for F-factors. Random Struct. Algorithms, 61(4):619–637, 2022

2022
[27]

R. W. Robinson and N. C. Wormald. Almost all regular grap hs are hamiltonian. Random Structures & Algorithms , 5(2):363–374, 1994. 32

1994
[28]

Ruci´ nski

A. Ruci´ nski. Matching and covering the vertices of a ra ndom graph by copies of a given graph. Discrete Math., 105(1-3):185–197, 1992

1992
[29]

N. C. Wormald. The asymptotic distribution of short cyc les in random regular graphs. J. Combin. Theory Ser. B , 31(2):168–182, 1981

1981
[30]

N. C. Wormald. Models of random regular graphs. In Surveys in Combinatorics, 1999 , volume 267 of London Math. Soc. Lecture Note Ser. , pages 239–298. Cambridge Univ. Press, Cambridge, 1999. A. K1,d−1-factor Let us show that, for d ≥ 5, G(n, d) whp does not contain a K1,d−1-fa...

1999

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Alon and J

N. Alon and J. H. Spencer. The probabilistic method . Hoboken, NJ: John Wiley & Sons, fourth edition, 2016

work page 2016

[2] [2]

Alon and N

N. Alon and N. Wormald. High degree graphs contain large- star factors. In Fete of Com- binatorics and Computer Science , pages 9–21. Springer, 2010

work page 2010

[3] [3]

Alon and R

N. Alon and R. Yuster. Threshold functions for H-factors. Combinatorics, Probability and Computing, 2(2):137–144, 1993

work page 1993

[4] [4]

Assiyatun and N

H. Assiyatun and N. Wormald. 3-star factors in random d-regular graphs. European Journal of Combinatorics , 27(8):1249–1262, 2006

work page 2006

[5] [5]

Bollob´ as

B. Bollob´ as. Random graphs. In Combinatorics (Swansea, 1981) , volume 52 of London Math. Soc. Lecture Note Ser. , pages 80–102. Cambridge Univ. Press, Cambridge-New York, 1981

work page 1981

[6] [6]

Bollob´ as.Random graphs

B. Bollob´ as.Random graphs. Cambridge University Press, 2nd edition, 2001

work page 2001

[7] [7]

R. L. Burden and J. D. Faires. Numerical analysis. Boston, MA: PWS Publishing Company; London: ITP International Thomson Publishing, 5th ed. edit ion, 1993

work page 1993

[8] [8]

Burghart, A

F. Burghart, A. Heckel, M. Kaufmann, N. M¨ uller, and M. Pa sch. Sharp thresholds for factors in random graphs. arXiv preprint, arXiv:2411.14138 , 2024. 31

arXiv 2024