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.
For example, if , then clearly property is monotone as if you add any edge to such graph, the resultant graph will still belong to property . However is not monotone.
Let us start with an easy obvious theorem related to monotone property.
Theorem 2 Suppose . Let and . Then, for any monotone we have,
Proof: Let us define . Clearly . Consider independent graphs and . Without loss of generality assume and are defined on the same set of vertices. Consider . We claim that . Clearly the edges are added independently and
Thus . By monotonicity of ,
This completes the proof.
Definition 3 (Threshold function) is a threshold function for a given property of a random graph following law if
Example: The threshold function for existence of an edge is . One can check that if
and if , for any , eventually. Hence
Since is arbitrary we have which implies when .
Before progressing further we will address the following questions.
- What about the existence of threshold function? Given any monotone property , do such a function always exist?
- What are the threshold functions for other well known properties like existence of triangles, cliques, cycles etc? How do we guess them?
- What happens at the critical case, i.e., when behaves like ?
Answer to question 1 is affirmative. The exact result will be stated and proved in Theorem 2. In regard to question 2, threshold function can be first guessed by making the appropriate expectation converge to a non zero number and then it can be verified by probability computations. However, in this series of posts we will primarily focus on question 3.