Universality in random graphs via optimal linking systems: trees and beyond

Asaf Cohen Antonir; Lyuben Lichev; Maksim Zhukovskii

REVIEW 2 major objections 5 minor 77 references

Universality in random graphs via optimal linking systems: trees and beyond

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

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

Pith's one-line read There is an absolute constant C>1 such that, with high probability, G(n,C ln n/n) contains every n-vertex tree of maximum degree at most Δ, for every fixed Δ; the same construction yields optimal girth bounds for all cycle factors.

desk verdict Genuinely important results, but the proof has two open seams: Lemma 6.7's termination claim and the sketched T3 case; referee it with those checks. read the letter →

arxiv 2608.06358 v1 pith:W4NC5CUV submitted 2026-08-06 math.CO math.PR

Asaf Cohen Antonir , Lyuben Lichev , Maksim Zhukovskii This is my paper

classification math.COmath.PR MSC 05C8005C05

keywords bounded-degreetreestreeuniversalityrandomgraphslinkingsystemscyclefactorsgirthbarepathsmany-to-onematchings

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

This paper proves that a single absolute constant C>1 governs bounded-degree tree universality: with probability tending to 1 as n grows, the random graph G(n,C ln n/n) contains a copy of every n-vertex tree whose maximum degree is at most Δ, for every fixed Δ. Earlier results needed a constant C that grew with Δ, and deciding whether the constant could be made absolute was an open problem. The proof also determines, up to constant factors, the smallest girth ℓ for which G(n,p) contains every cycle factor of girth at least ℓ, covering all densities from C ln n/n up to $n^{{-1+o(1)}}$; at the lowest density the answer is ℓ≈ln n/ln ln n. The engine of the argument is a linking system of optimal depth, a graph that simultaneously realises every pairing of two boundary vertex sets by disjoint paths of a fixed length.

What carries the argument

The central object is an (a,b;k)-linking system: a graph that, for every permutation σ of [m], contains vertex-disjoint paths of length k pairing each a_i with b_{σ(i)}. The paper constructs such systems of depth k≈C ln n/(ψ ln ln n) in G(n,C(ln n)^ψ/n), which is tight up to a constant factor by a union-bound lower bound, and uses them to embed the families of trees and cycle factors whose many disjoint long paths can be threaded between pre-arranged matchings. For the complementary leaf-heavy trees, the load-bearing mechanism is a leaf-cutting layering of the tree together with a shifting procedure that forces the layer sizes to fall into a bounded set of intervals, so that a union bound over only constantly many size vectors is possible; generalized Hall-type many-to-one matchings then absorb each layer into the host graph.

What would settle it

For a fixed Δ and growing n, enumerate all n-vertex trees with at most exp($Δ^{5}$)α leaves and no Kα bare paths of length n/($K^{2}$α), and run the leaf-cutting plus shifting procedure on each one: finding a single tree whose final layer sizes fall outside the intervals [(20+jδ_1^i)α,(20+jδ_1^i)α+ΔΓ] for all allowed j would disprove the structural lemma on which the leaf-heavy universality proof rests.

Watch

Extended reading notes

Core claim

The central claim is that the threshold for universality among bounded-degree trees has no hidden dependence on the degree bound: at edge probability C ln n/n, with C an absolute constant, the binomial random graph is whp universal for the family T_{n,Δ} of all n-vertex trees of maximum degree at most Δ, simultaneously for every fixed Δ. The proof splits trees into those with many long bare paths, which are embedded by routing each path through a chain of matchings joined by a linking system, and those with many leaves, which require a leaf-cutting layering with many-to-one matchings. A companion theorem gives, for every p with C ln n/n ≤ p = $n^{{-1+o(1)}}$, the minimum girth ℓ up to an absolute multiplicative constant for which the random graph whp contains all cycle factors of girth at least ℓ; at p=C ln n/n this minimum is Θ(ln n/ln ln n).

Load-bearing premise

The hard leaf-heavy case stands or falls on the structural lemma that the leaf-cutting plus shifting procedure always terminates with every layer size inside one of a bounded (as a function of Δ) set of intervals and with the number of shifted vertices at most δ2 α; if some bounded-degree tree forced a layering outside those intervals, the constant-size union bound and the absorption matching would no longer be guaranteed.

Editorial extensions

If this is right

For every fixed Δ, no Δ-dependent factor appears in the constant multiplying ln n/n in the tree-universality threshold, so the threshold is C ln n/n up to an absolute constant.
At p=C ln n/n, every cycle factor of girth at least Θ(ln n/ln ln n) appears whp, and this girth bound cannot be improved by more than a constant factor.
For all densities C ln n/n ≤ p = n^{-1+o(1)} with p=C(ln n)^ψ/n, cycle factors of girth at least K ln n/(ψ ln ln n) appear whp, matching the union-bound lower bound up to constants.
The same linking systems yield universality for graphs obtained by subdividing every edge of a bounded-degree graph by at least 24 ln n/ln ln n vertices, with a constant independent of Δ, and this implies spanning-subdivision minor universality in this density range.
The optimal-depth linking systems also give a new route to embedding spanning structures in sparse random graphs just above the connectivity threshold, where earlier linking-system constructions needed depth Θ((ln n)^2) or larger.

Reading between the lines

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

If the depth of linking systems can be pushed from C ln n/ln ln n to (1+ε) ln n/ln ln n at p=(1+ε) ln n/n, the paper's reductions would likely deliver sharp thresholds for both tree universality and cycle-factor universality at the connectivity threshold.
The spread-improvement idea—prepare a rich family of prefixes in one random subgraph, then apply the fractional expectation-threshold theorem to complements of those prefixes in a second subgraph—looks transferable to other spanning embedding problems where the minimal fragments are contained in too many completions.
The layer-shifting procedure may also suggest a route toward hitting-time statements in the random graph process, though the large absolute constant C in the current proof makes such a transfer far from automatic.

Share X Bluesky LinkedIn Reddit HN

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

First thing to know: this paper looks like it proves the right theorem. The absolute-constant tree universality (Theorem 1) answers Montgomery's question, and the cycle-factor result closes the log-log gap left by Kahn-Lubetzky-Wormald. The optimal-depth linking system in Corollary 3 is genuinely new, and the spread-improvement technique for path systems is a real contribution. I read the core architecture as coherent: T1 via linking systems plus matchings, T2 via layered leaf-cutting with absorption, T3 as a simplified version. The bookkeeping is heavy, but the strategy holds together.

The main soft spot is exactly where the stress-test points: Lemma 6.7. The termination of Algorithm 6.6 and the layer-size bounds are load-bearing for the T2 embedding, and the proof as written does not actually show the process cannot exhaust the available roots before each layer size enters the required interval. The statement that the final size of S_i is between delta_1^i alpha / Delta^Gamma and 2 delta_1^i alpha is asserted, not derived. This matters because Proposition 6.16 and Claims 6.17-6.19 only work for layer-size vectors in the constant-size set Lambda_Gamma. If some tree produced an off-menu layer-size vector, the union bound and the many-to-one matching argument would not cover it. I do not think this is fatal - the claim is plausible and likely follows from the stopping rule - but it needs to be settled before the paper is trusted.

Second gap: Section 6.3 calls the T3 universality proof a sketch. T3 is part of Theorem 1, so a sketch leaves a hole in the main theorem. It is the easy case and probably expands fine, but it is not a complete proof as written.

Minor: the paper repeatedly defers divisibility and rounding issues. Normal for this community, but combined with the above it keeps the proof from being final form.

The citation pattern is honest: Montgomery, Alon-Krivelevich-Sudakov, Frankston-Kahn-Narayanan-Park are all used and credited correctly. No circularity. The new results are not repackaged old ones.

Verdict: this is a major paper if the gaps close. It deserves a serious referee, not a desk reject. I would send it with specific instructions to check Lemma 6.7 and to require a full T3 proof. I would bring it to my reading group in the meantime.

Referee Report

2 major / 5 minor

Summary. The paper develops a framework for proving universality results in sparse random graphs via linking systems of optimal depth. The main results are: Theorem 1, which asserts the existence of an absolute constant C such that, for every fixed Δ≥2, whp G(n,C ln n/n) is universal for all n-vertex trees of maximum degree at most Δ, thereby answering a question of Montgomery; Theorem 2, which constructs (a,b;k)-linking systems of depth Θ(ln n/(ψ ln ln n)) for p=C(ln n)^ψ/n (with Corollary 3 for ψ=1); and Theorem 4, which establishes universality for cycle factors of girth at least K ln n/(ψ ln ln n), optimal up to an absolute constant. The proof decomposes the tree family into T1 (trees with many long bare paths), T2 (trees with an intermediate number of leaves), and T3 (trees with very many leaves). The hard T2 case uses a leaf-cutting and shifting procedure that reduces the number of layer-size vectors to a constant, followed by many-to-one matching constructions. The T1 case is reduced to linking systems and matchings, while T3 is treated by a simplified version of the T2 argument.

Significance. If the proofs are completed as intended, Theorem 1 resolves an open problem of Montgomery and a conjecture of Kahn, with the notable feature that the constant C is independent of Δ. The optimal-depth linking system result is a significant technical advance over sorting-network based constructions, and Theorem 4 gives cycle-factor universality that is tight up to an absolute constant factor. The paper is careful to build on prior results (the fractional expectation-threshold theorem of Frankston–Kahn–Narayanan–Park, Montgomery's rollback lemma, and the Alon–Krivelevich–Sudakov almost-spanning tree theorem) without circularity, and it provides several explicit, quantitative probabilistic lemmas (e.g., Lemmas 3.7, 3.8, 3.11). The claims are falsifiable and the constants are explicit enough to be checked, although the exposition is long and dense.

major comments (2)

[Section 6.1, Lemma 6.7] The termination proof of Algorithm 6.6 is incomplete. The statement 'at every step when i=i, L_i loses between 1 and Δ^Γ vertices and, therefore, the final size of S_i is between δ_1^i α/Δ^Γ and 2δ_1^i α' omits the essential comparison between the number of shifts and the number of available roots. To justify the claimed bounds one must use the definition of λ_i (the largest element of {20α + j δ_1^i α} not exceeding |L_i|-δ_1^i α) to show that the total reduction of |L_i| before stopping is Θ(δ_1^i α), and then combine this with the per-step reduction of at most Δ^Γ to bound the number of steps. One must also show that this number of steps is smaller than |S_{i-1}|, so that the process does not exhaust the available roots before entering the interval [λ_i, λ_i+Δ^Γ]. Neither of these steps appears in the proof. Since Lemma 6.7 supplies the bounded layer-size set Λ_Γ used in the union bound, and the shifted-vertex bound |L*_2 ∪ ... ∪ L*_{Γ+1}| ≤ δ_2 α used in Proposition 6.16, this gap is load-bearing for the T2-case. The argument appears repairable with a more detailed accounting, but as written the lemma is not proved.
[Section 6.3] The proof of T3-universality is explicitly presented as a sketch, with claims deferred by phrases such as 'one can verify' and 'similarly to Proposition 6.16'. Since T3 is one of the three families whose union is T_{n,Δ}, Theorem 1 depends on this case. The paper should provide a complete proof for T3 or a precise reduction to Montgomery's Case A that verifies the absolute-constant dependence on Δ. As it stands, the sketch does not constitute a proof of a load-bearing component of the main theorem.

minor comments (5)

[Algorithm 6.6] In the line 'for every i∈[i,Γ+1]', the symbol i is used both for the current layer and for the loop variable; this should be relabeled (for example, using ℓ) to avoid confusion.
[Algorithm 6.6] The definition of λ_i is written in a nonstandard form: 'max(20α+ (δ i 1α)N0)∩{1,...,|L i|−δ i 1α}'. It should be stated explicitly, for instance as λ_i := max{20α + j δ_1^i α : j ∈ N_0, 20α + j δ_1^i α ≤ |L_i| - δ_1^i α}.
[Abstract and Section 1.2] The journal name 'Transaction of the American Mathematical Society' should be 'Transactions of the American Mathematical Society' in both occurrences.
[Section 6.1.1] In the proof of Proposition 6.8, the phrase 'the same same vertex v' should be 'the same vertex v'.
[Section 6.1, proof of Lemma 6.7] The notation 'δ i 1' should be typeset as δ_1^i for readability; the same applies to 'δ 2' which should be δ_2.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the main theorems rest on external results and first-principles arguments; the flagged Lemma 6.7 issue is an under-proved internal assertion, not a circular step.

full rationale

The derivation chain is self-contained with respect to the target theorems. Theorem 1 is proved by splitting trees into T1, T2 and T3; T1-universality is reduced to Theorem 5.1, whose proof uses only the Alon–Krivelevich–Sudakov almost-spanning tree result and the linking-system Lemma 3.4, and Lemma 3.4 is derived in Appendix A from Theorem 3.3 via path systems and the Frankston–Kahn–Narayanan–Park expectation-threshold theorem. The T2/T3 arguments use rollback and matchmaking lemmas imported from Montgomery [70] and Draganić–Krivelevich–Nenadov [34], none of which contain the absolute-constant universality statement being proved. Theorem 4 follows from the same Theorem 5.1 applied to linear forests obtained from cycle factors, and its optimality is a separate first-moment union bound. The only issue flagged by the reviewer concerns Lemma 6.7: its termination proof asserts that 'the final size of S_i is between δ_1^i α/Δ^Γ and 2δ_1^i α' and then 'the total number of vertices ever shifted is bounded' without a fully explicit derivation from the stopping rule. That is a genuine potential correctness gap in an internal lemma, but it is not circularity: no part of the target theorem is assumed in the proof of Lemma 6.7, no fitted value is renamed as a prediction, and no load-bearing self-citation carries the argument. Citations to the present authors' own preprints appear only as illustrative uses of expectation-threshold techniques, not as support for the main claims. Thus the paper does not reduce, by definition or by self-citation, any of its predictions to its inputs.

Assumptions & free parameters 6 free parameters · 7 assumptions · 0 invented entities

The proof is a conventional probabilistic combinatorics argument and does not fit constants to data. It uses several external theorems as black boxes and a few divisibility assumptions that are explicitly waved off as routine. No new physical or model entities are postulated; linking systems, matchmaking sets, and adapted graphs are combinatorial definitions built from known concepts.

free parameters (6)

C = unspecified >1, chosen sufficiently large
The central theorem asserts existence of an absolute constant C; the proof uses a large-enough constant without an explicit numerical value.
K = sufficiently large absolute constant
Sets alpha = n ln ln n / (K^3 ln n) and the partition sizes in Definition 5.2; many inequalities require K large.
C0, C1, C2, epsilon, C* = 10000, 8, 8700, 10^-100, 2(1+epsilon)
Technical constants in Section 3 used for spreadness bounds and path-system counting; chosen by hand to make the inequalities close.
D = D(K) sufficiently large
Defines p1 = D (ln n)^psi / n in the adapted-graph argument and ensures p2 >= D (ln n)^psi / n.
delta1 = delta1(Delta) sufficiently small, delta1 < Delta^(-Gamma-1)
Step size in the layer-shifting Algorithm 6.6; controls the termination and the bounds in Lemma 6.7.
Gamma = Delta^3
Number of layers in the leaf-cutting construction for T2; chosen as a function of Delta.

assumptions (7)

standard math Chernoff bound and hypergeometric tail bounds
Used in dozens of concentration estimates; stated in Lemma 2.1.
standard math Lovasz Local Lemma
Used to construct matchmaker systems and typical graph events; stated in Lemma 2.2.
standard math Fractional expectation-threshold theorem, quantitative version of Frankston-Kahn-Narayanan-Park via Bell
Used to prove existence of path systems in the second random graph; stated in Theorem 2.15.
standard math Hall-type matching theorems, including many-to-one f-matchings
Core of the layer embedding and matchmaking arguments; Lemma 2.3, Theorem 2.6, and Lemma 2.8.
domain assumption Montgomery's rollback proposition and structural tree lemmas, including Proposition 2.13, Lemma 3.14, Proposition 3.19, and Corollary 3.7 from [70]
External prior results assumed without proof; central to the embeddings in Sections 5 and 6.
domain assumption Alon-Krivelevich-Sudakov almost-spanning tree universality
Provides the embedding of the forest F into G[V1] in Section 5; stated as Theorem 2.9.
ad hoc to paper Divisibility and exact-size assumptions such as m = n/(k+1) and n/(2K^2 alpha) congruent to 4 mod 6
The authors state that full proofs proceed verbatim with routine modifications; used to simplify notation and avoid rounding.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Universality in random graphs via optimal linking systems: trees and beyond." pith.science (2026). https://pith.science/paper/W4NC5CUV

@misc{pith2026260806358,
  author       = {Pith},
  title        = {Pith review of: Universality in random graphs via optimal linking systems: trees and beyond},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W4NC5CUV}},
  note         = {Machine review of arXiv:2608.06358}
}

abstract

We develop a framework for proving universality results in sparse random graphs. As a first application, we show that there exists an absolute constant $C>1$ such that, with high probability, for every fixed constant $\Delta$, the binomial random graph $G(n,C\ln n/n)$ contains every $n$-vertex tree with maximum degree at most $\Delta$. This answers a question of Montgomery (Advances in Mathematics, 2019). We also determine, for every $p$ satisfying $C\ln n/n\leq p=n^{-1+o(1)}$, the minimum girth $\ell$ (up to an absolute multiplicative constant) for which with high probability $G(n,p)$ contains all cycle factors of girth at least $\Omega(\ell)$. In particular, with high probability $G(n,C\ln n/n)$ contains all cycle factors of girth at least $100\ln n/\ln\ln n$, which is optimal up to a constant factor. This extends an earlier result of Ferber, Kronenberg, and Luh (Transaction of the American Mathematical Society, 2019) and significantly improves a corollary of a deep result of Kahn, Lubetzky, and Wormald (Communications on Pure and Applied Mathematics, 2017). One of the key ingredients in the proofs is establishing the optimal depth of linking systems in sparse random graphs.

Figures

Figures reproduced from arXiv: 2608.06358 by the authors.

**Figure 1.** The structure of the matchings found in Lemma 5.3 as part of the embedding of the paths P1, . . . , Pα. We abbreviate Nˆ = (N − 10)/6 and hide some of the names of the sets for stylistic and spacial reasons. The sets V1 \ W, V2 ∪ W and V3 are depicted in red, while the smaller sets A1, A2 and Z0, . . . , Z2Nˆ+1 appear in blue. The solid black segments indicate a perfect matching between two sets, which may be among … view at source ↗

**Figure 2.** Illustration of the shifting procedure in a forest F1, . . . , F5: the original roots of the highest two trees, F1 and F2, are shifted down along the red paths, thus creating the new forest F ′ 1 , F′ 2 , F3, F4, F5. does not ensure that this is the case for every tree in T2: in fact, the number of leaves may significantly shrink even by one step of leaf-cutting. The key observation here is that, if such a shrinking… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

77 extracted references · 71 canonical work pages

[1]

Ajtai, J

M. Ajtai, J. Komlós, and E. Szemerédi. Ano(nlogn)sorting network. InProceedings of the fifteenth annual ACM symposium on Theory of computing, pages 1–9, 1983

work page 1983
[2]

Ajtai, J

M. Ajtai, J. Komlós, and E. Szemerédi. The first occurrence of hamilton cycles in random graphs. Annals of Discrete Mathematics, 27:173–178, 1985

work page 1985
[3]

N. Alon. Universality, tolerance, chaos and order. In I. Bárány and J. Solymosi, editors,An irregular mind. Szemerédi is 70. Dedicated to Endre Szemerédi on the occasion of his seventieth birthday, pages 21–37. Springer, Berlin, 2010. 39

work page 2010
[4]

N. Alon. Implicit representation of sparse hereditary families.Discrete Comput. Geom., 72(2):476–482, 2023

work page 2023
[5]

N. Alon, I. Benjamini, G. Zakharov, and M. Zhukovskii. Sums along the edges of bounded degree graphs.arXiv preprintarXiv:2507.01138, 2025

work page Pith review arXiv 2025
[6]

N. Alon, B. Bukh, and B. Sudakov. Discrete Kakeya-type problems and small bases.Isr. J. Math., 174:285–301, 2009

work page 2009
[7]

Alon and M

N. Alon and M. Capalbo. Sparse universal graphs for bounded-degree graphs.Random Struct Algorithms, 31:123–133, 2007

work page 2007
[8]

N. Alon, M. Krivelevich, and B. Sudakov. Embedding nearly-spanning bounded degree trees.Com- binatorica, 27(6):629–644, 2007

work page 2007

Show all 77 references

[9]

Alon and J

N. Alon and J. H. Spencer.The probabilistic method. Wiley-Interscience Series in Discrete Mathe- matics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, second edition, 2000. With an appendix on the life and work of Paul Erdős

2000
[10]

Alon and R

N. Alon and R. Yuster. Threshold functions forh-factors.Combin. Probab. Comput., 2(2):137–144, 1993

1993
[11]

Alstrup, S

S. Alstrup, S. Dahlgaard, and M. B. T. Knudsen. Optimal induced universal graphs and adjacency labeling for trees.Journal of the ACM, 64(4):1–22, 2017

2017
[12]

Anastos, S

M. Anastos, S. Diskin, D. Ignasiak, L. Lichev, and Y. Sha. Spanning trees of bounded degree in random geometric graphs.arXiv preprint arXiv:2505.16818, 2025

2025 arXiv
[13]

Balogh, B

J. Balogh, B. Csaba, M. Pei, and W. Samotij. Large bounded degree trees in expanding graphs. The Electronic Journal of Combinatorics, pages R6–R6, 2010

2010
[14]

T. Bell. The Park-Pham theorem with optimal convergence rate.arXiv preprint arXiv:2210.03691, 2022

2022 arXiv
[15]

S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg. Universal graphs for bounded- degree trees and planar graphs.SIAM Journal on Discrete Mathematics, 2(2):145–155, 1989

1989
[16]

S. N. Bhatt and C. E. Leiserson.How to assemble tree machines. 1984

1984
[17]

Bollobás

B. Bollobás. The evolution of sparse graphs. InGraph theory and combinatorics, page 35–57. Academic Press, London, 1984

1984
[18]

Bollobás.Modern graph theory, volume 184

B. Bollobás.Modern graph theory, volume 184. Springer Science & Business Media, 1998

1998
[19]

Bonnet, J

E. Bonnet, J. Duron, J. Sylvester, V. Zamaraev, and M. Zhukovskii. Small but unwieldy: A lower bound on adjacency labels for small classes.SIAM Journal on Computing, 53(3):1578–1601, 2024

2024
[20]

Böttcher, J

J. Böttcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk, and Y. Person. Universality for bounded degree spanning trees in randomly perturbed graphs.Random Structures & Algorithms, 55(4):854–864, 2019

2019
[21]

Burghart, A

F. Burghart, A. H. amd M. Kaufmann, N. Müller, and M. Pasch. Sharp thresholds for factors in random graphs.arXiv preprintarXiv:2411.14138, 2024

2024 arXiv
[22]

Capalbo and S

M. Capalbo and S. R. Kosaraju. Small universal graphs. InProceedings of the thirty-first annual ACM symposium on Theory of Computing, STOC ’99, page 741–749, 1999

1999
[23]

M. R. Capalbo. A small universal graph for bounded-degree planar graphs. InProceedings of the 10th Annual Symposium On Disc. Algorithms, SODA ’99, page 156–160, 1999

1999
[24]

Chung and R

F. Chung and R. Graham.Erdős on graphs: His legacy of unsolved problems. AK Pe- ters/CRC Press, 1998

1998
[25]

F. R. K. Chung and R. L. Graham. On graphs which contain all small trees.J. Combin. Theory Ser. B, 24:14–23, 1978

1978
[26]

F. R. K. Chung and R. L. Graham. On universal graphs.Ann. New York Acad. Sci., 319:136–140, 1979

1979
[27]

F. R. K. Chung and R. L. Graham. On universal graphs for spanning trees.Proc. London Math. Soc., 27:203–211, 1983

1983
[28]

F. R. K. Chung, A. L. Rosenberg, and L. Snyder. Perfect storage representations for families of data structures.SIAM J. Alg. Disc. Methods, 4:548–565, 1983

1983
[29]

Delcourt, T

M. Delcourt, T. Kelly, and L. Postle. Thresholds for(n,q,2)-steiner systems via refined absorption. Mathematical Proceedings of the Cambridge Philosophical Society, pages 1–20, 2026

2026
[30]

Dellamonica, Jr

D. Dellamonica, Jr. and Y. Kohayakawa. An algorithmic Friedman–Pippenger theorem on tree embeddings and applications.The Electronic Journal of Combinatorics, pages R127–R127, 2008

2008
[31]

Dellamonica, Jr., Y

D. Dellamonica, Jr., Y. Kohayakawa, V. Rödl, and A. Ruciński. Universality of random graphs. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, page 782–788, 2008. 40

2008
[32]

Dellamonica, Jr., Y

D. Dellamonica, Jr., Y. Kohayakawa, V. Rödl, and A. Ruciński. An improved upper bound on the density of universal random graphs.Random Structures & Algorithm, 46(2):274–299, 2015

2015
[33]

A. E. Díaz and Y. Person. Spanningf-cycles in random graphs.Combinatorics, Probability & Computing, 32(5):833–850, 2023

2023
[34]

Draganić, M

N. Draganić, M. Krivelevich, and R. Nenadov. Rolling backwards can move you forward: on embedding problems in sparse expanders.Transactions of the American Mathematical Society, 375(7):5195–5216, 2022

2022
[35]

Draganić, R

N. Draganić, R. Montgomery, D. Munhá Correia, A. Pokrovskiy, and B. Sudakov. Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

2024 arXiv
[36]

Erdős and A

P. Erdős and A. Rényi. On the evolution of random graphs.Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960

1960
[37]

Ferber, G

A. Ferber, G. Kronenberg, and K. Luh. Optimal threshold for a random graph to be 2-universal. Transactions of the American mathematical Society, 372(6):4239–4262, 2019

2019
[38]

Spanninguniversalityinrandomgraphs.Random Struct Alg, 53:604–637, 2018

A.FerberandR.Nenadov. Spanninguniversalityinrandomgraphs.Random Struct Alg, 53:604–637, 2018

2018
[39]

Ferber, R

A. Ferber, R. Nenadov, and U. Peter. Universality of random graphs and rainbow embedding. Random Struct Alg, 48(3):546–564, 2016

2016
[40]

Frankston, J

K. Frankston, J. Kahn, B. Narayanan, and J. Park. Thresholds versus fractional expectation- thresholds.Ann. of Math. (2), 194(2):475–495, 2021

2021
[41]

Friedgut

E. Friedgut. Sharp thresholds of graph properties, and thek-sat problem.J. Amer. Math. Soc., 12(4):1017–1054, 1999. With an appendix by Jean Bourgain

1999
[42]

Friedman and N

J. Friedman and N. Pippenger. Expanding graphs contain all small trees.Combinatorica, 7(1):71–76, 1987

1987
[43]

Glebov.On Hamilton cycles and other spanning structures

R. Glebov.On Hamilton cycles and other spanning structures. PhD thesis, 2013

2013
[44]

Glebov, D

R. Glebov, D. Johannsen, and M. Krivelevich. Hitting time appearance of certain spanning trees in the random graph process.Unpublished manuscript
[45]

P. E. Haxell. Tree embeddings.Journal of Graph Theory, 36(3):121–130, 2001

2001
[46]

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

2021
[47]

Heckel, M

A. Heckel, M. Kaufmann, N. Müller, and M. Pasch. The hitting time of clique factors.Random Structures & Algorithms, 65(2):275–312, 2024

2024
[48]

Hefetz, M

D. Hefetz, M. Krivelevich, and T. Szabó. Sharp threshold for the appearance of certain spanning trees in random graphs.Random Structures & Algorithms, 41(4):391–412, 2012

2012
[49]

J. Hyde, N. Morrison, A. Müyesser, and M. Pavez-Signé. Spanning trees in pseudorandom graphs via sorting networks.Proceedings of the American Mathematical Society, 153(06):2353–2367, 2025

2025
[50]

Jain and H

V. Jain and H. T. Pham. Optimal thresholds for latin squares, steiner triple systems, and edge colorings. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’24, pages 1425–1436. Society for Industrial and Applied Mathematics, 2024

2024
[51]

Janson, T

S. Janson, T. Łuczak, and A. Rucinski.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000

2000
[52]

Johannsen, M

D. Johannsen, M. Krivelevich, and W. Samotij. Expanders are universal for bounded degree span- ning trees.Combinatorics, Probability and Computing, 22(2):253–281, 2013

2013
[53]

Johansson, J

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

2008
[54]

J. Kahn. Hitting times for shamir’s problem.Transactions of the American Mathematical Society, 375(1):627–668, 2022

2022
[55]

J. Kahn. Asymptotics for shamir’s problem.Advances in Mathematics, 422:109019, 2023

2023
[56]

J. Kahn, E. Lubetzky, and N. Wormald. The threshold for combs in random graphs.Random Structures & Algorithms, 48(4):794–802, 2016

2016
[57]

J. Kahn, E. Lubetzky, and N. Wormald. Cycle factors and renewal theory.Communications on Pure and Applied Mathematics, 70(2):289–339, 2017

2017
[58]

J. Kahn, B. Narayanan, and J. Park. The threshold for the square of a hamilton cycle.Proceedings of the American Mathematical Society, 149(8):3201–3208, 2021

2021
[59]

Kannan, M

S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. InProceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 334–343, New York, NY, USA, 1988. Association for Computing Machinery

1988
[60]

P. Keevash. The optimal edge-colouring threshold.preprint arXiv:2212.04397, 2022. 41

2022 arXiv
[61]

Kim and M

J. Kim and M. Kim. On the size of universal graphs for spanning trees.arXiv preprint arXiv:2511.22358, 2025

2025
[62]

J. H. Kim and S. J. Lee. Universality of random graphs for graphs of maximum degree two.SIAM Journal on Discrete Mathematics, 28(3):1467–1478, 2014

2014
[63]

D. E. Knuth.The art of computer programming, volume 3: sorting and searching. Addison Wesley Longman Publishing Co., Inc., second edition, 1998

1998
[64]

Komlós and E

J. Komlós and E. Szemerédi. Limit distributions for the existence of hamilton circuits in a random graph.Discrete Mathematics, 43:55–63, 1983

1983
[65]

A. D. Korshunov. Solution of a problem of erdős and rényin on hamiltonian cycles in nonoriented graphs.Soviet Math. Doklady, 17:760–764, 1976

1976
[66]

Krivelevich

M. Krivelevich. Triangle factors in random graphs.Combinatorics, Probability and Com- puting, 6:337–347, 1997

1997
[67]

Krivelevich

M. Krivelevich. Embedding spanning trees in random graphs.SIAM Journal on Discrete Mathe- matics, 24(4):1495–1500, 2010

2010
[68]

Krivelevich and R

M. Krivelevich and R. Nenadov. Minors in small-set expanders.Proceedings of the American Mathematical Society, 154:1407–1420, 2026

2026
[69]

Montgomery

R. Montgomery. Embedding bounded degree spanning trees in random graphs.arXiv preprint arXiv:1405.6559, 2014

2014 arXiv
[70]

Montgomery

R. Montgomery. Spanning trees in random graphs.Advances in Mathematics, 356:106793, 2019

2019
[71]

Park and H

J. Park and H. Pham. A proof of the kahn–kalai conjecture.Journal of the American Mathematical Society, 37(1):235–243, 2024

2024
[72]

W. Perkins. Searching for (sharp) thresholds in random structures: where are we now?Bull. Amer. Math. Soc. (N.S.), 62(1):113–143, 2025

2025
[73]

L. Pósa. Hamiltonian circuits in random graphs.Discrete Math., 14:359–364, 1976

1976
[74]

H. Robbins. A remark on stirling’s formula.The American Mathematical Monthly, 62(1):26–29, 1955

1955
[75]

Ruciński

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

1992
[76]

Vakhrushev and M

S. Vakhrushev and M. Zhukovskii. Spanning triangulations in random graphs.preprint arXiv:2605.20361v1, 2026

2026 arXiv
[77]

Zhukovskii

M. Zhukovskii. Sharp thresholds for spanning regular subgraphs.preprint arXiv:2502.14794v3, 2025. AppendixA.Proof of Theorem 2 and Lemma 3.4 We start with a corollary which follows by a simple union bound from Theorem 3.3. For this, we recall that for a functionψwithψ(n)∈ [ 1,...

2025 arXiv

Pith tools

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

[1] [1]

Ajtai, J

M. Ajtai, J. Komlós, and E. Szemerédi. Ano(nlogn)sorting network. InProceedings of the fifteenth annual ACM symposium on Theory of computing, pages 1–9, 1983

work page 1983

[2] [2]

Ajtai, J

M. Ajtai, J. Komlós, and E. Szemerédi. The first occurrence of hamilton cycles in random graphs. Annals of Discrete Mathematics, 27:173–178, 1985

work page 1985

[3] [3]

N. Alon. Universality, tolerance, chaos and order. In I. Bárány and J. Solymosi, editors,An irregular mind. Szemerédi is 70. Dedicated to Endre Szemerédi on the occasion of his seventieth birthday, pages 21–37. Springer, Berlin, 2010. 39

work page 2010

[4] [4]

N. Alon. Implicit representation of sparse hereditary families.Discrete Comput. Geom., 72(2):476–482, 2023

work page 2023

[5] [5]

N. Alon, I. Benjamini, G. Zakharov, and M. Zhukovskii. Sums along the edges of bounded degree graphs.arXiv preprintarXiv:2507.01138, 2025

work page Pith review arXiv 2025

[6] [6]

N. Alon, B. Bukh, and B. Sudakov. Discrete Kakeya-type problems and small bases.Isr. J. Math., 174:285–301, 2009

work page 2009

[7] [7]

Alon and M

N. Alon and M. Capalbo. Sparse universal graphs for bounded-degree graphs.Random Struct Algorithms, 31:123–133, 2007

work page 2007

[8] [8]

N. Alon, M. Krivelevich, and B. Sudakov. Embedding nearly-spanning bounded degree trees.Com- binatorica, 27(6):629–644, 2007

work page 2007