Keith Briggs

This page was last modified 2013-05-12  


·maths notes « 
·ex libris 
·site map 


cliques in G(n,p)

G(n,p) is the random graph model in which there are n nodes and each possible edge appears independently with probability p.

The clique number of a graph is the size of a largest complete subgraph. Computing the clique number is NP-complete.

In Modern graph theory, page 230, Bollobás shows that the clique number of G(n,p) as n→∞ is almost surely d or d+1, where d is the greatest natural number such that binomial(n,d)*p^binomial(d,2)≥log(n). We have 1≤d<n and d=2*log(n)/log(1/p)+O(loglog(n)).

How accurate is this formula when n is small? I did some simulations to check this.

G(100,p) cliques

G(200,p) cliques

G(500,p) cliques

This website uses no cookies. This page was last modified 2013-05-12 10:17 by Keith Briggs.