Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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. (Note: For $p\to0$ this is $n$ as expeted - every isolated node is a sink/source).

share|improve this answer
add comment

Your Answer

 
discard

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.