Complete Graphs and Bipartite Graphs in a Random Graph

Random graphs, or more precisely the Erdos-Renyi random graph model, is a major tool for modeling complex networks. The most distinctive property of a random graph is inarguably the threshold phenomenon. In this paper, we study the threshold phenomenon for the existence of a complete graph and distribution of complete bipartite graphs in random graphs using Markov's inequality and indicator functions.We review basic theorems in graph theory and random graphs. A graph is denoted by G(W,E), where the elements of W are the vertices of the graph G and the elements of E are its edges. A random graph is a graph where vertices or edges or both are determined by some random procedure. In the 1980's, Bollobas showed that every non-trivial monotone increasing property in a random graph has a threshold. Graphs of a size less than this threshold have a low probability to have the property, but graphs with a size larger than this threshold are almost guaranteed to have the property. This is known as a phase transition.For such random graphs denoted by G(n,p), where n is the number of vertices of the graph G and p is the probability of an edge between any two vertices is present, we present a proof of the threshold probability that a random graph contains a complete graph, K-d, which occurs at p = n(-2/d-1). A calculation of the probability distribution for a random graph to contain a complete bipartite graph K-r,K-s as an induced subgraph is also presented which exhibits a global maximum at p = 2rs/r(r-1) + s(s-1) + 2rs.