Problem 1: The probabilistic method

Consider an undirected graph $G=(V,E)$ with $n=|V|$. An all pairs multi-flow in $G$ is way of sending one unit of flow between every pair of vertices.

More precisely: For every pair $u,v \in V$, let $\mathcal{P}_{uv}$ denote the collection of undirected, simple $u$-$v$ paths in $G$. Let $\mathcal{P} = \bigcup_{u,v \in V} \mathcal{P}_{uv}$. An all-pairs multi-flow is a mapping $\Lambda : \mathcal{P} \to [0,\infty)$ such that for every $u,v \in V$ with $u \neq v$,

$$\sum_{\gamma \in \mathcal{P}_{u,v}} \Lambda(\gamma) = 1\,.$$

The flow is integral if for every $u,v \in V$ with $u \neq v$, it holds that $\Lambda(\gamma)=1$ for precisely one path $\gamma \in \mathcal{P}_{u,v}$.

For $v \in V$, define the amount of flow passing through vertex $v$ by:

$$\Lambda[v] = \sum_{\gamma \in \mathcal{P} : v \in \gamma} \Lambda(\gamma)\,.$$

Finally, define the energy of the flow $\Lambda$ as $\mathcal{E}(\Lambda) = \sum_{v \in V} \Lambda[v]^2\,.$

(a) Use the probabilistic method to show that given any all-pairs multi-flow $\Lambda$, there exists an integral all-pairs multi-flow $\Lambda'$ such that $\mathcal{E}(\Lambda') \leq \mathcal{E}(\Lambda) + n^3\,.$ You will need to use the fact that if $X$ and $Y$ are independent random variables, then $\mathbb{E}[XY]=\mathbb{E}[X]\cdot \mathbb{E}[Y]$.

(b) Use part (a) and the crossing number inequality (proved in Lecture 1) to show the following: There is a constant $c > 0$ such that if $G$ is a planar graph, then every all-pairs multi-flow $\Lambda$ in $G$ has

$$\mathcal{E}(\Lambda) \geq c n^4\,.$$

[Hint: You should relate an integral all-pairs multi-flow in $G$ 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 $2n$ users in two groups $A$ and $B$ with $|A|=|B|=n$. For every distinct pair of users $i$ and $j$, the pair $\{i,j\}$ are friends independently with probability $p$ if they are in the same group, and probability $q$ if they are in different groups. A loner is a user $i$ that has no friends.

Let $\mathcal{L}$ denote the event that there exists a loner. Prove that if $p + q \gg \frac{\ln n}{n}$, then $\Pr[\mathcal{L}] \to 0$ and if $p+q \ll \frac{\ln n}{n}$, then $\Pr[\mathcal{L}] \to 1$.

[As in Lecture 2, the notation $f(n) \gg g(n)$ means that $\lim f(n)/g(n) = \infty$.]