Giant component with Depth First Search |

I just finished reading a short paper of Michael Krivelevich and Benny Sudakov, two leading experts in probabilistic combinatorics, which appeared in Arxiv about a month ago [1]. It is a simple proof of the classical result that the random binomial graph $G(n,p)$ exhibits a phase transition around $p=\frac{c}{n}$ . When $c<1$ then the largest component has size $O(\log{n})$ and when $c>1$ the largest component has linear size with high probability (whp) i.e., they hold with probability tending to 1 as n grows to infinity. The proof is elegant and based on exploring the component structure using Depth First Search. Recall that DFS labels vertices with three different labels,explored, unexplored, active. The key idea for the hard part of the paper $p=\frac{1+\epsilon}{n},\epsilon>0$ [I call the other case easy since the branching process technique results in an easy argument too] is that at any time the set of unexplored vertices $T$ and the set of explored vertices $S$ cannot be both large since there are no edges between them (hence we get a probability for this event equal to $(1-p)^{|S||T|}$ ). Therefore, the set of active vertices on the stack $U$ (which form a path) must at some point be large since $|U|=n-|T|-|S|$ . Notice that $U$ is a path, and therefore we obtain that the longest path is $\Omega(n)$ . This is the simplest proof of a result of fundamental importance that I know of so far. Also, gives other hard results (e.g., the longest path in a random graph) as simple corollaries. Can it get even simpler? I doubt it, but who knows?! 🙂