Power of k choices and rainbow spanning trees in random graphs

MaRDI QIDQ2256126zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1410.3405, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p29

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

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)

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

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

Cites work

• Q3135082 scientific article; zbMATH DE number 420868 (Why is no real title available?)
• Q3672042 scientific article; zbMATH DE number 3825881 (Why is no real title available?)
• Q4004078 scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Q4519896 scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Q5684698 scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• Multicolored trees in random graphs Multicolored trees in random graphs
• Multicoloured Hamilton cycles Multicoloured Hamilton cycles
• Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Rainbow Hamilton cycles in random graphs Rainbow Hamilton cycles in random graphs
• Random graphs. Random graphs.

Cited in

(4)

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

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)