Given an arbitrary graph $G = (V,E)$, such that each vertex v is given randomly a unique integer identifier (call it v). An edge (u,v) is directed from u to v if u > v. This creates a DAG. A sink/source is a vertex that is smaller/larger than all its neighbors.
Assume that an edge $(u,v)$ exist in $G$ with a constant probability. Then, what is the expected number of sinks/sources in $G$ ?
I recall that a maximal independent set in such directed graphs is $O(log n)$ .. is that right ? [I could'nt find any reference yet - so I am not sure]