##### Department of Mathematics,

University of California San Diego

****************************

### Computer Science Seminar

## Benny Sudakov

#### UCLA

## The phase transition in random graphs -- a simple proof

##### Abstract:

In this talk we show how analyzing basic Depth First Search algorithm leads to a simple proof of the two most classical results about random graphs: 1. The result of Erdos-Renyi that the random graph $G(n,p)$ experiences sharp phase transition around $p=1/n$. For $p=(1-\epsilon)/n$, all connected components of $G(n,p)$ are typically of size $O(\log n)$, while for $p=(1+\epsilon)/n$, with high probability there exists a connected component of size linear in n. 2. The result of Ajtai-Komlos-Szemeredi that in the supercritical regime $p=(1+\epsilon)/n$, random graph typically contains a path of linear length. Joint work with M. Krivelelvich

Host: Jacques Verstraete

### May 15, 2013

### 11:00 AM

### CSE 1202

****************************