Thresholds in random graphs

This thesis follows the work of Erdos and Renyi, on the evolution of random graphs. We consider several models of random graphs and present results relating to the asymptotic existence of certain invariant graph theoretic properties, such as connectedness and planarity.; In Chapter 1 we describe a dynamic load sharing algorithm for a cellular telephone network with n transceiver towers. We model this network via a hypergraph and show how a random sequence of calls within the network can be modelled by a random bipartite graph. We show that an admissible sequence, i.e. a sequence of calls, each of which is accepted by the network, is equivalent to the existence of a matching of the random bipartite graph and find thresholds on the number of calls for admissibility.; In Chapter 2 we study the $Gk-out$ model for random graphs. In this model, each vertex randomly connects “out” to k other vertices. We find connectivity, planarity and maximal degree properties of the model. We also extend the model to non-integer values of k and find connectivity and planarity properties for this model as well.; In Chapter 3 we use combinatorial techniques for counting the number of connected random graphs in $Gk-out$ to solve number theoretic problems related to determining the asymptotics of where w = (w₁, w₂, w₃, ) is a sequence of numbers called weights and the sum is taken over all k-part compositions t₁ + t ₂ + + t_k of n. We note that although this problem has been recently solved using methods of complex analysis, our combinatorial approach is of interest due to its relative simplicity.