Cubic Graphs Embeddable on Surfaces

3 May 2016
Michael Mosshammer

In the theory of random graphs, the behaviour of the typical largest component was studied a lot. The initial results on G(n,m), the random graph on n vertices and m edges, are due to Erdős and Rényi. Recently, similar results for planar graphs were obtained by Kang and Łuczak.

In the first part of the talk, we will extend these results on the size of the largest component further to graphs embeddable on the orientable surface S_g of genus g>0 and see how the asymptotic number and properties of cubic graphs embeddable on S_g are used to obtain those results. Then we will go through the main steps necessary to obtain the asymptotic number of cubic graphs and point out the main differences to the corresponding results for planar graphs. In the end we will give a short outlook to graphs embeddable on surfaces with non-constant genus, especially which results generalise and which problems are still open.

  • Combinatorial Theory Seminar