## Answer To Test Your Intuition (4)

Let G be a graph and u and v two vertices.

(1) Let H be a random graph where every edge of G is chosen with probability ½. Let p be the probability that there is a path between u and v in H.

(2) Let T be a random orientation of the graph G. Namely, every edge {x,y} is directed from x to y with probability ½ and otherwise it is directed from from y to x. Let q be the probability that there is a directed path from u to v in T.

What is the relation between p and q?

Answer: p=q

This is an old theorem of Colin McDiarmid:

Colin McDiarmid, General Percolation and random graphs, Adv. Appl. Prob. 13, 40–60 (1981). (The paper at Jstor)

see also:

Svante Linusson, A note on correlations in randomly oriented graphs, Preprint 2009, arXiv:0905.2881.

I heard about it from Svante who learned about Colin’s result from Jeff Kahn. (A bunch of us are hanging now at the Mittag-Leffler Institute.)

Thanks all for the interesting discussion! James Martin has also guessed one possible correct generalization.

This entry was posted in Probability, Test your intuition and tagged , . Bookmark the permalink.

### 1 Response to Answer To Test Your Intuition (4)

1. pierre says:

Thanks for the puzzle.

The McDiarmid paper also mentions the probability that the resulting graph has a Hamiltonian cycle. Let p be this probability under (1) and q be this probability under (2). The paper says

p <= q

I wonder if its also true that

2 p <= q,

since every undirected cycle can be oriented into two directed cycles.