(Not such a set)

consider a planar set A with the following property. In every direction, the distance between the two parallel lines that touch A from both sides is the same! Must A be a circle? Continue reading

4 Replies

(Not such a set)

consider a planar set A with the following property. In every direction, the distance between the two parallel lines that touch A from both sides is the same! Must A be a circle? Continue reading

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

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?**

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