Zero-one laws for minor-closed classes of graphs
Presented by Prof. Marc NOY
Type: Oral presentation
Track: Plenary Talk
Let G be a class of labelled graphs endowed with a probability distribution on the set G(n) of graphs in G with n vertices. We say that a zero-one law holds in G if every first order graph property holds or does not hold in G(n) with probability 1 as n goes to infinity. Many zero-one laws have been established for the classical binomial model G(n,p) of random graphs, as well as for other classes such as random regular graphs. In this talk we present a zero-one law for connected graphs in a class of graphs G closed under taking minors (edge deletion and contraction) with the property that all forbidden minors of G are 2-connected. Interesting classes of this kind include trees and planar graphs. A zero-one law does not hold for non-necessarily connected graphs in G as, for instance, the probability of having an isolated vertex tends to a constant strictly between 0 and 1. For arbitrary graphs in G we prove a convergence law, that is, every first order property has a limiting probability. These results hold more generally for properties expressible in monadic second order logic. On the other hand, given a fixed surface S, we prove a convergence law in first order logic for the class of graphs embeddable in S (this class is closed under minors but the forbidden minors are not necessarily 2-connected). Moreover, we prove that the limiting probabilities of first order properties do not depend on S. (Joint work with Peter Heinig, Tobias Müller and Anushc Taraz).