Power of k choices and rainbow spanning trees in random graphs

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

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

We consider the Erdős-Rényi 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 G(n, m) be a graph with m edges obtained after m steps of this process. Each edge ei (i = 1, 2,…, m) of G(n, m) independently chooses precisely k ∈ N colours, uniformly at random, from a given set of n–1 colours (one may view ei as a multi-edge). We stop the process prematurely at time M when the following two events hold: G(n, M) is connected and every colour occurs at least once (M = (n2) 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 G(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 n/2 log n and the sharp threshold for seeing all the colours is n/k log n, 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 k ≥ 2.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume22
Issue number1
StatePublished - 1 Jan 2015

Fingerprint

Spanning tree
Random Graphs
Color
Sharp Threshold
Random processes
Stochastic Processes
Connectivity
Choose
Necessary
Graph in graph theory

Cite this

Bal, Deepak ; Bennett, Patrick ; Frieze, Alan ; Prałat, Paweł. / Power of k choices and rainbow spanning trees in random graphs. In: Electronic Journal of Combinatorics. 2015 ; Vol. 22, No. 1.
@article{15649a66038243caa7c97e79b5978ecf,
title = "Power of k choices and rainbow spanning trees in random graphs",
abstract = "We consider the Erdős-R{\'e}nyi 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 G(n, m) be a graph with m edges obtained after m steps of this process. Each edge ei (i = 1, 2,…, m) of G(n, m) independently chooses precisely k ∈ N colours, uniformly at random, from a given set of n–1 colours (one may view ei as a multi-edge). We stop the process prematurely at time M when the following two events hold: G(n, M) is connected and every colour occurs at least once (M = (n2) 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 G(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 n/2 log n and the sharp threshold for seeing all the colours is n/k log n, 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 k ≥ 2.",
author = "Deepak Bal and Patrick Bennett and Alan Frieze and Paweł Prałat",
year = "2015",
month = "1",
day = "1",
language = "English",
volume = "22",
journal = "Electronic Journal of Combinatorics",
issn = "1077-8926",
publisher = "Electronic Journal of Combinatorics",
number = "1",

}

Power of k choices and rainbow spanning trees in random graphs. / Bal, Deepak; Bennett, Patrick; Frieze, Alan; Prałat, Paweł.

In: Electronic Journal of Combinatorics, Vol. 22, No. 1, 01.01.2015.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Power of k choices and rainbow spanning trees in random graphs

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Frieze, Alan

AU - Prałat, Paweł

PY - 2015/1/1

Y1 - 2015/1/1

N2 - We consider the Erdős-Rényi 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 G(n, m) be a graph with m edges obtained after m steps of this process. Each edge ei (i = 1, 2,…, m) of G(n, m) independently chooses precisely k ∈ N colours, uniformly at random, from a given set of n–1 colours (one may view ei as a multi-edge). We stop the process prematurely at time M when the following two events hold: G(n, M) is connected and every colour occurs at least once (M = (n2) 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 G(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 n/2 log n and the sharp threshold for seeing all the colours is n/k log n, 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 k ≥ 2.

AB - We consider the Erdős-Rényi 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 G(n, m) be a graph with m edges obtained after m steps of this process. Each edge ei (i = 1, 2,…, m) of G(n, m) independently chooses precisely k ∈ N colours, uniformly at random, from a given set of n–1 colours (one may view ei as a multi-edge). We stop the process prematurely at time M when the following two events hold: G(n, M) is connected and every colour occurs at least once (M = (n2) 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 G(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 n/2 log n and the sharp threshold for seeing all the colours is n/k log n, 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 k ≥ 2.

UR - http://www.scopus.com/inward/record.url?scp=84922983840&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84922983840

VL - 22

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

SN - 1077-8926

IS - 1

ER -