A~0--1 Law for Planar Maps

A class~$C$ of combinatorial structures has a~$0-$1 law if, for every property~$P$ expressible in first-order logic, the probability that~$P$ holds in a random structure of size~$n$ in~$C$ approaches a limit of either~0 or~1 as~$n$ goes to infinity. There are many classes known to have a~0--1 law, e.g. the class of all graphs. These results have applications in problems such as expected time analyses for database query optimization algorithms and approximation algorithms for~$\cal N\cal P$-optimization problems. Often the tools from probability theory and enumeration theory needed to prove a~\hbox{0--1} law are simple, but occasionally more sophisticated results are needed. We prove a~0--1 law for random maps on a surface of fixed genus; the proof relies on difficult enumeration results of Bender, Gao and Richmond.

This is joint work with Ed Bender and Bruce Richmond.