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

Almost-spanning universality in random graphs (Extended abstract)

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

1503.05612.pdf
Files (206.5 kB)
Name Size Download all
md5:fe8df0febff24e5f4328eea8d01aa8b3
206.5 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 23, 2023