Local limit theorem in random graphs and graphs on non-constant surfaces

Thesis

The thesis is split into two parts. In the first part we prove a local limit theorem for the number of appearances of the complete graph on four vertices, K₄, in the Erdös-Rényi Random graph G(n, p) for p in (0, 1) a fixed constant. The proof of this is based on bounding the characteristic function of the number of K₄ in G(n, p) by using different conditioning arguments for different ranges of t. The second part treats classes of graphs embeddable in either an orientable surface of Euler genus at most g(n), denoted by G^(g(n)), or non-orientable surface of Euler genus at most g(n), denoted by H^(g(n)), for different non-constant functions g(n). We first find bounds on the sizes of these classes and prove that as long as g(n) = o(n/log^3(n)), the classes G^(g(n)) and H^(g(n)) both have a growth constant equal to the planar graph growth constant. As long as g(n) = O(n/log(n)) it is further shown that the classes G^g(n) and H^(g(n)) are both small. We then go on to show which properties graphs in these graph classes commonly display, such as giving bounds on the number of edges, faces, pendant vertices, the maximum degree and the probability of connectedness.

Authors: Saller, S

• DOI: 10.5287/ora-dqynkdop6
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: non-constant surfaces; growth constant; random graphs; graphs on surfaces; graph classes
• Subjects: Random graphs