Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]

share|cite|improve this question

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.

share|cite|improve this answer

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.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.