Cliques in random graphs 论文

摘要

Let 0 < p < 1 be fixed and denote by G a random graph with point set , the set of natural numbers, such that each edge occurs with probability p , independently of all other edges. In other words the random variables e ij , 1 ≤ i < j , defined by are independent r.v.'s with P ( e ij = 1) = p , P ( e ij = 0) = 1 − p . Denote by G n the subgraph of G spanned by the points 1, 2, …, n. These random graphs G, G n will be investigated throughout the note . As in (1), denote by K r a complete graph with r points and denote by k r ( H ) the number of K r 's in a graph H . A maximal complete subgraph is called a clique. In (1) one of us estimated the minimum of k r ( H ) provided H has n points and m edges. In this note we shall look at the random variables the number of K r 's in G n , and the maximal size of a clique in G n .