Rainbow Arborescence in Random Digraphs. Issue 3 (7th October 2015)
- Record Type:
- Journal Article
- Title:
- Rainbow Arborescence in Random Digraphs. Issue 3 (7th October 2015)
- Main Title:
- Rainbow Arborescence in Random Digraphs
- Authors:
- Bal, Deepak
Bennett, Patrick
Cooper, Colin
Frieze, Alan
Prałat, Paweł - Abstract:
- 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 D ( n, m ) be a graph with m edges obtained after m steps of this process. Each edge e i ( i = 1, 2, ..., m ) of D ( n, m ) independently chooses a color, taken uniformly at random from a given set of n ( 1 + O ( log log n / log n ) ) = n ( 1 + o ( 1 ) ) colors. We stop the process prematurely at time M when the following two events hold: D ( n, M ) has at most one vertex that has in‐degree zero and there are at least n − 1 distinct colors introduced ( M = n ( n − 1 ) if at the time when all edges are present there are still less than n − 1 colors introduced; however, this does not happen asymptotically almost surely). The question addressed in this article is whether D ( n, M ) 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."
- Is Part Of:
- Journal of graph theory. Volume 83:Issue 3(2016)
- Journal:
- Journal of graph theory
- Issue:
- Volume 83:Issue 3(2016)
- Issue Display:
- Volume 83, Issue 3 (2016)
- Year:
- 2016
- Volume:
- 83
- Issue:
- 3
- Issue Sort Value:
- 2016-0083-0003-0000
- Page Start:
- 251
- Page End:
- 265
- Publication Date:
- 2015-10-07
- Subjects:
- random digraphs -- arborescence
Graph theory -- Periodicals
511 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0118 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/jgt.21995 ↗
- Languages:
- English
- ISSNs:
- 0364-9024
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 4996.450000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 543.xml