Packing a randomly edge-colored random graph with rainbow k-outs

MaRDI QIDQ6255290zbMATH OpenFDO

Authors Asaf Ferber, Gal Kronenberg, Frank Mousset, Clara Shikhelman

Publication date 7 October 2014

Abstract: Let $G$ be a graph on $n$ vertices and let $k$ be a fixed positive integer. We denote by $$k$$ the probability space consisting of subgraphs of $G$ where each vertex $vinV(G)$ randomly picks $k$ neighbors from $G$, independently from all other vertices. We show that if $delta(G)=omega(logn)$ and $kgeq2$, then the following holds for every $p=omega(logn/delta(G))$. Let $H$ be a random graph obtained by keeping each $einE(G)$ with probability $p$ independently at random and then coloring its edges independently and uniformly at random with elements from the set $[kn]$. Then, w.h.p. $H$ contains $t:=(1-o(1))delta(G)p/(2k)$ edge-disjoint graphs $H_1,\mathrm{...},H_t$ such that each of the $H_i$ is emph{rainbow} (that is, all the edges are colored with distinct colors), and such that for every monotone increasing property of graphs $mathcalP$ and for every $1leqileqt$ we have $$k$$. Note that since (in this case) a typical member of $$k$$ has average degree roughly $2k$, this result is asymptotically best possible. We present several applications of this; for example, we use this result to prove that for $p=omega(logn/n)$ and $c=23n$, a graph $Hsimmathcal{G}_c(K_n,p)$ w.h.p. contains $(1-o(1))np/46$ edge-disjoint rainbow Hamilton cycles. More generally, using a recent result of Frieze and Johansson, the same method allows us to prove that if $G$ has minimum degree $delta(G)geq(1+varepsilon)n/2$, then there exist functions $c=O(n)$ and $t=Theta(np)$ (depending on $varepsilon$) such that the random subgraph $Hsimmathcal{G}_c(G,p)$ w.h.p. contains $t$ edge-disjoint rainbow Hamilton cycles.

This page was built for publication: Packing a randomly edge-colored random graph with rainbow $k$-outs

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