CSE 525 (Spring 2019): HW #1

Due: Thurs, Apr 11, 11:59pm

Problem 1: The probabilistic method

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.]

Problem 2: The second moment method

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 .]