##### Department of Mathematics,

University of California San Diego

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

### Math 295 - Mathematics Colloquium

## Jeong Han Kim

#### Korea Institute for Advanced Study (KIAS)

## A tale of two models for random graph

##### Abstract:

Since Erdos-Renyi introduced random graphs in 1959, two closely related models for random graphs have been extensively studied. In the $G(n,m)$ model, a graph is chosen uniformly at random from the collection of all graphs that have n vertices and m edges. In the $G(n,p)$ model, a graph is constructed by connecting each pair of two vertices randomly. Each edge is included in the graph $G(n,p)$ with probability p independently of all other edges. Researchers have studied when the random graph $G(n,m)$ (or $G(n,p)$, resp.) satisfies certain properties in terms of $n$ and $m$ (or $n$ and $p$, resp.). If $G(n,m)$ (or $G(n,p)$, resp.) satisfies a property with probability close to 1, then one may say that a ``typical graphÃ¢ï¿½ï¿½Ã¢ï¿½ï¿½ with $m$ edges (or expected edge density $p$, resp.) on $n$ vertices has the property. Random graphs and their variants are also widely used to prove the existence of graphs with certain properties. In this talk, a well-known problem for each of these categories will be discussed. First, a new approach will be introduced for the problem of the emergence of a giant component of $G(n,p)$, which was first considered by ErdÃ…ï¿½sÃ¢ï¿½ï¿½RÃƒÂ©nyi in 1960. Second, a variant of the graph process $G(n,1), G(n,2), Ã¢ï¿½Â¦, G(n,m), Ã¢ï¿½Â¦$ will be considered to find a tight lower bound for Ramsey number $R(3,t)$ up to a constant factor. No prior knowledge of graph theory is needed in this talk.

Jacques Verstraete

### April 11, 2013

### 4:00 PM

### AP&M 6402

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