Details

Autor(en) / Beteiligte

• Bender, Edward A.
• Compton, Kevin J.
• Richmond, L. Bruce

Titel

0-1 laws for maps

Ist Teil von

• Random structures & algorithms, 1999-05, Vol.14 (3), p.215-237

Ort / Verlag

New York: John Wiley & Sons, Inc

Erscheinungsjahr

1999

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 logical structures. Three such representations are given, the most general being 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, richness and large representativity, then the corresponding class of full cross representations has a 0–1 law with respect to first‐order logic. As a corollary 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 maps. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 215–237, 1999