Notes on the group Steiner tree proof

A few notes on the rounding proof (and how to complete it):

1. When you round down the $x_e$ values to the power of $2$ below it, note that you might violate the minimality of the solution: e.g., if an edge has value $x_e=3/4$, and has two children of value $x_{e1}=1/2$ and $x_{e2}=1/4$, then rounding down would give $x{ʹ}_e=1/2$ but would maintain $x{ʹ}_{e1}=1/2$ and $x{ʹ}_{e2}=1/4$.
   
   This kind of situation would cause some concern if we want to "merge" edges with identical values in the last step of the preprocessing: how would we merge $e$ and $e1$ in this case? The answer is: we would just "contract" the edge $e1$, and hence any children of $e1$ would now become children of $e$. The key observation is the random process on this new contracted graph connects the same set of leaves to the root as on the original uncontracted graph, since $x{ʹ}_{e1}=x{ʹ}_e$.
   
   (Aside: the procedure is fairly robust, so you could alter the procedure and add a step to regain the minimality. Or you could just forget about the last "merging" step entirely. Note that we now no longer have a tree of "height" $\log \mid g\mid$, and the closing arguments would now change slightly.)
   
   
2. The argument to compute $\Delta$: suppose the height of the "merged" tree is $H$.
   
   For some vertex $u\in g$, let us first show that ${\Delta }_u=\sum _{w\sim u}Pr[E_u\cap E_w]\le O\left(H\right)\times x{ʹ}_u$. Summing this over all $u\in g$ gives us $O\left(H\right)$, since the $x{ʹ}_u$'s sum up to at most $1$, and hence completes the proof.
   
   For any $w\in g$, let $e$ be the lowest edge shared by the path from $u$ to the root, and the path from $w$ to the root. A moment's thought tells us that $Pr\left[E_u\right]=x{ʹ}_u$, and $Pr[E_w\mid E_u]=x{ʹ}_w/x{ʹ}_e$ $Pr[E_w\mid E_u]=x{ʹ}_u/x{ʹ}_e$. Hence, $Pr[E_u\cap E_w]=(x{ʹ}_{u}x{ʹ}_w/x{ʹ}_e)$.
   
   Now, if we sum over all $w$ such that the paths from $u$ to root, and $w$ to root have the edge $e$ as their least common ancestor edge as above. Now use the fact that $\sum _{suchw}x{ʹ}_w\le O\left(x{ʹ}_e\right)$, since all the flow going to such $w$'s must have been supported on the edge $e$ before rounding down. Hence, the sum of $Pr[E_u\cap E_w]$ over all the relevant $w$ for some edge $e$ is $O\left(x{ʹ}_u\right)$.
   
   Finally, the tree is of height $H$, which means there are at most $H$ such terms, giving us $O\left(H\right)x{ʹ}_u$ as claimed.
   
   
3. Aravind Srinivasan has some notes on Janson's inequality: it explains how the "simple" structure of the events $E_i$ and (the independence of the random variables determining these events) allow us to prove such a strong inequality. Joel Spencer also has slides on the proof: in fact, he states it in exactly the form we needed today, with his "bad" events $B_i$ being our "good" events $E_v$!
   

If anything else was unclear, please post questions, comments, or clarifications!