Spanning universality in random graphs

DOI10.1002/RSA.20816MaRDI QIDQ4625020zbMATH OpenOpenAlexFDO

Authors Asaf Ferber, Rajko Nenadov

Publication date 20 February 2019

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

Full work available at URL https://arxiv.org/abs/1707.07914

zbMATH Keywords

random graphsspanning subgraphsuniversality

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: A graph is said to be $mathcalH(n,Delta)$-universal if it contains every graph on $n$ vertices with maximum degree at most $Delta$. Using a `matching-based' embedding technique introduced by Alon and F"uredi, Dellamonica, Kohayakawa, R"odl and Ruci'nski showed that the random graph $G_{n,p}$ is asymptotically almost surely $mathcalH(n,Delta)$-universal for $p=ildeOmega(n^{-1/Delta})$ - a threshold for the property that every subset of $Delta$ vertices has a common neighbour. This bound has become a benchmark in the field and many subsequent results on embedding spanning structures of maximum degree $Delta$ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that $G_{n,p}$ is almost surely $mathcalH(n,Delta)$-universal for $p=ildeOmega(n^{-1/(Delta-1/2)})$.

Recommendations

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

Cited in

(19)

• On universal representation of random graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Random perturbation of sparse graphs
• 2-universality in randomly perturbed graphs
• Clique-factors in sparse pseudorandom graphs
• Universality of random graphs and rainbow embedding
• An improved upper bound on the density of universal random 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
• Almost-spanning universality in random graphs
• Expanders are universal for the class of all spanning trees
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• Almost spanning universality in random graphs
• Universality for graphs of bounded degeneracy
• Universal edge scaling in random partitions

This page was built for publication: Spanning universality in random graphs

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