Carnegie Mellon University
Browse
file.pdf (399.74 kB)

Power of k choices and rainbow spanning trees in random graphs

Download (399.74 kB)
journal contribution
posted on 2014-12-18, 00:00 authored by Deepak Bal, Patrick Bennett, Alan FriezeAlan Frieze, Pawel Pralat

We consider the Erdős-Rényi random graph process, which is a stochastic process that starts with nvertices 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 nvertices). 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 n2logn and the sharp threshold for seeing all the colours is nklogn, 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.

History

Publisher Statement

Copyright 2015 the Authors

Date

2014-12-18

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC