FraïsséEhrenfeucht Games and Asymptotics
Alan Woods
University of Western Australia
Algorithms Seminar
March 23, 1998
[summary by Julien Clément and JeanMarie Le Bars]
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).
Abstract
FraïsséEhrenfeucht games are played on two structures, where a
structure might, for example, consist of a unary function mapping a finite
set into itself. Via generating series and a Tauberian theorem,
it is possible to investigate the asymptotic probability of having a
winning strategy
for such a game, when it is played using a fixed structure,
and a random structure of size n, with n going to infinity.
Actually for unary
functions this gives a convergence law for all properties of the
structure which are definable in monadic second order logic.
1 Introduction
We consider here structures A based upon a set A and
finitely many relations E_{j} of finite arity
A= 
< 
A,E_{1}(x,y),E_{2}(x),E_{3}(x,y,z), ... 
> 
. 
A classical example is a set of
vertices V and an edge relation E(x,y) so that
V=<V,E>
describes a graph. We can also think of simple structures
A=<A,f>
consisting
of a finite set A and a
unary function mapping this set into itself (see
fig. 1). This unary function induces a binary relation
F(x,y) Û f(x)=y.
Figure 1: Graphical representation a structure A=<[29],f>
(where the unary function f maps {1,2,..., 29} on itself).
In order to use generating functions (see the last section) we need to
translate a decomposition
property of structures to the generating functions: this
will be done through the disjoint union.
Let us consider two structures
A= 

A,E 

, ... 

and
B= 

B,E 

, ... 

. 
If A Ç B=Ø and each E_{i}^{ A} has the same
arity as E_{i}^{ B}, the disjoint union is defined as
the structure whose domain is the union of the domains and
whose relations are the unions of the corresponding relations
A ú`½ B= 

A È B, E 

È
E 

,... 

. 
A class of structures has components if each structure can be uniquely
decomposed into disjoint unions of structures (called component
structures) from some components
classes.
For structures A=<[n],f>, where [n] denotes
{1,...,n} and f is a unary function, one can define
component classes relative to the size of the unique loop present
in each connected component of the graph of f.
From this point of
view,
for the structure
A of figure 1, we see three components.
The first component of A
consists of two component structures in the first
component class (the class corresponding to loops of size one
i.e. fixed elements of f).
The two other components consist in two single component structures and
are respectively in the component classes 2 and 7 (relatively to the
size of the loop).
Let us define the rank r(j) of a formula j in the
context of the second order logic (or MSO logic for short) inductively by:

If j has no quantifiers, then r(j)=0;
 If j is ¬ s, then r(j)=r(s);
 If j is obtained from s_{1}, s_{2} by the
application of a binary propositional connective (e.g., if j is
s_{1} Ù s_{2}, s_{1} « s_{2}, etc.) then
r(j)=max{r(s_{1}),r(s_{2})};
 If j is of the form
" v s,
$ v s,
" V s or
$ V s for some variable v, V, then
r(j)=r(s)+1.
A sentence is a formula that has no free variables and
is a
property
of a structure.
The key observation is that there are only finitely many inequivalent
sentences x_{1}, ..., x_{m} of rank r.
Hence every structure A satisfies exactly one of the
sentences (also of rank r)
y_{1}=x_{1} Ù ... Ù x_{m},
y_{2}=¬ x_{1} Ù ... Ù x_{m},...,
y 

=¬ x_{1} Ù ... Ù ¬ x_{m}. 
Given a rank r (and implicitly the sentences
y_{1},...,y_{2}^{m}), for each i Î {1,...,2^{m}}
we define the class of structures which satisfies
y_{i}.
These classes can be viewed as equivalence classes of
FraïsséEhrenfeucht games.
2 FraïsséEhrenfeucht Games
The goal is to see whether or not
we can distinguish two structures in a r moves
game.
The game is played with two structures
A=<A,E_{1}^{ A}, ...> and
B=<B,E_{1}^{ B}, ...>.

At move i,
Spoil chooses A or B (let's say
B) and one of the following is satisfied

an element b_{i} Î B or
 a subset B_{i} Í B.

Dupe responds on the other structure ( A here)
choosing one of the following

an element a_{i} Î A or
 a subset A_{i} Í A.
Dupe wins if after r moves the map {a_{i},...}
® {b_{i},...} taking a_{i} ® b_{i} is an isomorphism
of the induced substructures of < A,A_{j},...>,
< B,B_{j},...> on these sets.
We write
A º_{r} B
Û
Dupe has a winning strategy.
Note that there is no ex æquo (either Spoil or
Dupe has a winning strategy).
These games are the main tools for proving
the following theorems:
Theorem 1
Let us consider some structures
A_{1}, A_{2}, B_{1}, B_{2}, one has
A_{1} º_{r} B_{1},
A_{2} º_{r} B_{2}
Þ
A_{1} ú`½ A_{2} º_{r}
B_{1} ú`½ B_{2}.
Theorem 2
For every structures A and B, one has
A º_{r} B iff
there exists i such that A = y_{i} and
B = y_{i},
where the sentences y_{i}'s are defined in the first section.
Corollary 1
There are only finitely many º_{r} classes.
Another problem consists in determining
the º_{r} class of a given structure
A. It is solved if we know
the number of component structures
lying in each º_{r} component class (or color if we
think of º_{r} as a colouring).
On figure 2,
we have 5 component classes C_{1},..., C_{5}
relative to the º_{3} relation
(namely triangles, squares,
cycles of odd length strictly greater
than 3, cycles of even length strictly greater than 4).
The numbers of component structures in each component of
the structure A are respectively m_{1}=5,m_{2}=1,m_{3}=0,m_{4}=4.
Figure 2: The components classes C_{1},..., C_{4}
relative to º_{3}
(left), the structure A and its four
components (right).
3 Counting Structures with Components
We count either

the number a_{n} of labelled
structures with n elements, or
 the number b_{n} of unlabelled
structures with n elements
(which is, also, the number of
nonisomorphic structures with n elements).
Here we focus on counting labelled structures. So the exponential
generating series
will prove highly useful.
Indeed, for a structure A= G ú`½
H,
letting a(x), h(x) and g(x) be
the corresponding exponential generating
series, we write
a(x)=g(x) h(x) or
a(x)= 

, 
whether G and H
are in different classes or not.
By induction
the exponential
generating series associated to
A= G^{(1)} ú`½ ... ú`½
G^{(m)} the disjoint union of m structures
G^{(1)},..., G^{(m)}, is
a(x)=g^{(1)}(x) ··· g^{(m)}(x) or
(x)= 

, 
respectively if G^{(1)},..., G^{(m)} are all
from different classes or all in the same class.
Hence the generating series a(x) for structures with components in
the component class C
is
a(x)=1+c(x)+ 

+
...+ 

+···=e^{c(x)}, 
where c(x)=å_{n} c_{n}/n!x^{n} (c_{n} is the number of
labelled structures in the component class C with n
elements).
There is a connection with monadic second order logic due to Compton
[2].
Let us consider the component classes (relatively to º_{r}) C_{1},
..., C_{k} (so that the
generating series for whole component class is c(x)=å_{i=1}^{k}
c_{i}(x)).
There is a unique ktuple (m_{1},...,m_{k})
associated to each structure A, where m_{i} is the number
of component structures of A lying in the ith component
class C_{i}.
Moreover for two structures A and
B
(with ktuples (m_{1},...,m_{k}) and (n_{1},...,n_{k})),
there is an integer R=R(r) such that if " i Î
{1,...,k} either m_{i}=n_{i} or m_{i},n_{i} ³ R, then
A º_{r} B (plainly speaking,
too many component structures of
the same component class prevent to distinguish structures).
Hence for a sentence j of rank r, the number
of labelled structures A such that
A = j depends only on
m_{1},...,m_{k} where m_{i} Î {0,1,...,R1,¥} is the
number of components in C_{i} (¥ means anything
equal to at least R=R(r)).
Considering the exponential generating series
a_{j}(x)=åa_{n}^{j}/n! where a_{n}^{j} the number
of labelled structures with n elements satisfying j,
we can write
where S is finite and c_{i}(x)^{¥}/¥! denotes
å_{m=R}^{¥}c_{i}(x)^{m}/m!=
e^{c}_{i}^{(x)}å_{m=0}^{R1} c_{i}(x)^{m}/m!.
The series a_{j}(x) is a finite sum of very similar terms.
It is enough just
to consider a series of the form
This formula means that a structure A
satisfying j has exactly
m_{i} components in the class i for i Î {1,...,t} and any
number of components in the other classes. We want to know
a_{n}^{j} or equivalently
µ_{n}(j)=a_{n}^{j}/a_{n}, the fraction of structures
of size n satisfying j. We are also interested in
the asymptotic probability
µ_{j}=lim_{n ® ¥}
µ_{n}(j), when this limit exists.
It is Compton's idea to use partial converses Tauberian lemmas to get
limit laws for µ_{n}.
Here is a sample theorem whose proof is based on such lemmas.
Theorem 3
For any class with components, if
a_{n}/n! ~ C t^{n}/n^{a} and
c_{n}/n!=O(t^{n}/n) (with a> 1)
then
µ(j)=lim_{n® ¥} µ_{n}(j)
exists for all MSO sentences j and is
equal to a_{j}(r)/a(r).
Due to known results about a_{n} and c_{n} for structures with one unary
function, we have also
Corollary 2
The asymptotic probability µ_{j} always exists with one
unary function.
References
 [1]

Compton (Kevin J.). 
Application of a Tauberian theorem to finite model theory. Archiv für Mathematische Logik und Grundlagenforschung, vol. 25,
n°12, 1985, pp. 9198.
 [2]

Compton (Kevin J.). 
A logical approach to asymptotic combinatorics. II. Monadic
secondorder properties. Journal of Combinatorial Theory. Series A,
vol. 50, n°1, 1989, pp. 110131.
 [3]

Fagin (Ronald). 
Probabilities on finite models. Journal of Symbolic Logic,
vol. 41, n°1, 1976, pp. 5058.
 [4]

Glebskii (Ju. V.), Kogan (D. I.), Liogon'kii (M. I.), and Talanov
(V. A.). 
Volume and fraction of satisfiability of formulas of the lower
predicate calculus. Kibernetika (Kiev), vol. 5, n°2,
1969, pp. 1727. 
English translation Cybernetics, vol. 5 (1972), pp. 142154.
 [5]

Woods (Alan). 
Counting finite models. The Journal of Symbolic Logic,
vol. 62, n°3, September 1997, pp. 925949.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.