On induced acyclic subgraphs in sparse random digraphs

Given a simple directed graph D = ( V , A ) , let the size of the largest induced directed acyclic subgraph (dag) be denoted by mas(D). Let D ∈ D ( n , p ) be a random instance, obtained by choosing each of the ( n 2 ) possible undirected edges independently with probability 2 p and then orienting each chosen edge independently in one of two possible directions with probabibility 1/2. We obtain improved bounds on the concentration width and lower bound of mas(D). Our main result is that there exists C ∈ R + such that for all p ⩾ C / n m a s ( D ) ⩾ ⌊ 2 log q d − X ⌋ where q = ( 1 − p ) − 1 , d = n p , X = W / ( ln q ) and W is a suitably large positive constant. In the case p ⩽ n − 1 / 2 , this improves the previously known lower bound of [Spencer, J. and Subramanian, C.R., (2008). “On the size of induced acyclic subgraphs in random digraphs”, Disc. Math. and Theoret. Comp. Sci., 10:2, 47–54], which had an O ( ln ln d / ln q ) term instead of X.