Number of sinks/sources in a a random directed acyclic graph

Question

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]

Answer 1

A vertex with $k$ neighbours is a sink/source with probability $\frac1{k+1}$, namely if its value is the max/min of the $k$ neighbour values and itself. This is not independantly for different vertices, but that doesn't matter for the expected value. Let $n=|V|$ and $p$ the probability that two vertices are connected by an edge. Then $P(\rho_v=k) = {n-1\choose k}p^k(1-p)^{n-1-k}$ and $v$ is a source with $$\sum_{k=0}^{n-1} \frac1{k+1}{n-1\choose k} p^k(1-p)^{n-1-k}=\sum_{k=0}^{n-1} \frac1{n}{n\choose k+1} p^k(1-p)^{n-1-k}$$ $$=\frac1{np}\sum_{k=1}^{n} {n\choose k} p^{k}(1-p)^{n-k} =\frac{1-(1-p)^n}{np}.$$ Hence the expected number of sinks and sources is $\frac{1-(1-p)^n}p$ each.
NB: For $p\to0$ this is $n$ as expected - every isolated node is a sink/source.

Answer 2

Let $V=\{1,\dots,n\}.$ A vertex $v\in V$ is a sink if and only if none of the edges $uv$ exists where $1\le u\lt v.$ Let $q=1-p,$ the probability that an edge $uv$ does not exist. By symmetry, we have $$\text{expected value of number of sources}$$ $$=\text{expected value of number of sinks}$$ $$=\sum_{v=1}^n\text{probability}(v\text{ is a sink})$$ $$=\sum_{v=1}^nq^{v-1}=\frac{1-q^n}{1-q}=\frac{1-q^n}p=\frac{1-(1-p)^n}p.$$