Consider an undirected graph with . An all pairs multi-flow in is way of sending one unit of flow between every pair of vertices.
More precisely: For every pair , let denote the collection of undirected, simple - paths in . Let . An all-pairs multi-flow is a mapping such that for every with ,
The flow is integral if for every with , it holds that for precisely one path .
For , define the amount of flow passing through vertex by:
Finally, define the energy of the flow as
(a) Use the probabilistic method to show that given any all-pairs multi-flow , there exists an integral all-pairs multi-flow such that You will need to use the fact that if and are independent random variables, then .
(b) Use part (a) and the crossing number inequality (proved in Lecture 1) to show the following: There is a constant such that if is a planar graph, then every all-pairs multi-flow in has
[Hint: You should relate an integral all-pairs multi-flow in to a drawing of the complete graph in the plane.]
Consider the following simple model for a social network: There are users in two groups and with . For every distinct pair of users and , the pair are friends independently with probability if they are in the same group, and probability if they are in different groups. A loner is a user that has no friends.
Let denote the event that there exists a loner. Prove that if , then and if , then .
[As in Lecture 2, the notation means that .]