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

Additional details