Rainbow Arborescence in Random Digraphs

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

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

We consider the Erdős–Rényi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let (Formula presented.) be a graph with m edges obtained after m steps of this process. Each edge (Formula presented.) ((Formula presented.)) of (Formula presented.) independently chooses a color, taken uniformly at random from a given set of (Formula presented.) colors. We stop the process prematurely at time M when the following two events hold: (Formula presented.) has at most one vertex that has in-degree zero and there are at least (Formula presented.) distinct colors introduced ((Formula presented.) if at the time when all edges are present there are still less than (Formula presented.) colors introduced; however, this does not happen asymptotically almost surely). The question addressed in this article is whether (Formula presented.) has a rainbow arborescence (i.e. a directed, rooted tree on n vertices in which all edges point away from the root and all the edges are different colors). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is “yes.”.

Original languageEnglish
Pages (from-to)251-265
Number of pages15
JournalJournal of Graph Theory
Volume83
Issue number3
DOIs
StatePublished - 1 Nov 2016

Fingerprint

Digraph
Rooted Trees
Random Graphs
Directed Graph
Stochastic Processes
Choose
Color
Roots
Distinct
Necessary
Zero
Graph in graph theory
Vertex of a graph

Keywords

  • arborescence
  • random digraphs

Cite this

Bal, D., Bennett, P., Cooper, C., Frieze, A., & Prałat, P. (2016). Rainbow Arborescence in Random Digraphs. Journal of Graph Theory, 83(3), 251-265. https://doi.org/10.1002/jgt.21995
Bal, Deepak ; Bennett, Patrick ; Cooper, Colin ; Frieze, Alan ; Prałat, Paweł. / Rainbow Arborescence in Random Digraphs. In: Journal of Graph Theory. 2016 ; Vol. 83, No. 3. pp. 251-265.
@article{e1e03bd07dce42b99f34debb50280e27,
title = "Rainbow Arborescence in Random Digraphs",
abstract = "We consider the Erdős–R{\'e}nyi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let (Formula presented.) be a graph with m edges obtained after m steps of this process. Each edge (Formula presented.) ((Formula presented.)) of (Formula presented.) independently chooses a color, taken uniformly at random from a given set of (Formula presented.) colors. We stop the process prematurely at time M when the following two events hold: (Formula presented.) has at most one vertex that has in-degree zero and there are at least (Formula presented.) distinct colors introduced ((Formula presented.) if at the time when all edges are present there are still less than (Formula presented.) colors introduced; however, this does not happen asymptotically almost surely). The question addressed in this article is whether (Formula presented.) has a rainbow arborescence (i.e. a directed, rooted tree on n vertices in which all edges point away from the root and all the edges are different colors). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is “yes.”.",
keywords = "arborescence, random digraphs",
author = "Deepak Bal and Patrick Bennett and Colin Cooper and Alan Frieze and Paweł Prałat",
year = "2016",
month = "11",
day = "1",
doi = "10.1002/jgt.21995",
language = "English",
volume = "83",
pages = "251--265",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "3",

}

Bal, D, Bennett, P, Cooper, C, Frieze, A & Prałat, P 2016, 'Rainbow Arborescence in Random Digraphs', Journal of Graph Theory, vol. 83, no. 3, pp. 251-265. https://doi.org/10.1002/jgt.21995

Rainbow Arborescence in Random Digraphs. / Bal, Deepak; Bennett, Patrick; Cooper, Colin; Frieze, Alan; Prałat, Paweł.

In: Journal of Graph Theory, Vol. 83, No. 3, 01.11.2016, p. 251-265.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Rainbow Arborescence in Random Digraphs

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Cooper, Colin

AU - Frieze, Alan

AU - Prałat, Paweł

PY - 2016/11/1

Y1 - 2016/11/1

N2 - We consider the Erdős–Rényi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let (Formula presented.) be a graph with m edges obtained after m steps of this process. Each edge (Formula presented.) ((Formula presented.)) of (Formula presented.) independently chooses a color, taken uniformly at random from a given set of (Formula presented.) colors. We stop the process prematurely at time M when the following two events hold: (Formula presented.) has at most one vertex that has in-degree zero and there are at least (Formula presented.) distinct colors introduced ((Formula presented.) if at the time when all edges are present there are still less than (Formula presented.) colors introduced; however, this does not happen asymptotically almost surely). The question addressed in this article is whether (Formula presented.) has a rainbow arborescence (i.e. a directed, rooted tree on n vertices in which all edges point away from the root and all the edges are different colors). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is “yes.”.

AB - We consider the Erdős–Rényi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let (Formula presented.) be a graph with m edges obtained after m steps of this process. Each edge (Formula presented.) ((Formula presented.)) of (Formula presented.) independently chooses a color, taken uniformly at random from a given set of (Formula presented.) colors. We stop the process prematurely at time M when the following two events hold: (Formula presented.) has at most one vertex that has in-degree zero and there are at least (Formula presented.) distinct colors introduced ((Formula presented.) if at the time when all edges are present there are still less than (Formula presented.) colors introduced; however, this does not happen asymptotically almost surely). The question addressed in this article is whether (Formula presented.) has a rainbow arborescence (i.e. a directed, rooted tree on n vertices in which all edges point away from the root and all the edges are different colors). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is “yes.”.

KW - arborescence

KW - random digraphs

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

U2 - 10.1002/jgt.21995

DO - 10.1002/jgt.21995

M3 - Article

AN - SCOPUS:84949883759

VL - 83

SP - 251

EP - 265

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -

Bal D, Bennett P, Cooper C, Frieze A, Prałat P. Rainbow Arborescence in Random Digraphs. Journal of Graph Theory. 2016 Nov 1;83(3):251-265. https://doi.org/10.1002/jgt.21995