Almost-spanning universality in random graphs

DOI10.1002/RSA.20661MaRDI QIDQ5739095zbMATH OpenOpenAlexFDO

Authors David Conlon, Asaf Ferber, Rajko Nenadov, Nemanja Škorić

Publication date 2 June 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.05612, https://resolver.caltech.edu/CaltechAUTHORS:20190812-163000547

zbMATH Keywords

bounded degree graphsrandom graphsuniversality

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A graph $G$ is said to be $mathcalH(n,Delta)$-universal if it contains every graph on $n$ vertices with maximum degree at most $Delta$. It is known that for any $varepsilon>0$ and any natural number $Delta$ there exists $c>0$ such that the random graph $G(n,p)$ is asymptotically almost surely $mathcalH((1-varepsilon)n,Delta)$-universal for $pgeqc(logn/n{)}^{1/Delta}$. Bypassing this natural boundary, we show that for $Deltageq3$ the same conclusion holds when $p=omegaleft(n^{-frac1Delta-1}lo{g}^{5}night)$.

Recommendations

• Almost-spanning universality in random graphs (extended abstract)
• Spanning universality in random graphs
• Universality of Random Graphs for Graphs of Maximum Degree Two
• Universality of random graphs
• Universality of random graphs and rainbow embedding

Cites work

• An improved upper bound on the density of universal random graphs
• Hall's theorem for hypergraphs
• Local resilience of almost spanning trees in random graphs
• On Graphs Which Contain All Sparse Graphs
• On size Ramsey number of paths, trees, and circuits. I
• On Universal Graphs for Spanning Trees
• Sparse partition universal graphs for graphs of bounded degree
• Sparse universal graphs
• Sparse universal graphs for bounded‐degree graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• Universality of random graphs and rainbow embedding
• Universality of Random Graphs for Graphs of Maximum Degree Two

Cited in

(20)

• On universal representation of random graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Non-Ramsey graphs are c n-universal
• 2-universality in randomly perturbed graphs
• Universality of random graphs
• Spanning structures and universality in sparse hypergraphs
• Almost-spanning universality in random graphs (extended abstract)
• Universality for distances in power-law random graphs
• Spanning universality in random graphs
• An improved upper bound on the density of universal random graphs
• Optimal threshold for a random graph to be 2-universal
• Universality of graphs with few triangles and anti-triangles
• Almost universal graphs
• Universal and unavoidable graphs
• The size‐Ramsey number of cubic graphs
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Almost spanning universality in random graphs
• Universality for graphs of bounded degeneracy
• On universal hypergraphs
• Universal edge scaling in random partitions

This page was built for publication: Almost-spanning universality in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5739095)