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