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 May 2017 | Submitted
Journal Article Open

Almost-spanning universality in random graphs


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

© 2016 Wiley. Issue online 23 March 2017; version of record online 28 April 2016; manuscript accepted 12 January 2016; manuscript received 19 March 2015. Supported by Royal Society University Research Fellowship (to D.C.). We would like to thank the anonymous referees for their thorough reviews and valuable remarks.

Attached Files

Submitted - 1503.05612.pdf


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

Additional details

August 21, 2023
October 18, 2023