0-1 laws for maps

A class of finite structures has a 0-1 law with respect to a logic if every property expressible in the logic has a probability approaching a limit of 0 or 1 as the structure size grows. To formulate 0-1 laws for maps (i.e., embeddings of graphs in a surface), it is necessary to represent maps as lo gical structures. Three such representations are given, the most general be ing the full cross representation based on Tutte's theory of combinatorial maps. The main result says that if a class of maps has two properties, rich ness and large representativity, then the corresponding class of full cross representations has a 0-1 law with respect to first-order logic. As a coro llary the following classes of maps on a surface of fixed type have a first -order 0-1 law: all maps, smooth maps, 2-connected maps, 3-connected maps, triangular maps, 2-connected triangular maps, and 3-connected triangular ma ps. (C) 1999 John Wiley & Sons, Inc.