Probability and Combinatorics Seminar: Random planar graphs

  • Date: –18:15
  • Location: Ångströmlaboratoriet, Lägerhyddsvägen 1 4006 or Zoom meeting https://uu-se.zoom.us/j/67720169564, pwd first six digits of Pi after the decimal point
  • Lecturer: Clément Requilé
  • Organiser: Matematiska institutionen
  • Contact person: Paul Thévenin
  • Seminarium

Abstract:

A graph is labelled when its vertex set is {1,...,n}, and planar when it admits an embedding on the sphere. A random (labelled) planar graph is a graph chosen uniformly among all planar graphs on n vertices. We would like to study its properties as n goes to infinity. However, the planarity constraint makes it difficult to mimic the classical methods used in the study of the Erdős-Rényi random graph.

An alternative is to rely on asymptotic enumeration via generating functions and analytic combinatorics.

The starting point is a decomposition of graphs according to their connected components developed by Tutte in the 60's to study planar maps (fixed embeddings of planar graphs), and which can be extended to encode parameters of interest.

In this talk I will present several results about some families of planar graphs, in particular in the cubic (3-regular), 4-regular, and bipartite cases. We will discuss the behaviour of various parameters in the random setting and explain how some of them can be encoded via the Ising and Potts models.

If time permits, I will also try to highlight some limitations of this method and where can a more probabilistic viewpoint hopefully help.