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

Abstract

Let $G$ be a graph on $n$ vertices and let $k$ be a fixed positive integer. We denote by $\mathcal G_{\text{$k$-out}}(G)$ the probability space consisting of subgraphs of $G$ where each vertex $v\in V(G)$ randomly picks $k$ neighbors from $G$, independently from all other vertices. We show that if $\delta (G)=\omega (\log n)$ and $k\ge 2$, then the following holds for every $p=\omega (\log n/\delta (G))$. Let $H$ be a random graph obtained by keeping each $e\in E(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,...,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 $\mathcal{P}$ and for every $1\le i\le t$ we have $\Pr[\mathcal G_{\text{$k$-out}}(G)\models \mathcal P]\leq \Pr[H_i\models \mathcal P]+n^{-ω(1)}$. Note that since (in this case) a typical member of $\mathcal G_{\text{$k$-out}}(G)$ 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 (\log n/n)$ and $c=23n$, a graph $H\sim {\mathcal{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)\ge (1+\epsilon )n/2$, then there exist functions $c=O(n)$ and $t=\Theta (np)$ (depending on $\epsilon$) such that the random subgraph $H\sim {\mathcal{G}}_c(G,p)$ w.h.p. contains $t$ edge-disjoint rainbow Hamilton cycles.

Cited by in corpus (1)

• Perfect fractional matchings in k-out hypergraphs