Search

Let $\mathcal{A}_n $ denote a random acyclic directed graph which is obtained from a random graph with vertex set $\{ 1,2, \cdots ,n\} $, such that each edge is present with a prescribed probability p and all the edges are directed from higher to lower indexed vertices. Define a subset of vertices in $\mathcal{A}_n $ to be strongly independent if there is no directed path between any pair of vertices in the subset. We show that the sequence $\mathcal{J}(\mathcal{A}_n )$, the number of vertices in the largest strongly independent vertex subset of $\mathcal{A}_n $ satisfies with probability tending to 1, \[ \frac{\mathcal{J} (\mathcal{A}_n )}{\sqrt{\log n}} \to \frac{\sqrt{2 }}{\sqrt{\log 1/q}}\quad {\text{as}}\,n \to \infty , \] where $q=1-p$.