What is the Complexity of a Random Map?
Kevin Compton
University of Michigan
Algorithms Seminar
March 29, 1999
[summary by Gilles Schaeffer
^{1}]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
This talk presents a joint work with Ed Bender and Bruce
Richmond [
2].
1 Introduction
A class of structures obeys a 01 law if every firstorder sentence
has an asymptotic probability of 0 or 1 within the class. Techniques
used to prove 01 laws are closely related to averagecase analyses of
algorithms. For example, Abiteboul, Compton and Vianu
[1] showed that the 01 law for random relational
structures (which includes random graphs with constant edge
probabilities) can be used to give an averagecase analysis of certain
database query optimizations. However, the random graph model is not a
very realistic model for databases, so it is useful to examine other
structures. A map, or embedding of a graph into a surface of fixed
genus, may be a better model of certain kinds of geometric databases.
Here we show that the class of random maps in surface of fixed genus
obeys a 01 law. The proof is based on game strategies and keeping
track of anchors.
2 First Order Logic on Maps
A map is an embedding of a connected graph G in a surface S
such that all components of S\ G are simply connected regions
called faces. Maps are considered up to homeomorphisms of
the surface taking vertices to vertices, edges to edges and faces to
faces.
Like graphs, maps with a finite number of edges can be given various
combinatorial representations. We shall use the cross
representation, introduced by Tutte [9]: each edge is viewed
as a fat ribbon with four corners or crosses (see Figure 1),
and three fixpoint free involutions are defined on the set A_{c} of
crosses. The first two, g and d, relate two by two the
four adjacent crosses of each edge, g along faces and d
along vertices. The last one, t, relates pairs of crosses sharing
an incidence between a face and a vertex. The structure á
A_{c},g,d,tñ completely defines the map: for instance,
vertices, faces and edges are respectively described by the orbits of
the subgroups ág,tñ, ád,tñ
and á g,dñ.
Figure 1: Illustration of the action of the three involutions on
the four corners or crosses of edges, and two different drawings
of the same map on the torus.
Now let us consider the vocabulary S_{1} consisting of a set of
constants and the binary relations G, D and T. A map
á A_{c},g,d,tñ can then be seen as a
structure over S_{1}, where the constants are taken in A_{c} and
the binary relations are interpreted as the respective graphs of the
three involutions. Our interest is in properties expressible by first
order formulas on these structures. In order to allow quantification
on vertices and faces, and not only on crosses, we enrich the
vocabulary with two other sets of constants (for vertices and faces)
and two other binary relations I and J, respectively interpreted
as the incidence relations between vertices and crosses and between
crosses and faces. For convenience the binary relation E is also
added to describe crosses that belong to the same edge (although E
could be expressed in terms of G, D and T). Let
S be this extended vocabulary.
For instance, the following sentence (i.e., formula without free
variable) is satisfied by maps containing a cycle of length three:
$ v_{1},v_{2},v_{3}
$ c_{12},c_{21} c_{12}¹ c_{21}Ù E(c_{12},c_{21})Ù
I(v_{1},c_{12}) Ù I(v_{2},c_{21}) 
Ù
$ c_{13},c_{31} c_{13}¹ c_{31}Ù E(c_{13},c_{31})Ù
I(v_{1},c_{13}) Ù I(v_{3},c_{31}) 
Ù
$ c_{23},c_{32} c_{23}¹ c_{32}Ù E(c_{23},c_{32})Ù
I(v_{2},c_{23}) Ù I(v_{3},c_{32}). 
In the study of asymptotic 01 laws for random structures (here
maps), we consider a class of structures C on S,
with the uniform measure µ_{n} on the set C_{n} of
structures of size n (here maps with n edges). Our interest is in the limit when n goes to
infinity of
µ_{n}(f)=µ_{n}({ AÎ C_{n}
 A=f}).
If this limit exists, it is called the asymptotic probability of f
and denoted µ(f).
A class of structures has an asymptotic first order 01 law if all
firstorder sentences have an asymptotic probability of either 0 or 1.
3 01 Laws and the EhrenfeuchtFraïssé Game
A classical logical tool to prove 01 laws is the
EhrenfeuchtFraïssé game: essentially this game is used to show
that if two structures have the same kinds of local
substructures then they satisfy the same firstorder sentences of
given quantifier rank.
The quantifier rank of a formula is the maximal number of
stacked quantifiers in the formula (e.g. the previous example
has rank 5). Given two maps A and B, we write
Aº_{m} B if they satisfy the same formulas of
rank at most m. Remark that the number of inequivalent formulas of
given rank over S is finite, so that the number of equivalence
classes for º_{m} is finite, a fact that we shall use in Section 4.
The following proposition is only a matter of rephrasing:
Proposition 1
A class of structure C has an asymptotic first order 01
law if and only if for all m there exists an equivalence class
E_{m} of º_{m}, such that


µ_{n} ({ AÎ C_{n}
AÎ E_{m}})=1.

Therefore, in order to prove a 01 law, one should define, for all
m, a large enough class E'_{m} in which maps cannot be
distinguished by rank m formulas. Here come the EhrenfeuchtFraïssé game in play: There are two players, Spoiler and
Duplicator, playing m rounds on two structures (here maps)
A and B. Spoiler starts each round
by picking an element (a cross, a vertex or a face) in one of the maps
and Duplicator responds by picking an element of the same
kind in the other map. These 2m elements are viewed as
interpretations d_{1}^{ A},...,d_{m}^{ A} and
d_{1}^{ B},...,d_{m}^{ B} of some fresh constants
d_{1},...,d_{m}. After m rounds, Duplicator wins if the
two extended structures over SÈ{d_{1},...,d_{m}} cannot be
distinguished by atomic formulas (i.e., without
quantifier).
Theorem 1 [Fraïssé, Ehrenfeucht]
Let A and B be two structures over
S. Duplicator has a winning strategy in the mround
game if and only if Aº_{m} B.
Hence we look for a large enough class E'_{m} on which we
can describe a winning strategy for Duplicator. As suggested
by the classical approach, we want to consider the class of structures
that contain many copies of all possible kinds of local
substructures. In such a structure Duplicator will always
be able to find a local substructure on which to imitate
Spoiler.
4 Distance and Richness in Maps
In order to formalize the idea of local substructures for maps
we are led by existing results on random maps to consider:

Distances in the derived map
 a proper notion of distance can be
defined (which is somewhat more complicated than distance on graphs)
so that all relations of S are local (i.e., they are
false as long as elements are at a distance greater than, say, two).
 Planar balls
 the substructures we consider are the finite radius
balls (in the sense of the previous distance) which are planar.
While it is natural to define a distance and consider finite radius
balls, the planarity assumption may be surprising. It comes from the
theory of random maps: many families of maps (on surfaces of given
genus) have the large representativity property, asserting that
for a given d, in almost all maps, the balls of diameter d are
planar submaps. All the families C of maps we will
consider then have the following richness property:
Property 1 [Richness]
Let P be a fixed planar map occurring as a submap of some map in
our family C, and k be a nonnegative integer. Then
µ(" a_{1},...,a_{k} $ a submap isomorphic to
P not containing a_{1},...,a_{k})=1
where a_{1},...,a_{k} range over all vertices, faces and crosses.
At each round of the game, our Duplicator will need to use
richness to choose an element with a neighborhood isomorphic to the
neighborhood of the element chosen by Spoiler.
Unfortunately, given a diameter d, there are infinitely many
possible planar balls with this diameter, so that the richness
property is not sufficient. Instead of requiring Duplicator
to choose an isomorphic neighborhood, we will content with a
neighborhood that is indistinguishable by rankmsentences. As
there are only a finite number of º_{m}equivalence classes of
planar balls with given diameter d, Duplicator will only
have to make his choice in a finite set of representative
B_{1},..., B_{k}.
We are now in a position to define the class of maps E'_{m}
on which Duplicator has a winning strategy: let m be fixed,
and consider the set of maps such that, for each B_{i} and
a_{1},...,a_{k} as above, there exists a submap isomorphic to
B_{i} avoiding a_{1},...,a_{k}. As there are finitely many
B_{i}, Property 1 implies that this set
E'_{m} is large enough, i.e., satisfies


µ_{n}({ AÎ C_{n}
AÎ E'_{m}})=1. 
Therefore we need to prove that
Duplicator has a winning strategy for all couples of maps in
E'_{m}.
5 Winning Strategy and the Good Use of Anchors
The strategy for Duplicator associates a
security zone to each chosen element with the following requirements:

The security zone of an element e chosen at round i
contains all elements at distance at most 2^{mi+1} of e.
 The security zones of the two elements chosen at each round are
indistinguishable (i.e., belong to the same
º_{m}equivalence class).
Suppose now Spoiler chooses element e at round i; there
are two cases:

if no previously chosen element is in the security zone
Z of e, then Duplicator chooses any element
e' in the other map with a security zone Z'
indistinguishable from Z, and disjoint from previously
chosen zones. In this case, e and e' are their own anchor. The
assumption on E' assures that this is always
possible.
 if a previously chosen element f is in the security zone of
e, then there is a chance that they interact. In this case, let
g be the anchor of f. It is easy to see that e belongs to the
security zone of g, because the sizes of the zones are
exponentially distributed. Therefore Duplicator can choose
the image e' of e in the zone Z' associated to the
security zone Z of g. The anchors of e and e' are
respectively set to be g and g'.
At the end of the game, elements in A are either too far
away to interact or share the same anchor. In both cases the
corresponding elements in B will satisfy the same atomic
formulas.
6 Conclusion
Richness properties have been proved for many families of rooted maps
by Bender et al.
[4, 3, 5, 6, 7]. Thanks
to the work of Richmond and Wormald [8] these results
hold as well for unrooted maps. Using the previously described
machinery it implies 01 laws for the following families of maps on a
surface of given genus: all maps, smooth maps, 2connected maps,
3connected maps, triangular maps, 2connected triangular maps and
3connected triangular maps.
References
 [1]

Abiteboul (S.), Compton (K. J.), and Vianu (V.). 
Queries are easier than you though (probably). In Proceedings of
the ACM Symposium on Principle of Database Systems. pp. 3242. 
Association for Computing Machinery, 1992.
 [2]

Bender (E. A.), Compton (K. J.), and Richmond (L. B.). 
01 laws for maps. Random Structures & Algorithms,
vol. 14, n°3, 1999, pp. 215237.
 [3]

Bender (E. A.), Gao (Z.), and Richmond (L. B.). 
Submaps of maps. I. General 01 laws. Journal of
Combinatorial Theory. Series B, vol. 55, n°1, 1992,
pp. 104117.
 [4]

Bender (E. A.), Gao (Z.), and Richmond (L. B.). 
Almost all rooted maps have large representativity. Journal of
Graph Theory, vol. 18, n°6, 1994, pp. 545555.
 [5]

Bender (E. A.), Gao (Z.), Richmond (L. B.), and Wormald (N. C.). 
Asymptotic properties of rooted 3connected maps on surfaces. Australian Mathematical Society. Journal. Series A. Pure Mathematics and
Statistics, vol. 60, n°1, 1996, pp. 3141.
 [6]

Bender (E. A.) and Richmond (L. B.). 
Submaps of maps. III. kconnected nonplanar maps. Journal of Combinatorial Theory. Series B, vol. 55, n°1,
1992, pp. 125132.
 [7]

Gao (Z.). 
A pattern for the asymptotic number of rooted maps on surfaces. Journal of Combinatorial Theory. Series A, vol. 64, n°2,
1993, pp. 246264.
 [8]

Richmond (L. B.) and Wormald (N. C.). 
Almost all maps are asymmetric. Journal of Combinatorial Theory.
Series B, vol. 63, n°1, 1995, pp. 17.
 [9]

Tutte (W. T.). 
Graph theory. 
AddisonWesley Publishing Co., Reading, Mass., 1984,
Encyclopedia of Mathematics and its Applications, vol. 21, xxi+333p.
With a foreword by C. St. J. A. NashWilliams.
 1
 See also the summary on the same subject by
Frédéric Chyzak in the 19951996 edition.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.