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.

Introduction

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.

For example, if {\mathcal{A}=(\mbox{graphs with at least one triangle})}, then clearly property {\mathcal{A}} is monotone as if you add any edge to such graph, the resultant graph will still belong to property {\mathcal{A}}. However {\mathcal{B}=(\mbox{disconnected graphs})} is not monotone.

Let us start with an easy obvious theorem related to monotone property.

Theorem 2 Suppose {p_1\le p_2}. Let {G_1\sim ER_n(p_1)} and {G_2\sim ER_n(p_2)}. Then, for any monotone {\mathcal{A}} we have,

\displaystyle P(G_1 \in \mathcal{A}) \le P(G_2\in \mathcal{A})

Proof: Let us define {p_0=\dfrac{p_2-p_1}{1-p_1}}. Clearly {p_0\in [0,1]}. Consider independent graphs {G_0\sim ER_n(p_0)} and {G_1 \sim ER_n(p_1)}. Without loss of generality assume {G_0} and {G_1} are defined on the same set of {n} vertices. Consider {G=G_0\cup G_1}. We claim that {G\sim ER_n(p_2)}. Clearly the edges are added independently and

\displaystyle \begin{aligned} P(\mbox{an edge }E\mbox{ is vacant in }G) & = P(E\mbox{ is vacant in }G_0)P(E\mbox{ is vacant in }G_1) \\ & = (1-p_0)(1-p_1) \\ & = (1-p_1-p_2+p_1)=1-p_2 \end{aligned}

Thus {G\stackrel{d}{=}G_2\sim ER_n(p_2)}. By monotonicity of {\mathcal{A}},

\displaystyle P(G_1 \in \mathcal{A}) \le P(G_0\cup G_1 \in \mathcal{A})= P(G_2\in \mathcal{A})

This completes the proof. {\square}

Definition 3 (Threshold function) {t(n)} is a threshold function for a given property {\mathcal{A}} of a random graph {G} following law {ER_n(p_n)} if

  1. {P(G \in \mathcal{A})\rightarrow 0} if {\displaystyle \frac{p_n}{t(n)}\rightarrow 0}
  2. {P(G \in \mathcal{A})\rightarrow 1} if {\displaystyle \frac{p_n}{t(n)}\rightarrow \infty}

Example: The threshold function for existence of an edge is {t(n)=n^{-1}}. One can check that if {np_n \rightarrow 0}

\displaystyle P(G\mbox{ has an edge}) \le E(\mbox{Number of egdges})=np_n \rightarrow 0

and if {np_n \rightarrow \infty}, for any {k \in \mathbb{N}}, {p_n>\dfrac{k}{n}} eventually. Hence

\displaystyle \limsup_{n\rightarrow\infty} P(G\mbox{ has no edges})=\limsup_{n\rightarrow \infty} (1-p_n)^n \le \limsup_{n\rightarrow\infty} \left(1-\frac{k}{n}\right)^n=e^{-k}

Since {k} is arbitrary we have {P(G\mbox{ has no edges}) \rightarrow 0} which implies {P(G\mbox{ has an edge}) \rightarrow 1} when {np_n \rightarrow \infty}.

Before progressing further we will address the following questions.

  1. What about the existence of threshold function? Given any monotone property {\mathcal{A}}, do such a function always exist?
  2. What are the threshold functions for other well known properties like existence of triangles, cliques, cycles etc? How do we guess them?
  3. What happens at the critical case, i.e., when {p_n} behaves like {t(n)}?

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.

Reference: https://www.math.cmu.edu/~af1p/MAA2005/L2.pdf

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s