Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops).

Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for all edges $e \in E$. Let $D_G(k,l,m) = (V,A)$ be the random digraph obtained from $G$ in the following manner: independently for each edge $e = \{u,v\} \in E$, remove $e$ and replace it with:

  1. the arc $(u,v)$ with probability $k(e)$;
  2. the arc $(v,u)$ with probability $k(e)$;
  3. nothing with probability $l(e)$;
  4. both arcs $(u,v)$ and $(v,u)$ with probability $m(e)$.

For a choice of root $q \in V$, we say a digraph $D = (V,A)$ is $q$-connected if there is a directed path from $q$ to every vertex $v \in V\setminus \{q\}$.

Proposition: $\mathrm{Pr}(D_G(k,l,m) \textrm{ is $q$-connected}) = \mathrm{Pr}(D_G(k',l',m') \textrm{ is $q'$-connected})$ if $k(e) + l(e) = k'(e) + l'(e)$ for every edge $e \in E$.

I know that this proposition is true; it follows from the discussion in Remark 5.4 of this paper. Basically the reason it is true is because both probabilities can be computed via a deletion-contraction recurrence.

But I would like to know if there is a simpler/more conceptual reason why this probability should be independent of the particular distribution $(k,l,m)$ so long as $k(e) + l(e)$ is fixed. (It is pretty easy to see, via ``path-reversals'', why it is independent of the choice of root $q$.)

Here is one heuristic reason why we might expect this probability to depend only on $k(e) + l(e)$. Fix a root $q \in V$. Let us say a cut $C = \{U,W\}$ of $G$ is bad for a digraph $D = (V,A)$ if $q \in U$ and there are no arcs from $U$ to $V$ in $D$. Observe that $D$ is $q$-connected iff it has no bad cuts. And the probability a given cut $C$ is bad for $D_G(k,l,m)$ is $\prod_{e \in \mathrm{cutset}(C)} (k(e) + l(e))$. But this is not a rigorous proof that $k(e) + l(e)$ is all that matters because clearly the events of $C$ and $C'$ being bad for $D_G(k,l,m)$ are not independent.


Instead of thinking of the initial graph as undirected, replace each edge with directed edges in each direction. The meaning of $k(e)+l(e)$ is the probability that you remove the directed edge $uv$. (You also want to assume the probability of removing $vu$ stays the same.)

Choose any edge $e$. Condition on the rest of the graph. The conditional probability that the graph is $q$-connected is one of $0$, $1$, the probability of including $uv$, or the probability of including $vu$. It can't be that you need to add both $uv$ and $vu$ to connect $q$ to everything since a path from $q$ through $e$ has to connect $q$ to one of the vertices $u$ or $v$ first. If $q$ is connected to $u$, then $vu$ is redundant, and if $q$ is connected to $v$, then $uv$ is redundant. So, the probability that the graph is $q$-connected only depends on the probabilities of including the edges $uv$ and $vu$ separately, not the probability of including both at the same time.

Given two functions that produce the same probabilities of removing each directed edge, the probability that the graph is $q$ connected does not change as you change the probabilities one edge at a time to convert one function to the other.

  • $\begingroup$ Very nice proof! $\endgroup$ – Sam Hopkins Dec 13 '15 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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