Rainbow arborescence in random digraphs (Q2833120)

A rainbow arborescence in a directed graph on \(n\) vertices whose edges have been coloured is a rooted spanning tree in the graph where all \(n-1\) edges point away from the root and have different colours. Two obvious necessary conditions for this to happen are that at most one vertex has indegree zero and that at least \(n-1\) colours have been used.NEWLINENEWLINEThe paper under review studies the Erdős-Rényi random graph process which starts with \(n\) isolated vertices and at each stage adds one directed edge chosen uniformly at random from the set of edges not thus far added: let \(\mathcal{D}(n,m)\) denote the state of this process when \(m\) edges have been added. The question posed in this paper is what happens when the process is stopped when at most one vertex has outdegree zero and \(n-1\) colours are present. The answer is that with probability tending to 1 as \(n\rightarrow\infty\), there is a rainbow arborescence.NEWLINENEWLINEThe proof is delicate -- the event that causes the process to stop has probability tending to 0 with \(n\) -- and depends on, very crudely summarising, revealing the randomness in a very specific order (relative to a certain encoding of the coloured graph) and working round some vertices having dangerously low in-degrees in certain colours.