Paul Erdos discovered that probabilistic methods are often useful in tackling problems in extremal graph theory. So, instead of constructing a graph with some given properties, one takes a random graph (in some appropriately defined probability space) and proves that with positive probability it has the required properties. Typical applications include Erdos' lower bound on the Ramsey number, as well as his proof of the existence of graphs of arbitrarily large girth and chromatic number. 

The basic random graph models are G(n,m) and G(n,p). In the first model one choses a graph on n vertices and m edges uniformly at random. In the second model, we have a graph on n vertices in which every possible edge is present independently at random with probability p. There are many other interesting models. For example random regular graphs in which an n-vertex d-regular graph is chosen uniformly at random; random Cayley graphs in which generating sets from a group are chosen according to some probability distribution; preferential attachment graphs in which vertices of high degree are more likely to be joined to new vertices; and many others.

Sample publications:

• D. Christofides and K. Markström, Random Latin square graphs, Preprint.
  

• D. Christofides and K. Markström, Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales, Random Structures Algorithms, 32: 88-100, 2008.
• D. Achlioptas, A. Coja-Oghlan. Algorithmic barriers from phase transitions. Proc. 49th FOCS (2008) 793-802.
• Michael Behrisch, A. Coja-Oghlan, Mihyun Kang. The order of the giant component of random hypergraphs. Random Structures and Algorithms 36 (2010) 149-184.