Anusch Taraz: Limiting probabilities for properties of random planar graph

Over the last ten years, typical properties of random planar graphs have been studied extensively. It is known that, maybe somewhat surprisingly, not all natural properties satisfy a zero-one law; for instance, the probability for a random planar graph to be connected tends to 0.96325...

However, we show that for every property that can be expressed in monadic second order logic (which is first order logic enriched with quantification over vertex sets), there exists a limiting probability for random planar graphs. This can be generalized to graphs that are embeddable on a given surface (provided that we weaken MSO to FO), and here we can prove that the limiting probabilities do not depend on the choice of the surface.

Moreover, in the case of random planar graphs, we are also able to give an explicit description of the closure of the set of all limiting probabilities: they turn out to be the union of 108 disjoint intervals.

This is joint work with Peter Heinig, Tobias Mueller and Marc Noy.