Monthly Archives: June 2009

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: Continue reading

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?

Continue reading

Social Choice Talk

condorcetable0

I took part in a workshop celebrating the publication of a new book on Social Choice by Shmuel Nitzan which took place at the Open University. (The book is in Hebrew, and an English version is forthcoming from Cambridge University Press.) It was a very interesting event and all the lectures were excellent. I thought of blogging about my lecture.

The main part of the lecture was about the four old theorems in the table above and about what should replace the two question marks. The left side of the table deals with properties of the majority voting rule for binary preferences. The right side of the table is about general voting rules. On the top tight is the famous Arrow Impossibility Theorem. The table is filled by two theorems I proved in 2002 (in this paper) and it now looks like this: Continue reading