Threshold functions in Erdos-Renyi Random Graphs: Part 1

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 {n} vertices. Each of the {\binom{n}{2}} edge is occupied with probability {p} independently. We will denote the law of such random graph as {ER_n(p)}. Usually we also vary {p} with {n} and typically write {p} as {p_n}.

We start with few definitions.

Definition 1 (Montone Property) A property {\mathcal{A}} of a graph is a collection of graphs that has some prescribed features. A property {\mathcal{A}} is said to be monotone if adding edges does not violate it.

Continue reading