Power of k choices and rainbow spanning trees in random graphs

zbMATH Open1307.05064arXiv1410.3405MaRDI QIDQ2256126FDOQ2256126

Authors: Deepak Bal, Patrick Bennett, Paweł Prałat, Alan Frieze 

Publication date: 19 February 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider the ErdH{o}s-R'enyi random graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let $mathcalG(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ($i=1,2,\mathrm{...},m$) of $mathcalG(n,m)$ independently chooses precisely $kinmathbbN$ colours, uniformly at random, from a given set of $n-1$ colours (one may view $e_i$ as a multi-edge). We stop the process prematurely at time $M$ when the following two events hold: $mathcalG(n,M)$ is connected and every colour occurs at least once ($M=nchoose2$ if some colour does not occur before all edges are present; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $mathcalG(n,M)$ has a rainbow spanning tree (that is, multicoloured tree on $n$ vertices). Clearly, both properties are necessary for the desired tree to exist. In 1994, Frieze and McKay investigated the case $k=1$ and the answer to this question is "yes" (asymptotically almost surely). However, since the sharp threshold for connectivity is $fracn2logn$ and the sharp threshold for seeing all the colours is $fracnklogn$, the case $k=2$ is of special importance as in this case the two processes keep up with one another. In this paper, we show that asymptotically almost surely the answer is "yes" also for $kge2$.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Multicolored trees in random graphs
• Rainbow trees in uniformly edge‐colored graphs
• Rainbow arborescence in random digraphs
• Rainbow connectivity of sparse random graphs
• On the threshold for rainbow connection number \(r\) in random graphs

zbMATH Keywords

Erdős-Rényi random graph process

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Multicoloured Hamilton cycles
• Random graphs.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold
• Multicolored trees in random graphs
• Rainbow Hamilton cycles in random graphs

Cited In (4)

• Rainbow arborescence in random digraphs
• Rainbow spanning trees in random subgraphs of dense regular graphs
• Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\)
• Rainbow trees in uniformly edge‐colored graphs

This page was built for publication: Power of \(k\) choices and rainbow spanning trees in random graphs

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