Universality of random graphs and rainbow embedding

DOI10.1002/RSA.20596MaRDI QIDQ2811163zbMATH OpenOpenAlexWikidataFDO

Authors Asaf Ferber, Rajko Nenadov, Ueli Peter

Publication date 10 June 2016

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

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

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)

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).

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

Cites work

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

Cited in

(15)

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

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)