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.

Test your intuition (1), test your intuition (2), test your intuition (3), answer to (3)

One thought on “Answer To Test Your Intuition (4)

  1. pierre

    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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s