Random Digraphs : Some Concentration Results

C.R. Subramanian, The Institute of Mathematical Sciences, Chennai.

Consider the random digraph $D(n,p)$ obtained by initially choosing a random undirected graph $G(n,2p)$ with uniform edge probability $2p$ and then choosing uniformly a random orientation of this graph. We study the maximum sizes of any induced acyclic tournament and any induced acyclic subgraph in such a random digraph. We describe a 2-point concentration for the first invariant and a tight concentration for the second invariant. This is joint work with Kunal Dutta and Joel Spencer.