Almost-spanning universality in random graphs

Journal article

A graph G is said to be inline image-universal if it contains every graph on at most n vertices with maximum degree at most Δ. It is known that for any inline image and any natural number Δ there exists inline image such that the random graph G(n, p) is asymptotically almost surely inline image-universal for inline image. Bypassing this natural boundary, we show that for inline image the same conclusion holds when inline image.

Authors: Conlon, D; Ferber, A; Nenadov, R; Škorić, N

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley Publisher's website
• Journal: Random Structures and Algorithms Journal website
• Publication date: 2016-01-01
• Acceptance date: 2016-01-12
• DOI: 10.1002/rsa.20661
• EISSN: 1098-2418
• ISSN: 1042-9832
• Keywords: universality; bounded degree graphs; random graphs