Universality of random graphs and rainbow embedding

DOI10.1002/RSA.20596zbMATH Open1338.05248arXiv1311.7063OpenAlexW1951087126WikidataQ105583249 ScholiaQ105583249MaRDI QIDQ2811163FDOQ2811163

Authors: Asaf Ferber, Rajko Nenadov, Ueli Peter 

Publication date: 10 June 2016

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

Abstract: In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of $G(n,p)$. Let the emph{maximum density} of a graph $H$ be the maximum average degree of all the subgraphs of $H$. First, we show that for $p=omega(Delt{a}^{12}{n}^{-1/2d}lo{g}^{3}n)$, a graph $GsimG(n,p)$ w.h.p. contains copies of all spanning graphs $H$ with maximum degree at most $Delta$ and maximum density at most $d$. For $d<Delta/2$, this improves a result of Dellamonica, Kohayakawa, R"odl and Ruci'ncki. Next, we show that if we additionally restrict the spanning graphs to have girth at least 7 then the random graph contains w.h.p. all such graphs for $p=omega(Delt{a}^{12}{n}^{-1/d}lo{g}^{3}n)$. In particular, if $p=omega(Delt{a}^{12}{n}^{-1/2}lo{g}^{3}n)$, the random graph therefore contains w.h.p. every spanning tree with maximum degree bounded by $Delta$. This improves a result of Johannsen, Krivelevich and Samotij. Finally, in the same spirit, we show that for any spanning graph $H$ with constant maximum degree, and for suitable $p$, if we randomly color the edges of a graph $GsimG(n,p)$ with $(1+o(1))|E(H)|$ colors, then w.h.p. there exists a emph{rainbow} copy of $H$ in $G$ (that is, a copy of $H$ with all edges colored with distinct colors).

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

Recommendations

• Spanning universality in random graphs
• Embedding spanning trees in random graphs
• Universality of random graphs
• Embedding large graphs into a random graph
• Rainbow trees in uniformly edge‐colored graphs

zbMATH Keywords

embeddingsrandom graphsuniversality

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Embedding nearly-spanning bounded degree trees
• Large bounded degree trees in expanding graphs
• Factors in random graphs
• Concentration of Measure for the Analysis of Randomized Algorithms
• Spanning subgraphs of random graphs
• Sparse universal graphs
• Local resilience of almost spanning trees in random graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• On Graphs Which Contain All Sparse Graphs
• On Universal Graphs for Spanning Trees
• Sparse universal graphs for bounded‐degree graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Expanders Are Universal for the Class of All Spanning Trees
• Matching and covering the vertices of a random graph by copies of a given graph
• Explicit sparse almost-universal graphs for \(\mathcal G (n, \frac kn)\)
• Universality of Random Graphs for Graphs of Maximum Degree Two
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• Rainbow Hamilton cycles in random graphs

Cited In (14)

• Spanning structures and universality in sparse hypergraphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• The threshold for the full perfect matching color profile in a random coloring of random graphs
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• Spanning universality in random graphs
• An improved upper bound on the density of universal random graphs
• On rainbow Hamilton cycles in random hypergraphs
• Almost spanning universality in random graphs
• Rainbow trees in uniformly edge‐colored graphs
• Optimal threshold for a random graph to be 2-universal
• On universal representation of random graphs
• Almost-spanning universality in random graphs
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree

This page was built for publication: Universality of random graphs and rainbow embedding

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