Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs

Given a simple directed graph $D = (V,A)$, let the size of the largest induced acyclic subgraph \em(dag) of $D$ be denoted by mas$(D)$. Let $D \in \mathcal{D}(n,p)$ be a random instance, obtained by choosing each of the ${{n}\choose{2}}$ possible undirected edges independently with probability $2p$ and then orienting each chosen edge independently in one of two possible directions with probability $1/2$. We obtain improved bounds on the range of concentration, upper and lower bounds of mas$(D)$. Our main result is that mas$(D) \geq \lfloor 2\log_{q} np - X \rfloor$, where $q = (1-p)^{-1}$, $X=1$ if $p \geq n^{-1/3+\epsilon}$ ($\epsilon > 0$ is any constant), $X=W/(\ln q)$ if $p \geq C/n$, where $W>4$ is any constant (and $C=C(W)$ is a suitably large constant). This improves the previously known lower bounds of [J. Spencer and C. Subramanian, Discrete Math. Theor. Comput. Sci., 10 (2008); C. R. Subramanian, Electron. J. Combin., 10 (2003)], where there is an $O(\ln \ln np/\ln q)$ term instead of $X$. We al...