Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 2015 | public
Journal Article Open

Almost-spanning universality in random graphs (Extended abstract)


A graph G is said to be ℋ(n, Δ)-universal if it contains every graph on n vertices with maximum degree at most Δ. It is known that for any ε > 0 and any natural number Δ there exists c > 0 such that the random graph G(n, p) is asymptotically almost surely ℋ((1 - ε)n, Δ)-universal for p ≥ c(log n/n)^(1/Δ). Bypassing this natural boundary Δ ≥ 3, we show that for the same conclusion holds when [equation; see abstract in PDF for details].

Additional Information

© 2015 Elsevier. Available online 12 November 2015. Research supported by a Royal Society University Research Fellowship.

Attached Files

Submitted - 1503.05612.pdf


Files (206.5 kB)
Name Size Download all
206.5 kB Preview Download

Additional details

August 22, 2023
September 11, 2023