In these series posts, we will study threshold functions of various properties in random graphs. We will also try to see what happens in the critical case. Since usually the desired properties have a dependent structure, tools like Chen-Stein Method will be useful in the critical case.
Networks are ubiquitous in our surroundings. World-wide web, social networks, food webs, protein interactions etc are all real life examples of networks. In order to study properties of these networks, several random graph models have been proposed. The most classical model for a random graph is the Erdos-Renyi Random Graph model.
In Erdos Renyi Random graph, there are vertices. Each of the edge is occupied with probability independently. We will denote the law of such random graph as . Usually we also vary with and typically write as .
We start with few definitions.
Definition 1 (Montone Property) A property of a graph is a collection of graphs that has some prescribed features. A property is said to be monotone if adding edges does not violate it.