Colouring Rules for Finite Trees
and Probabilities of Monadic Second Order Sentences


Alan R. Woods

University of Western Australia

Algorithms Seminar

March 10, 1998

[summary by Cyril Chabaud]

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
Given a set of colouring rules applying to the vertices of any finite rooted tree, we study the asymptotic behaviour of the probability that an n vertex tree has a given root colour. These results will prove that the fraction of labelled or unlabelled rooted trees satisfying any fixed monadic second-order sentence converge to limiting probabilities.



1   Introduction

Given a finite rooted tree and a set of k colours, the vertices are coloured from the leaves to the root according to a set of colouring rules, namely a function h:Nk {1,2,...,k}. The colour assigned to a vertex depends only on the number C1,...,Ck of its immediate predecessors having colour 1,...,k.

Example 1   Let
h(Cblack,Cwhite)=


black if Cblack is even
white if Cblack is odd
be a set of colouring rules. From the definition of h, the leaves of the following tree are coloured black and we find its root colour is black.

Note that the root of a finite rooted tree is black iff the number of its vertices is odd, with the set of colouring rules defined above.

Let n[i] be the fraction of n vertex labelled trees with root colour i.
Theorem 1   Let [i]=limn n[i] and the corresponding Cesro limit
_
 
[i]=
 
lim
n
1
n
n
m=1
m[i].
For any set of colouring rules h, _[i] exists for all colours i=1,...,k and either
  1. _[i]>0 or
  2. $ c>1 such that n[i]<c-n for all sufficiently large n.
Although the existence of [i] implies the existence of _[i] in general, the converse needs additional conditions to be true.

2   Applications to Logic

2.1   First Order Logic

There exists an analogous result for first order sentences about a graph. The language in which these sentences are written contains the usual quantifiers, parentheses and connectives with an additional predicate symbol E(x,y) expressing the fact that vertex x and vertex y are joined by an edge.

Example 2   The following expression is a first order logic sentence expressing ``every vertex has degree 2'':
" x$ y1$ y2( y1=y2" z(E(x,z) z=y1 z=y2)).
Fagin [3], Glebskii, Kogan, Liogon'kii and Talanov [4] have proved the following result
Proposition 1   Let n(j) be the fraction of n vertex graphs with property j. For every first order sentence j about a graph, (j)=limn n(j) exists and (j)=0 or 1.
That the only possible values are 0,1 is a consequence of the fact that graphs have no roots.

2.2   Monadic Second Order Logic

The situation for monadic second order sentences about a rooted tree is quite different since the language provides a constant symbol R denoting the root, and it can handle sets of vertices using second order variables.

Determining the satisfiability of a monadic second order sentence j of rank r reduces to finding the root colour of a rooted tree T for a particular system of colouring rules. Results arising from Compton's method of components [2] establish that if j is a sentence of rank r, then there exists sentences y1,...,yk of rank r such that:
  1. Every finite rooted tree satisfies exactly one yi;
  2. Every j of rank r is equivalent to i Syi for some set S.
If T is a rooted tree that has component trees T1,..., Tm that satisfy sentences yi1,...,yim, then there exists a unique i such that T satisfies yi, and this particular i can be interpreted as the root colour of T. (For details see [8]).

2.3   Boolean Formulas

Assume we have M boolean variables x1,...,xM. Then the colours turn out to be the 22M boolean functions Yi. The existence of the limiting probability [i] is stated in the following theorem:
Theorem 2   Let n[i] be the fraction of formulas of size n which compute the boolean function Yi, i{1,...,22M}. Then limnn[i]=[i] exists and [i]>0.

3   Enumeration of Rooted Trees

3.1   Labelled Rooted Trees

We use generating functions methods to determine _[i] in the labelled case. Note that a similar proof can be done for the unlabelled case.

Let T(x) denote the generating function for labelled rooted trees:
T(x)=t1x+
t2
2!
x2+
t3
3!
x3+... +
tn
n!
xn+
where ti is the number of i vertex labelled rooted trees. Since this structure is decomposable, we easily obtain a functional equation on T(x) and find:
T(x)=xeT(x).
Hence, using Lagrange inversion we get:
T(x)=x+
2
2!
x2+
32
3!
x3+... +
nn-1
n!
xn+.
The radius of convergence of this series is r=1/e, x=r is the only singularity on the circle of convergence, where there exists a constant h1 such that T(x) behaves like 1+h1(r-x)1/2. One can then apply Darboux's theorem and find that tn behaves asymptotically like tn~ Cr-nn-3/2.

3.2   Labelled Trees with a Particular Root Colour

Let Ti(x) be the generating function for labelled trees with root colour i,
Ti(x)=x
 
M1,...,Mk
h(M1,...,Mk)=i
T
M1
 
1
(x)
M1!
T
Mk
 
k
(x)
Mk!
.
To find yi=Ti(x) we have to solve the system:
{yi=gi(x,y1,...,yk)}
 
i{1,...,k}
where gi(x,y1,...,yk)=x
 
M1,...,Mk
h(M1,...,Mk)=i
y
M1
 
1
M1!
y
Mk
 
k
Mk!
.

4   Cesro Probabilities

To determine probability _[i] we use a partial converse of the following Abelian theorem:
Theorem 3   Let b(x)=n 0bnxn, c(x)=n 0cnxn and r be the radius of convergence of b(x). If limncn/bn= and n 0 bnrn diverges then:
 
lim
xr-
c(x)/b(x)=.
Setting c(x)=Ti'(x) and b(x)=T'(x), we find that the conditions above are satisfied since limxr -T'(x)=. The result is given by the following Tauberian theorem:
Theorem 4  [Compton [1]]   Let bn~ Cna, a>-1, bn 0 for n 0, cn=O(bn). If
 
lim
xr -
c(x)/b(x)=,
where r is the radius of convergence of b(x)=n 0 bnxn then:
_
 
=
 
lim
n
1
n
n
M=1
cM
bM
=.
Since
T
'
 
i
(x)=
gi
x
(x,Ti(x),..., Tk(x))+
k
j=1
T
'
 
j
(x)
gi
yj
(x,Ti(x),...,Tk(x)),
when xr -, we have
_
 
[i]=
k
i=1
gi
yj
_
 
[j]  for   i=1,...,k.
Thus, the _[i] are linearly dependent, as the following matrix relation shows:











_
 
[i]


_
 
[k]











=W(r)











_
 
[i]


_
 
[k]











where W(r)=











g1
y1
g1
yk


 

gk
y1
gk
yk











,
yielding the linear system: (Id-W(r)) T[_[i]_[k]]=0. Here W(r) is a stochastic matrix, and from the theory of nonnegative matrices, the rank of (Id-W(r)) is k-1. Consequently, the linear system above has a unique solution satisfying _[i]+... + _[k]=1.

We associate with W(r) its dependency digraph D. Namely, we put a directed edge from vertex j to vertex i iff gi/ yi(r,T1(r),...,Tk(r ))>0. In other words, this directed edge exists iff $ C1$ Ck (Cj>0 h(C1,...,Ck)=i)
Property 1   There is a unique strong component S in D with the property that, for every colour j, there is a directed edge in D from j to some colour in S. S is called the principal component of D.
This property is the key point to prove the first part of theorem 1:
Theorem 5   For any system of colouring rules, _[i] exists for all colours i. Moreover, if S is the principal component of dependency digraph D then
_
 
[i]>0 i S.

Proof. From the property above there exist A(x) and B(x) such that
W(x)=

A(x) C(x)
  B(x)

and A(x) is an irreducible matrix. Matrix A(x) is indexed by S={1,...,s} after renumbering. Since 1 is the largest eigenvalue of A(r), from Perron-Frobenius theory (see for instance [7]) there is a unique normalized solution m1,...,ms of





m1


ms





=A(r)





m1


ms





with m1>0,...,ms>0. Then we just show that 1 cannot be an eigenvalue of B(r) and prove that [m1,...,ms,0,...,0] is a normalized eigenvector of W (r).
The colours that do not belong to the principal component S have probabilities that converge exponentially to zero, as the following theorem shows:
Theorem 6   For any system of colouring rules, if iS then there is some c>1 such that n[i]<c-n. (The same property holds in the unlabeled case).

Proof.[Sketch of proof] We prove that for each i such that iS, Ti(x) has an analytic continuation on the circle of convergence of T(x), meaning that the radius of convergence of Ti(x), ri, is greater than r. Since n[i]=tni/tn, this leads to desired result. For details, see [8].


5   Existence of [i]

We examine here a sufficient condition to ensure the existence of [i] rather than just _[i]. The existence of [i] is conditioned by the presence of a unique singularity on the circle of convergence of Ti(x), indeed:
Lemma 1   Let A(x) be the irreducible block of matrix W(x). If det(A(x)-I) 0 for all xr on the circle |x|=r then [i] exists for all i S. The probabilities [1],...,[s] are all strictly positive and form the unique normalized solution of





[1]


[s]





=A(r)





[1]


[s]








Proof. See [8]
If we look again the first example, clearly [1] and [2] do not exist since series Tblack(x) and Twhite(x) have two singularities on the circle |x|=r.

The next theorem is a sufficient criterion on colouring rules to guarantee the convergence of n[i]:
Theorem 7   Suppose that for each i{1,...,k} there exists at least one pair of rules of the following sort, namely: there exists C1>1,...,Ck>1 such that h(C1,...,Ci-1,...,Ck)=h(C1,...,Ci,...,Ck). Then [i] exists and [i]>0 for all i S.

Proof.[Sketch of proof] We prove that det(I-W(x)) 0 for all |x|r except x=r, and that each Ti(x) has at most x=r as a singularity on the circle |x|=r.


6   Open Problems and Extensions

A partial answer to this last question is that n(j) converges, and it has been given in the labeled case for g=0 by Compton and Shelah; Woods (also in the unlabeled case) [9]; Luczak and Thoma [5].

References

[1]
Compton (Kevin J.). -- Application of a Tauberian theorem to finite model theory. Archiv fr Mathematische Logik und Grundlagenforschung, vol. 25, n°1-2, 1985, pp. 91--98.

[2]
Compton (Kevin J.). -- A logical approach to asymptotic combinatorics. II. Monadic second-order properties. Journal of Combinatorial Theory. Series A, vol. 50, n°1, 1989, pp. 110--131.

[3]
Fagin (Ronald). -- Probabilities on finite models. Journal of Symbolic Logic, vol. 41, n°1, 1976, pp. 50--58.

[4]
Glebskii (Y. V.), Kogan (D. I.), Liogon'kii (M. I.), and Talanov (V. A.). -- Range of degree and realizability of formulas in the restricted predicate calculus. Kibernetika (Kiev), vol. 5, n°2, 1969, pp. 17--28. -- [Engl. Transl. Cybernetics, vol. 5, 142--154 (1972)].

[5]
Luczak (Tomasz) and Thoma (Lubos). -- Convergence of probabilities for the second order monadic properties of a random mapping. Random Structures & Algorithms, vol. 11, n°3, 1997, pp. 277--295.

[6]
McColm (Gregory L.). -- MSO asymptotics on random free trees (and random strings). -- 1996. Preprint.

[7]
Minc (Henryk). -- Nonnegative matrices. -- John Wiley & Sons Inc., New York, 1988, Wiley-Interscience Series in Discrete Mathematics and Optimization, xiv+206p. A Wiley-Interscience Publication.

[8]
Woods (Alan R.). -- Coloring rules for finite trees, and probabilities of monadic second order sentences. Random Structures & Algorithms, vol. 10, n°4, 1997, pp. 453--485.

[9]
Woods (Alan R.). -- Counting finite models. The Journal of Symbolic Logic, vol. 62, n°3, 1997, pp. 925--949.

This document was translated from LATEX by HEVEA.