Math 581E

Random Graphs

Chris Hoffman

Autumn 2005, Monday/Wednesday/Friday, 12:30

During the quarter we will consider three main types of random graphs.

  1. Erdos-Renyi subgraphs of the complete graph
  2. Albert-Barabassi preferential attachment models, and
  3. percolation.
One of the main themes of the quarter will be that of phase transitions. For Erdos-Renyi graphs we will study the phase transitions that occur when a "large" cluster in the random graph emerges and when the random graph becomes connected. We will also study the diameter of random graph and the largest clique size. For the preferential attachmentment models we will focus on the distribution of the degree of the edges, the diameter of the graph as well as aplications. In percolation we will show the existence of a phase transition, exponential decay of cluster size below the critical parameter and uniqueness of the infinite cluster.

Prerequisites: Knowledge of elementary probability, and mathematical maturity at the level of a graduate student in mathematics.