Marc Noy: Limiting probabilities of FO and MSO properties of random graphs from minor-closed classes
Given a minor-closed class of graphs G, and a graph property A expressible in first order or monadic second order logic, we study the limiting probability that A is satisfied for graphs in G according to the uniform distribution. We obtain several zero-one laws and convergence laws, and a non-convergence result for graphs embeddable in a surface of positive genus. The proofs are based on Ehrenfeucht-Fraïssé games, asymptotic enumeration and topological graph theory.
Based on joint work with P. Heinig, T. Müller, A. Taraz, and with A. Atserias, S. Kreutzer.
