比利时vs摩洛哥足彩
,
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
****************************