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 Erdos–Renyi 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.