A RANDOM GRAPH MODEL

 A RANDOM GRAPH MODEL 

LEMMA:1.1

A random graph G_(n,p), given that its number of edges is m, is equally likely to be one of the (((n¦2))¦m) graph that have m edges.

Proof:

Let G_0  be any labelled graph with m edges. Then since

{G_(n,p)= G_0  }⊆{|E_(n,p) |=m}

We have 

P(G_(n,p)= G_0 |E_(n,p) |=m)=  (P(G_(n,p)= G_0 |E_(n,p) |=m))/(P(|E_(n,p) |=m))  

=  P(G_(n,p)= G_0 )/((|E_(n,p) |=m) )

=  (p^m (1-p)^((n¦2)-m ))/(〖(((n¦2))¦m)  p〗^m (1-p)^((n¦2)-m ) )

= (((n¦2))¦m)^(-1).

Thus G_(n,p) conditional on the event {G_(n,p) has m edges} is equal in distribution to G_(n,m), the graph chosen uniformly at random from all graphs with m edges. Obviously, the main difference between those two models of random graph is that in G_(n,m.)we choose its number of edges, while in the case of G_(n,p) the number of edges is the binomial random variable with the parameters and p. intuitively, for large n random graphs G_(n,m) and G_(n,p)  should behave in similar fashion when the number of edges m in G_(n,m) equals or is “ close” to the expected number of edges of G_(n,p)ie., when m= (n¦2)p≈(n^2 p)/2,

Or, equivalently, when the edge probability in G_(n,p)

p≈2m/n^2 .

Throughout the book, we will use the notation f≈g to indicate that f=(1+o(1)g, where the o(1) term will depend on some parameter going to 0 or ∞.

We next introduce a useful “coupling techniques” that generates the random graph G_(n,p)in two independent steps. We will then describe a similar idea in relation to G_(n,m). Suppose that p_1<p and p_2 is defined by the equation

1-p=(1- p_1 )(1-p_2 ),

Or equivalently,  

p= p_1+p_2-p_1 p_2.

Thus, an edge is not included in G_(n,p) if it is not included in either of G_(n,p1)  or G_(n,p2.)

 It follows that 

G_(n,p)=G_(n,p1)  ∪ G_(n,p2.)

Where the two graph G_(n,p1)  ,G_(n,p2.)   are independent .so when we write

G_(n,p1)  ⊆ G_(n,p),

We mean that the two graph are coupled so that G_(n,p) is obtained from G_(n,p1)by super imposing it with  G_(n,p2.)and replacing eventual double edges by a single one. 

We can also couple random graph G_(n,m_1 )  or G_(n,m_2.)  where m_2≥ m_1 via 

G_(n,m_2 )  = G_(n,m_1 )∪H.

Here H is the random graph on vertex set [n] that has m = m_2  -m_1 edges chosen uniformly at random from ((([n])¦2))⁄E_(n,m_1 ) 

Consider now a graph property P defined as a subset of the set of all labelled graphs on vertex set [n], i.e.,,P ⊆2^((n¦2) ). 

 For example, all connected graphs (on n vertices), graphs with a Hamiltonian cycle, graphs containing a given subgraph, planar graphs, and graphs with a vertex of given degree form a specific “graph property”.

We will state below two simple observations which show a general relationship between G_(n,m) and G_(n,p)in the context of the probabilities of having a given graph property P. The constant 10 in the next lemma is not best possible, but in the context of the usage of the lemma, any constant will suffice.

LEMMA:1.2 

Let  P be any graph property and p=  m⁄((n¦2)  where m=m(n)→∞,(n¦2)  →∞,then,for all large n,)

P(G_(n,m)∈P)≤10m^(1⁄2) P(G_(n,m)∈P)

Proof:

By the law of total probability, 

P(G_(n,m)∈P)= ∑_(k=0)^((n¦2))▒P(G_(n,m)∈P)  (|E_(n,p) |=k P(E_(n,m)=k))

= ∑_(k=0)^((n¦2))▒〖P(G_(n,m)∈P)P(E_(n,m)=k)     1.4〗

≥P(G_(n,m)∈P)P(E_(n,m)=m)

To justify (1.4), we write

P(G_(n,m)∈P)|E_(n,p) |=k)=  (P(G_(n,m)∈P)∧|E_(n,p) |=k) )/P(|E_(n,p) |=k ) 

= ∑_█(G∈P@|E(G)|=k)▒(p^k (1-p)^(N-K))/((N¦K)  p^k (1-p)^(N-K) )

= ∑_█(G∈P@|E(G)|=k)▒1/((N¦K)  )

=P(G_(n,k)∈P)

Next recall that the number of edges |E_(n,p) | of a random graph G_(n,p) is a random variable with the binomial distribution with parameters(n¦2)  and p. Applying Stirling’s formula:

 k!=(1+o(1)) (k/e)^k √2πk,                                          (1.5)

 Putting, 

N= (n¦2),we get,after substituting (1.5)for the factorials in (N¦m),

 P(|E_(n,p) |=m )=(N¦m) p^m (1-p)^((n¦2)-m)  

=   (1+o(1))  ((N)^k √2πN p^m (1-p)^(N-m)  )/(m^m (N-m)^(N-m)  √(2πm(N-m) ))  (1.6)

    =   (1+o(1)) √(N/2πm(N-m) ,)

  hence,                   P(|E_(n,p) |=m )≥1/(10√m),  

so,       P(G_(n,m)∈P)≤10m^(1⁄2) P(G_(n,m)∈P)

we call a graph property P monotone increasing if G∈P implies G+e∈P, ie., adding an edge e to a graph G does not destroy the property. For example, connectivity and Hamilton city are monotone increasing properties. A monotone increasing property is non – trivial if the empty graph K ̅_n∉P and the complete graph K_n∈P.

P monotone decreasing if G∈P implies G-e∈P, ie., adding an edge e to a graph G does not destroy the property. Properties of a graph not being connected or being planar are examples of monotone decreasing graph properties. Obviously, a graph property Pis monotone increasing if and only if its complement is monotone decreasing. Clearly not all graph property monotone. For example, having at least half of the vertices having a given fixed degree d is not monotone.

From the coupling argument it follows that if P is monotone increasing property then, whenever p<p^' or m<m^',

P(G_(n,p)∈P)≤P(G_(n,p^' )∈P),   (1.7)

P(G_(n,m)∈P)≤P(G_(n,m^' )∈P),   (1.8)

Respectively, for monotone increasing graph properties we can get a much a better upper bound on  P(G_(n,m)∈P), in terms of P(G_(n,m)∈P),than that given by lemma1.2.

LEMMA:1.3 

 Let P be an monotone increasinggraph property and p=  m⁄(N ,then,for all large n and p=o(1)such that Np,N(1-p)/〖(NP)〗^(1/2)→∞,)

P(G_(n,m)∈P)≤3P(G_(n,p)∈P)

Proof:

Suppose P be an monotone increasing and   p=m/N  N=(n¦2)then, 

P(G_(n,m)∈P)= ∑_(k=0)^N▒P(G_(n,k)∈P)  P(E_(n,p)=k)

≥ ∑_(k=0)^N▒〖P(G_(n,m)∈P)P(E_(n,m)=k)     〗

However, by the coupling property we know that k≥m.

P(G_(n,k)∈P)≥P(G_(n,m)∈P)

The number of edges |E_(n,p) |  in〖 G〗_(n,p)  has the binomial distribution with parameters N, p. hence, 

P(G_(n,p)∈P)≥ P(G_(n,m)∈P) ∑_(k=m)^N▒P(|E_(n,p) |=k ) 

=P(G_(n,m)∈P) ∑_(k=m)^N▒u_(k   ) (1.9)

u_k=(N¦K)  p^k (1-p)^(N-K)

Applying Stirling’s formula:

 u_m=(1+o(1))  (N^N p^m (1-p)^(N-m)  )/(m^m (N-m)^(N-m) (2πm)^(1/2) )   =((1+o(1)))/(2πm)^(1/2)       

furthermore,ifk=m+t where 0≤t≤m^(1/2)  then,

 u_(k+1)/u_k =  (N-k)p/(k+1)(1-p) =  (1- t/(N-m))/(1+(t+1)/m  )≥exp⁡{-t/(N-m-t)-(t+1)/m},

After using lemma23.1(a), (b) to obtain the inequality. And our assumptions on N, p to obtain to second.

It follows that for 0≤t≤m^(1/2),

u_(m+t)≥((1+o(1)))/(2πm)^(1/2)   exp{-∑_(s=0)^(t-1)▒〖s/(N-m-s)-(s+1)/m〗}

≥exp⁡{-t^2/2m-o(1)}/(2πm)^(1/2)   ,

Where we have used the fact that m=o(N).

It follows that 

∑_(k=m)^(m+m^(1/2))▒u_k ≥((1+o(1)))/(2πm)^(1/2)  ∫_(x=0)^1▒〖e^(-x^2⁄2) dx〗≥1/3

 And lemma follows from (1.9).

Lemmas 1.2 and 1.3 are surprisingly applicable. In fact, since the G_(n,p)model is computationally easier to handle than G_(n,m), we will repeatedly use both lemmas to show that P (G_(n,p)∈P)  → 0 implies that P (G_(n,m)∈P) → 0 when n → ∞. In other situations, we can use a stronger and move widely applicable result. The theorem below, which we state without proof, gives precise conditions for the asymptotic equivalence of random graph G_(n,p)  and G_(n,m).it is due to Lucak [557].