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 (n2) possible undirected edges independently with probability 2p 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/nmas(D)⩾⌊2logqd−X⌋ where q=(1−p)−1,d=np,X=W/(lnq) 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(lnlnd/lnq) term instead of X.