THE ENUMERATION OF PLANAR GRAPHS VIA WICK S THEOREM
MIHYUN KANG AND MARTIN LOEBL
Abstract. A seminal technique of theoretical physics called the Wick s theorem interprets the
Gaussian matrix integral of the product of the traces of powers of matrix M as the number of
labelled maps with a given degree sequence, sorted by their Euler characteristics. This leads to
map enumeration with results analogous to those obtained by more pedestrian combinatorial
methods. We first write down a proof of the correctness of the method and then we start
playing with it; in particular, we show that enumeration of the graphs embeddable on a given
2D surface (a seminal open problem of graph theory) may also be formulated by the matrix
integral machinery. Some of the most puzzling conjectures of discrete mathematics are related
to the notion of the Cycle Double Cover. We express the number of the graphs on at most N
vertices with a fixed Directed Cycle Double Cover as the matrix integral of an Ihara-Selberg-type
function.
Contents
1. Introduction 1
1.1. The motivation and the results 2
1.2. Acknowledgement 2
1.3. Gaussian integral 2
1.4. Gaussian matrix integral 3
1.5. Graphic interpretation 4
2. Gaussian matrix integral and planar fat graphs 7
3. Directed graphs 12
4. Even sets of directed edges 13
4.1. Cycle double cover conjectures 13
4.2. Calculations 14
5. Back to fat graphs 16
5.1. Extracting the planar graphs 17
References 19
1. Introduction

Let M be an N × N matrix and let f(M) = aI (ij)"I Mij be a polynomial in its entries,
I
where I ranges over a finite system of multisets of elements of N × N. The basis of the Wick game
is the following definition of < f >.
Definition 1.1. We let

< f > = aI < Mij > = aI < MpMq >,
I (ij)"I I P (p,q)"P
where P ranges over all partitions of I into pairs, and for p = (p1, p2), q = (q1, q2) we have
< MpMq > is non-zero only if p1 = q2 and p2 = q1 and in that case < MpMq > = 1/N.
Date: August 28, 2006.
2000 Mathematics Classification. Primary 05C30. Secondary 46T12, 81T18.
Key words and phrases: Gaussian matrix integral, Feynman diagram, planar maps, fat graphs, flows, cycle double
cover .
1
arXiv:math.CO/0605218 v1 9 May 2006
1.1. The motivation and the results. A seminal technique of theoretical physics called Wick s
theorem interprets < f > as the Gaussian matrix integral (see e.g. [3, 4, 5, 6, 7]). Principally
studied functions f are products of powers of the trace of Mk. For such functions f, < f > has
a useful graphic interpretation as the number of labelled maps with given degree sequence, sorted
by their Euler characteristics (these maps are the Feynman diagrams for the matrix integral).
This approach leads to the formulas for the numbers of labelled maps with given degree sequence
and the genus, which are analogous to the formulas obtained by more pedestrian combinatorics
method [2].
The purpose of this paper is two-fold. First we write down a complete proof of the correctness
of the Wick s theorem method. We were not able to find it in the literature and many discussions
with our  reserved colleagues of the discrete mathematics community make us believe that it is
not a waste of time.
Once the correctness is established, it is tempting to start playing with the method. In par-
ticular, a natural question is whether it may be applied as well to counting of the graphs which
are embeddable on a given 2D surface, say the plane. This has been a long-standing open problem
in the discrete enumeration community, solved only for plane and fairly recently by Giménez and
Noy [10].
We show in Theorem 4 that these enumeration tasks as well may be formulated as a matrix
integral (not solved so far).
On the way we encounter a pleasant surprise: the number of graphs on at most N vertices and
with a fixed directed cycle double cover is expressed as a matrix integral of an Ihara- Selberg- type
function (see Theorem 2).
1.2. Acknowledgement. We would like to thank Bojan Mohar for helpful discussions. M. L.
gratefully acknowledges the support of CONICYT via grant Anillo en Redes. M.K. is supported
by the Deutsche Forschungsgemeinschaft (DFG Pr 296/7-3).
The rest of section 1 expands [6].
1.3. Gaussian integral. Let us recall Gaussian integral and Gaussian matrix integral. We first
consider the case N = 1. For an arbitrary real function f, the standard Gaussian integral is
defined as

"
1 x2
2
(1) < f(x) > = " e- f(x)dx,
2Ä„ -"
where we abuse notation by a multiple use of the symbol <>. Note that < 1 > = 1. We are
in particular interested in a function of the form f(x) = x2n, where n is an integer. In order to
compute < x2n >, we introduce the so-call source integral < exs > for a given real s. Taking the
k-th derivatives of < exs > with respect to s and taking s = 0, we get

"
"k 1 x2 "k

2
< exs > = " e- exs dx

"sk s=0 "sk s=0
2Ä„
-"
"
1 x2
2
= " e- xkdx
2Ä„ -"
(2) = < xk > .
On the other hand the source integral becomes

"
1 x2
2
< exs > = " e- exsdx
2Ä„
-"
"
(x-s)2
1 s2
2 2
= " e- + dx
2Ä„ -"

"
(x-s)2
s2 1
2 2
= e " e- dx
2Ä„ -"
s2
2
(3) = e .
2
Thus we have

(2) "k (3) "k s2

2
(4) < xk > = < exs > = e .

"sk s=0 "sk s=0
As a consequence, we obtain < xk > = 0 for odd k, and < x2 > = 1. Further since the derivative


"2n s2
2
e must be taken in pairs, < x2n > is the same as the number of ways to partition 2n

"s2n
s=0
elements into n pairs, which is (2n - 1)!! = (2n - 1) × (2n - 3) × · · · 3 × 1.
1.4. Gaussian matrix integral. Let M = (Mij) be an N × N Hermitian matrix, i.e., Mij =
Mji for every 1 d" i, j d" N, where Mji denotes the complex conjugate of Mji. Let dM =

dMii dRe(Mij)dIm(Mij) denote the standard Haar measure. Then the Gaussian Her-
i imitian matrix integral of an arbitrary function f is defined as

1 M2
2
(5) < f(M) > = e-N Tr( )f(M)dM,
Z0(N)
where the integration is over N × N Hermitian matrices, and Z0(N) is the normalization factor

M2
2
making < 1 > = 1, i.e., Z0(N) = e-N Tr( )dM.

As before we are particularly interested in a function of the form f(M) = aI (ij)"I Mij,
I
where I ranges over a finite system of multisets of elements of N × N. We introduce also the
source integral < eT r(MS) > for a given N × N Hermitian matrix S. It can easily be computed by

1 M2
2
< eTr(MS) > = e-N Tr( )eTr(MS)dM
Z0(N)

Tr(S2 )
1 1 S
2 N 2N
= e-N Tr( (M- )2)e dM
Z0(N)
Tr(S2 )
2N
(6) = e ,
since the trace is linear and Tr(MS) = Tr(SM), and thus we get

M2 M2 MS + SM
-N Tr + Tr(MS) = -N Tr -
2 2 2N

2
Tr S2
1 S
= -N Tr M - + .
2 N 2N
Note that for any 1 d" i, j d" N we get


" "
eTr(MS) = Tr(MS) eTr(MS)

"Sji S=0 "Sji S=0



"
= MmnSnm eTr(MS)

"Sji S=0
m,n
= Mij,
and thus the derivatives of the source integral becomes


" " 1 M2 " "

2
· · · < eTr(MS) > = e-N Tr( ) · · · eTr(MS) dM

"Sji "Slk S=0 Z0(N) "Sji "Slk S=0

1 M2
2
= e-N Tr( )MijMkl · · · dM
Z0(N)
(7) = < MijMkl · · · > .
On the other hand, we obtain

(7) " "

< MijMkl · · · > = · · · < eTr(MS) >
"Sji "Slk S=0

Tr(S2)
(6) " "

2N
(8) = · · · e
"Sji "Slk S=0
3
and in particular

Tr(S2)
" "

2N
< MijMkl > = e
"Sji "Slk S=0


Tr(S2)
" " Tr(S2)

2N
= e
"Sji "Slk 2N S=0



SmnSnm
Tr(S2)
" "
m,n
2N
= e
"Sji "Slk 2N S=0
Tr(S2)
" Skl ´il´jk

2N
(9) = e = .

"Sji N S=0 N
Further, it is clear that the derivatives in (8) and (9) must be taken in pairs (eg. Sji and Slk with
l = i and k = j) to get a non-zero contribution. This yields

< Mij > = < MijMkl >
(ij)"I pairings,P ‚"I2 ((ij),(kl))"P

´il´jk
(10) = ,
N
pairings,P ‚"I2 ((ij),(kl))"P
which is known as the matrix Wick theorem.
1.5. Graphic interpretation. A map is a graph together with a fixed cyclic ordering of the
incident edges of each vertex: it defines an embedding of the graph on an orientable 2D surface
(see [12]). A map is also called fat graph; we prefere this term because it corresponds to a
helpful graphic representation of a fat graph F in which the vertices are made into discs (islands)
and connected by fattened edges (bridges) prescribed by the cyclic orders. This defines a two-
dimensional orientable surface with boundary which we also denote by F . Each component of the
boundary of F will be called face of F . Each face is an embedded circle ([12]). We will denote by
G(F ) the underlying graph of F .
We denote by e(F ), v(F ), p(F ), c(F ), g(F ) the number of the edges, vertices, faces, connected
components, and the genus of F . We recall that 2g(F ) = 2c(F ) + e(F ) - v(F ) - p(F ).
In the next sections we will count fat graphs and their relatives. To avoid confusion we assume
that a fat graph has labelled vertices, i.e., two fat graphs are equal if they are equal as sets. We
speak about unlabelled fat graphs if the equality is up to isomorphism.
Definition 1.2. A fat graph is pointed if for each vertex, one fat edge incident to it is specified
as its initial fat edge.
Observation 1. Let F be a pointed fat graph. Then there is a unique orientation of the faces of
F defined in each component as follows: let v be a vertex and let e be its incident fat edge. Orient
the first (clockwise) shore of e from v, and the second shore of e to v.
Proof. We need to observe that the described process consistently orients each face of F , and that
is simple.

The graphic interpretation for the non-zero contributions to < f >, where f(M) = aI (ij)"I Mij,
I
is as follows. We represent Mij as a half- fat edge consisting of two end points and two lines with
opposite orientation such that i is associated with the out-going line and j the in-coming line as
follows:
i
00
11
Mij
j
00
11
Further (9) can be interpreted as that two half- fat edges Mij and Mkl construct a fat edge
with oppositely oriented shores and with weight 1/N if and only if i = l and j = k:
A fat edge with oppositely oriented shores will be called decorated fat edge.
4
i l, l = i
1
00 00
11 11
< Mij, Mkl >=
N
j k, k = j
00 00
11 11
Example 1.3. Let us consider Tr(Mn). By definition of the trace we get

Tr(Mn) = Mi i2Mi i3 · · · Mi i1 .
1 2 n
1d"i1,i2,··· ,ind"N
Following the above graphic interpretation we represent Tr(Mn) as a star fat diagram with n
decorated half- fat edges arranged in a clockwise pointed order and such that for each half- fat
edge, its first shore (clockwise along the center) is oriented from the center, as in Figure 1.
00
11
i1 i2
00
11
0 0
Mi i2Mi i3 · · · Mi i1 1 1
in i3
1 2 n
00
11
00
11
000
111
0
1
00
11
0
1
00
11
Figure 1. Tr(Mn) and its graphic interpretation as a star fat diagram
Moreover, using the matrix Wick theorem we can compute

< Tr(Mn) > = < Mi i2Mi i3 · · · Mi i1 >
1 2 n
1d"i1,i2,··· ,ind"N

= < Mi ik+1Mi il+1 >
k l
1d"i1,i2,··· ,ind"N pairing

´i ik+1´i il+1
k l
(11) = .
N
1d"i1,i2,··· ,ind"N pairing
Note that n should be even in order to get a non-zero contribution to (11) and thus set n = 2m.
Further, observe that only a fraction of (2m - 1)!! possible pairings have non-zero contribution
to (11); equivalently such pairings form decorated fat edges. In other words, we can think of a
pairing with non-zero contribution to (11) as a pointed fat graph with one island, whose faces are
oriented as in Observation 1. It indeed defines uniquely an embedding on a surface (see Figure 2).
0 00 0
1 11 1
00 0 00
11 1 11
0 00 0
1 11 1
00 0 00
11 1 11
00 00 0
11 11 1
00 00 00
11 11 11
Figure 2. All possible fat graphs with one island and n = 4
Let F be a contributing pointed fat graph. Certainly it has n/2 = m edges. Since each edge
contributes 1/N to (11), each pairing gets 1/Nm from all its edges. However, we should count
the contributions due to the summations over 1 d" i1, i2, · · · , in d" N. Notice that each (oriented)
face attains independently any index from 1 to N and thus the faces contribute Np(F ) to (11).
In summary each pointed fat graph F with one island and m faces contribute Np(F )-m. Thus
5
pointed fat graphs with genus zero (i.e., planar) contribute the leading term in N as N tends to
".
Now we count the plane fat graphs interpreted from < Tr(Mn) >; i.e., let Cm denote the set and
cm the number of the plane pointed fat graphs with one vertex and with m = n/2 fat edges. Note
that the half- fat edge Mi i2 would be paired by one of the half- fat edges Mi i3, Mi i5, · · · , Mi i1,
1 2 4 2m
say Mi i2k+1, forming a fat edge. We can interpret each element of Cm as being composed of an
2k
element of Ck-1 and an element of Cm-k (see Figure 3).
0
1
i1
0
1
0
1
0
1
0
12m
0
1
i
0
0 i3
12mi2 1
i
0
1
0
1
0
1
0 0
1 1
0 0
1 1
0
1
i3
0
1
0 0
1 1
0
1
00 1
11 i2k-1 i2k+1
0
00 00
11 11
i2k
00 0
11 1
i2k
0
1
0 00
1 11
0 1
0
0
1
00 i2k+11
11 i2k+21
0 i2k+2 i2k-1
0
1
0
1
0 00
1 11
0 0
1 1
000 0
111 1
00
11
000
111
00
11
000
111
00
11
Figure 3. Decomposition of a plane fat graph interpreted from < Tr(Mn) >
It implies the following recursion
m

cm = ck-1cm-k, c0 = c1 = 1,
k=1
which yields a well-known Catalan number

1 2m
cm = for m e" 1.
m + 1 m
As a consequence we can compute the limit of Gaussian matrix integral of Tr(Mn) as follows:

< Tr(Mn) > cm if n = 2m
lim =
N" N
0 otherwise .
Example 1.4. Our next example is Tr(M3)4 Tr(M2)3. As before we can compute
< Tr(M3)4 Tr(M2)3 >
ëÅ‚ öÅ‚4 ëÅ‚ öÅ‚3

íÅ‚
(12) = < Mi i2Mi i3Mi i1Å‚Å‚ íÅ‚ Mj j2Mj j1Å‚Å‚ > .
1 2 3 1 2
1d"i1,i2,i3d"N 1d"j1,j2d"N

Analogously to the previous example, (12) equals Np(F )-e(F ), where the sum is over all
F
pointed fat graphs F consisting of four fat vertices of degree 3, and three fat vertices of degree 2
(see Figure 4).
0
1
00
11
0
1
00
11
0 0
1 1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
00
11
0
1
000 0
111 1
0
1
00
11
00
11
00
11
Figure 4. A plane fat graph interpreted from < Tr(M3)4 Tr(M2)3 >
6
In summary, if f(M) is a product of the traces of powers of M then < f > is equal to the
number of pointed fat graphs F with the degree sequence given by the powers, and weighted by
Np(F )-e(F ).
2. Gaussian matrix integral and planar fat graphs
In this section we derive the formula for the number of planar fat graphs with given degree
sequence using matrix Wick theorem. For this we first recall some necessary concepts from the
complex analysis [13]. For every complex number z the exponential function exp(z), or ez, is
defined by the formula
"

zn z2 z3 z4
ez = = 1 + z + + + + · · · .
n! 2! 3! 4!
n=0
Fix a region (i.e. a nonempty connected open subset of complex plane) &! that exp(&!) = B(1, 1),
where B(c, r) = {z : |z - c| < r} for c complex and r > 0 real. The natural logarithm function
log(z) may be defined as its inverse function, that is, it satisfies w = log(z) and ew = z for
z " B(1, 1). It is holomorphic, i.e., infinitely often differentiable in B(1, 1). Thus it can be
described by its Taylor series
"

(-1)n+1 (z - 1)2 (z - 1)3 (z - 1)4
log(z) = (z - 1)n = (z - 1) - + - · · · .
n 2 3 4
n=1
The definition of the exponential function given above can be extended for every Banach algebra.
For each i e" 1 let zi be a non-zero complex variable with |zi| " (0, %EÅ‚i) where %EÅ‚i > 0 will be
chosen later. Let I be the group consisting of all non-negative integer vectors with only a finite
number of non-zero entries a = (n1, n2, · · · ), ni " N equipped with a linear order, which then
forms a linearly ordered abelian group. The ring R[[Z]] of formal power series over R in variable
Z = (z1, z2, · · · , zi, · · · ), i " N with a linearly ordered abelian group I as the index set is a Banach
algebra. Thus we can extend the definition of the exponential function for the ring R[[Z]]. In

particular, for X " R[[Z]] with X = cizi, ci " R,
ie"1
"
i
Xn (cizi)n
(13) eX = = lim ,


"
n! ni!
n=0 ad"

id"k
a=(n1,··· ,nk)
where instead of a = (n1, n2, · · · ) we write a = (n1, · · · , nk) for short if ni = 0 for i e" k + 1.
Now we consider a function f which maps each Hermitian matrix M to


Mi
ie"1 i
f(M) = eN ziTr ,
and investigate the relation between the Gaussian matrix integral of f and the asymptotic number
of planar fat graphs.
N
Observe first that for each i e" 1, Tr(Mi) = j(M)i where j(M) s are the eigenvalues
j=1
N j (M)i
i
of M, which are all real since M is a Hermitian matrix, and hence Tr(M ) = " R.
i j=1 i


Mi
Thus N ziTr " R[[Z]] and we can use (13) and get
ie"1 i
n
i
i
(N zi)n Mi
f(M) = lim Tr


"
ni! i
ad"

id"k
a=(n1,··· ,nk)
i
n
(N zi)n
i
= lim Tr(Mi) .
i


"
in ni!
ad"

id"k
a=(n1,··· ,nk)
7
We let
i
n
(N zi)n
i
·

(M) = Tr(Mi)
i
in ni!
ad"

id"k
a=(n1,··· ,nk)
i
n
(N zi)n
i
·(M) = lim Tr(Mi) .
i


"
in ni!
ad"

id"k
a=(n1,··· ,nk)
We first claim the following:
Claim 2.1. For each zi with |zi| " (0, %EÅ‚i), we have


i
Mi n
(N zi)n
i
ie"1 i
< eN ziTr > = lim < Tr(Mi) > .
i


"
in ni!
ad"

id"k
a=(n1,··· ,nk)
That is,
< ·(M) > = lim < ·

(M) > .


"
To prove it we use the following lemma, which is reformulated from Theorem 4 and Lemma 2
in Section 2, Chap. II in [15]:
Lemma 2.2. Let {·n}ne"1 be a sequence of random variables. If {·n}ne"1 satisfies
(i) E(|·n|) is uniformly bounded, i.e., supn E(|·n|) < ",
(ii) E(|·n|IA) is uniformly absolutely continuous, i.e., for any %EÅ‚ > 0 there exists ´ = ´(%EÅ‚) > 0
such that if E(IA) < ´, then supn E(|·n|IA) < %EÅ‚, and
(iii) limn" ·n = ·,
then
E(·) = lim E(·n).
n"
We set E(F ) = < F (M) > for any integrable function F . Let i = i(M), 1 d" i d" N, be the
eigenvalues of M and let  = (M) = max1d"id"N |j(M)|. Then the following holds.
Lemma 2.3. For any non-negative integer k, E(k) < ".
Proof of Lemma 2.3. We will show that for fixed 1 d" i d" N the function k is measurable (with
i
respect to the Haar measure dM), and so E(k) < ". It follows then that for fixed 1 d" i d" N
i
the absolute function |i|k and the maximum function k = max1d"id"N |j|k are also measurable,
and so E(k) < " (see e.g.,[13]).
Let U = U(M) be the unitary matrix that diagonalize M,
M = U›U"
where U" is the conjugate transpose of U, i.e., (U")ij = Uji and › = ›(M) is a diagonal matrix
defined by ›ij = i´ij. Since Tr(M2) = Tr(›2) and the Jacobian of the transformation M
M = U›U" is

J = (i - j)2,
1d"id"jd"N
8
we get dM = Jd1 · · · dN . Further we obtain

M2
2
Z0(N) = e-N Tr( )dM

1
2
= e-N Tr( ›2)Jd1 · · · dN ,

2
1 M
2
< eTr(›S) > = e-N Tr( )eTr(›S)dM
Z0(N)

Tr(S2)
1 1 S
2N 2 N
= e e-N Tr( (›- )2)Jd1 · · · dN
Z0(N)
Tr(S2)
2N
= e .
Thus, similarly to (7) and (8) we get


Tr(S2)
"k "k 0 if k is odd

2N
< ›k > = < eTr(›S) > = e =

ii (k-1)!!
k k
"Sii S=0 "Sii S=0
if k is even.
Nk/2
Thus E(k) = < k > = < ›k > < ".
i i ii

N
i i i
Proof of Claim 2.1. Observe first that [Tr(Mi)]n = [ j(M)i]n d" (N(M)i)n .
j=1
Now we will show that E(|·

|) is uniformly bounded. We let

= (n1, · · · , nk) be given and we
Å» Å»
select %EÅ‚i(

) > 0 so that for every zi with |zi| " (0, %EÅ‚i(

)) we have
i
(N2 |zi|)n
¾

= < " .
i
in ni!
ad"

id"k
a=(n1,··· ,nk)
Let
(14) %EÅ‚i = inf %EÅ‚i(

) > 0.




ini
Å» id"k
From Lemma 2.3 we know that  = E((M) ) < ". It follows that

ëÅ‚
öÅ‚

i
ìÅ‚ n ÷Å‚
(N zi)n
i
ìÅ‚ ÷Å‚
E(|·

|) = E Tr(Mi)

íÅ‚
i
in ni!
Å‚Å‚
ad"


a=(n ,··· id"k
,nk)
1
ëÅ‚ öÅ‚
i
n
(N |zi|)n
i
íÅ‚ Å‚Å‚
d" E N(M)i
i
in ni!
ad"

id"k
a=(n1,··· ,nk)
ëÅ‚ öÅ‚
i
(N2 |zi|)n
ini
íÅ‚ id"k Å‚Å‚
= E (M)
i
in ni!
ad"

id"k
a=(n1,··· ,nk)
i
(N2 |zi|)n ini
id"k
= E (M)
i
in ni!
ad"

id"k
a=(n1,··· ,nk)
Å»
= ¾

 < " .
Thus sup

E(|·

|) < ".
9
Second we will show that E(|·

|IA) is uniformly absolutely continuous. We let ¾ = sup

¾

< ",
Å»
´ = %EÅ‚/(2¾). Then if E(IA) < ´, then

ëÅ‚ öÅ‚


i
ìÅ‚ n ÷Å‚
(N zi)n
i
ìÅ‚
E(|·

|IA) = E Tr(Mi) IA÷Å‚

íÅ‚ Å‚Å‚
i
in ni!

ad"


a=(n ,··· id"k
,nk)
1
ëÅ‚ öÅ‚
i
n
(N |zi|)n
i
íÅ‚
d" E N(M)i IAÅ‚Å‚
i
in ni!
ad"

id"k
a=(n1,··· ,nk)
i
(N2 |zi|)n ini
id"k
d" E (M) IA
i
in ni!
ad"

id"k
a=(n1,··· ,nk)
Å»
d" ¾´ < %EÅ‚ .
Thus sup

E(|·

|IA) < %EÅ‚ for E(IA) < ´.
As a consequence Claim 2.1 follows immediately from Lemma 2.2.
From Claim 2.1 and Example 1.4 we have that
i
n
(N zi)n
i
< f(M) > = lim < Tr(Mi) >
i


"
in ni!
ad"

id"k
a=(n1,··· ,nk)
i
n
(N zi)n
i
= lim < Tr(Mi) >
i


"
in ni!
ad"

id"k id"k
a=(n1,··· ,nk)
ni

zi
(15) = lim Nv(“)+p(“)-e(“) ,
i


"
in ni!
ad"

“ id"k
a=(n1,··· ,nk)
where the second sum is over all pointed fat graphs “ with ni vertices of degree i.
Note that
(16) the number of pointed (labelled) fat graphs
i
in ni!
= the number of unlabelled fat graphs × .
|Aut(“)|
i
Hence

Nv(“)+p(“)-e(“) ni
(17) < f(M) > = lim zi .


"
|Aut(“)|
ad"

“ unlabelled id"k
a=(n1,··· ,nk)
Next we observe in the formula (15) that v(“)+p(“)-e(“) = -2g(“)+2c(“) is additive for the
operation of the disjoint union. Taking the logarithm of < f(M) > we get the following formula
for the connected pointed fat graphs.
Proposition 2.4. For every zi with |zi| " (0, %EÅ‚i) where %EÅ‚i > 0 satisfying (14) we have
ni

zi
log < f(M) > = lim Nv(“)+p(“)-e(“)
i


"
in ni!
ad"

“pointed connected id"k
a=(n1,··· ,nk)
ni

zi
= lim N-2g(“)+2 .
i


"
in ni!
ad"

“pointed connected id"k
a=(n1,··· ,nk)
10
Again due to the formula (17) we have

N-2g(“) ni
(18) N-2 log < f(M) > = lim zi .


"
|Aut(“)|
ad"

“ unlabelled connected id"k
a=(n1,··· ,nk)
Now we are ready to state the formula for the asymptotic number of unlabelled connected
planar fat graphs. For the proof we need Fatou s lemma (Theorem 2 (c) in Section 2, Chap. II
in [15]):
Lemma 2.5. Let {¾n} be a sequence of random variables. If ¾n d" · for every n e" 1 and E(·) < ",
then
E(lim inf ¾n) d" lim inf E(¾n) d" lim sup E(¾n) d" E(lim sup ¾n).
n n
n n
Theorem 1. For every zi with |zi| " (0, %EÅ‚i) where %EÅ‚i > 0 satisfying (14) and (19) we have

1
ni
lim N-2 log < f(M) > = lim zi ,
N"

"
|Aut(“)|
ad"

“ unlabelled connected planar id"k
a=(n1,··· ,nk)
where “ has ni vertices of degree i, i e" 0.
Proof. From (18) we know that

1
ni
lim N-2 log < f(M) > = lim zi
N"

"
|Aut(“)|
ad"

“ unlabelled connected planar id"k
a=(n1,··· ,nk)

N-2g(“) ni
+ lim lim zi .
N"

"
|Aut(“)|
ad"

“ unlabelled connected non-planar id"k
a=(n1,··· ,nk)
It is enough to show that

N-2g(“) ni
lim lim zi = 0.
N"

"
|Aut(“)|
ad"

“ unlabelled connected non-planar id"k
a=(n1,··· ,nk)
For a given sequence · = {·(a)}a"I, where I is a linearly ordered abelian group introduced
above, we can think of the series

lim ·(a)


"
ad"


a=(n1,··· ,nk)
as the expectation over I equipped with measure µ such that µ(a) = 1 iff a " I. That is,

lim ·(a) = Eµ(·) .


"
ad"


a=(n1,··· ,nk)
We define a sequence · = {·(a)}a"I by, for each a = (n1, · · · , nk),

i
·(a) = |zi|n ,
“np id"k
where the sum is over all unlabelled conected non-planar fat graphs “np with ni vertices of degree
i. We select %EÅ‚i s so that for all zi with |zi| " (0, %EÅ‚i)

i
(19) Eµ(·) = lim |zi|n < " ,


"
ad"

“np id"k
a=(n1,··· ,nk)
where the sum is over all unlabelled connected non-planar fat graphs “np with ni vertices of degree
i.
11
We consider a sequence ¾N = {¾N (a)}a"I defined by, for each a = (n1, · · · , nk),
np
N-2g(“ )
ni
¾N (a) = zi ,
|Aut(“np)|
“np id"k
where the sum is over all unlabelled connected non-planar fat graphs “np with ni vertices of degree
i. Note that we have

Eµ(¾N ) = lim ¾N (a) ,


"
ad"


a=(n1,··· ,nk)
and |¾N (a)| d" ·(a) for every N e" 1 since g(“np) > 0. In addition the sequence limN" ¾N =
{limN" ¾N (a)}a"I satisfies
np
N-2g(“ )
ni
lim ¾N (a) = lim zi
N" N" |Aut(“np)|
“np id"k
np
N-2g(“ )
ni
= zi lim
N" |Aut(“np)|
“np id"k
= 0 ,
because g(“np) > 0 for non-planar fat graphs “np. Thus we obtain

Eµ( lim ¾N ) = lim lim ¾N (a) = 0 .
N"

" N"
ad"


a=(n1,··· ,nk)
By Fatou s lemma we have that
lim inf Eµ(¾N ) = lim sup Eµ(¾N ) = 0 .
N"
N"
It follows then that
np
N-2g(“ )
ni
0 = lim Eµ(¾N ) = lim lim zi ,
N" N"

"
|Aut(“np)|
ad"

“np id"k
a=(n1,··· ,nk)
where the second sum is over all unlabelled connected non-planar fat graphs “np with ni vertices
of degree i.
3. Directed graphs
In this section we move from matrices to directed graphs. Let M be an N × N matrix and
let D = D(M) = (N, N × N) be a directed with weights on directed edges given by
graph
M. Now Tr(Mn) may be interpreted as Me, where the sum is over all pointed (i.e.,
p e"p
with a prescribed beginning) closed walks in D of length n. Similarly, Tr(M3)4Tr(M2)3 may be
interpreted as

( Me)4( Me)3,
p1 e"p1 p2 e"p2
where the first sum is over all pointed closed walks p1 in D of length 3, and the second sum is
over all pointed closed walks p2 in D of length 2.
Hence if f(M) = Tr(M3)4Tr(M2)3 we get:

< f > = 1/N,
q=q1q2...q7 {e,e2 }"P
P
where the second sum is over all proper pairings P of the directed edges of the disjoint union
q = q1q2 . . . q7 of 7 pointed closed walks, from which 4 have length 3 and remaining 3 have length
2. Two directed edges form a proper pairing if one is reversed the other. We also say that pair
(q, P ), P proper, contributes to < f >.
12
4. Even sets of directed edges
The starting idea is to replace pointed closed walks by flows. A non-negative integer function
on the directed edges of D is flow if for each vertex v of D, the sum of f(e) over the incoming
edges is the same as over the outgoing edges. It turns out that a restrictive subset of the set of
all flows consisting of 0, 1 flows is already interesting. These flows naturally lead to even subsets
of edges defined below. In this section we again let D = D(M) = (N, N × N).
Definition 4.1. A subset A ‚" E(D) of directed edges is even if A can be written as a union of
edge-disjoint cycles of length bigger than two.
We further denote by A(r3, . . . , rk) the set of all even sets of edges which have a decomposition
into ri cycles of length i (i = 3, . . . , k) and by A2 (r3, . . . , rk) the set of all even sets of edges with a
fixed decomposition into ri cycles of length i (i = 3, . . . , k). We let A(r) = *"r=r +...rkA(r3, . . . , rk),
3
A = *"r>0A(r), and A2 (r) = *"r=r +...rkA2 (r3, . . . , rk), A2 = *"r>0A2 (r).
3
A proper pairing of an even set A is a partition of A into pairs (ij), (ji) of oppositely directed
edges.
4.1. Cycle double cover conjectures. It is not true that a set of directed edges, which induces
the same indegree and outdegree at each vertex, is a union of disjoint directed cycles of length
bigger than 2. This is closely related to the cycle double cover conjectures.
Definition 4.2. Let G be an undirected graph. A collection of its cycles is called cycle double
cover (CDC) if each edge belongs to exactly two of the cycles. Moreover it is called directed cycle
double cover (DCDC) if it is possible to orient the cycles so that they go oppositely on each edge.
Some of the most puzzling conjectures of discrete mathematics are centered around this notion.
A graph is bridgeless if it cannot be disconnected by deletion of a single edge. Clearly a graph
with a bridge does not have a CDC. On the other hand, there are
" Cycle double cover conjecture: Is it true that each bridgeless graph has a CDC?
" Directed cycle double cover conjecture: Is it true that each bridgeless graph has a DCDC?
The following observation is straightforward.
Observation 2. Let q " A2 (r3, . . . , rk) come with a fixed decomposition into ri cycles Ci,1, . . . , Ci,r
i
of length i (i = 3, . . . , k). Let P be a proper pairing of q. Then the cycles form a DCDC of the
simple graph with vertices {1, . . . , N} and the edges given by the pairings.
Definition 4.3. Let M be a matrix. We let

gr(M) = Me,
e"c
c"A(r)

2
gr(M) = Me,
e"c
c"A2 (r)
2
and we define g, g2 , gr ,...,rk(M), gr ,...,rk(M) analogously.
3
3

We call Me the weight of the cycle c.
e"c
Next definition and proposition are crucial.
Definition 4.4. Let G be a finite simple undirected graph with at most N vertices and with a
DCDC. Then we let c(G) be the set of all pairs (q, P ) so that there is a coloring d of the vertices of G
by colors {1, . . . , N}, where each vertex gets a different color, q = {(d(x), d(y)), (d(y), d(x)); {x, y} "
E(G)}, and P consists of all the pairs ([(d(x), d(y)), (d(y), d(x))]; {x, y} " E(G)).
We remark that each such q is an even subset of directed edges of D = (N, N × N) since G has
a DCDC, and |c(G)| = N(N - 1) . . . (N - |V (G)| + 1).
Proposition 4.5. A term (q, P ) contributes to < gr ,...,rk(M) > if and only if there is a simple
3
graph G with a DCDC consisting of ri cycles of length i (i = 3, . . . , k) such that (q, P ) " c(G).
13
Proof. If (q, P ) " c(G) then any DCDC provides a partition of q into its cycles and hence (q, P )
contributes to < gr ,...,rk(M) >. On the other hand if (q, P ) contributes to < gr ,...,rk(M) > then
3 3
let G be the graph with the vertices from {1, . . . , N} and the edges given by P . Then G is simple
since q consists of edge-disjoint directed cycles, it has a DCDC consisting of ri cycles of length i
(i = 3, . . . , k), and (q, P ) " c(G).
Proposition 4.6. If c(G) )" c(G2 ) = " then G is isomorphic to G2 . Moreover, if G is isomorphic

to G2 then c(G) = c(G2 ).
Proof. If (q, P ) " c(G) )" c(G2 ) then the construction of q induces a function between the sets of
vertices of G and G2 , and P gives the edges of both G, G2 . Hence they are isomorphic. The second
part is true since the definition of c(G) does not depend on  names of the vertices.
As a consequence we have
Theorem 2.

N(N - 1) . . . (N - |V (G)| + 1)
< gr ,...,rk(M) > = ,
3
Ne(G)
[G]
where the sum is over all isomorphism classes of simple graphs with at most N vertices that have
a DCDC consisting of ri cycles of length i (i = 3, . . . , k). Moreover

N(N - 1) . . . (N - |V (G)| + 1)
2
< gr ,...,rk(M) > = ,
3
Ne(G)
[G]2
where the sum is over all isomorphism classes of simple graphs with at most N vertices and with
a specified DCDC consisting of ri cycles of length i (i = 3, . . . , k).
2
Analogous statements hold for gr, gr, g, g2 .
4.2. Calculations. The integral < g2 (M) > counts all the directed cycle double covers of graphs
on at most N vertices and hence its calculation is an attractive task which neednot be hopeless.
We show next a curious formula for g2 (M) which identifies it with an Ihara-Selberg-type function
(see Theorem 2). Let us recall that

g2 (M) = Me,
c"A2 e"c
is the generating function (with variables Me s) of the collections of edge-disjoint directed cycles
of length at least three, in the directed graph D = D(M) = (N, N × N).
Construction of digraph D . We first construct a directed graph D2 with the weights on the
transitions between the edges. First we split each vertex of D, i.e. we replace each vertex v by
new edge e(v) and we let all the edges of D entering v enter the initial vertex of e(v), and all the
edges of D leaving v leave the terminal vertex of e(v). If edge g enters v in D then we define the
weight of the transition w(g, e(v)) = Mg. We let all the remaining transition be equal to one.
Finally, for each pair g1, g2 of oppositely directed edges of D, say g1 = (uv), g2 = (vu) we
introduce new vertex vg and we let both g1, g2 pass through it; equivalently, we subdivide both
g1, g2 by one vertex and identify this pair of vertices into unique vertex called vg (and thus we
have new edges (uvg), (vgv) from g1 = (uv), and new edges (vvg), (vgu) from g2 = (vu)).
See Figure 5.
We let the weights of the transitions at vertex vg between g1 and g2 (i.e., between (uvg) and
(vgu) and between (vvg) and (vgv)) be equal to zero, the transitions along g1 and g2 (i.e., between
(uvg) and (vgv) and between (vvg) and (vgu)) be equal to one, and the transitions between (vgv)
and e(v) be equal to Mg and between (vgu) and e(u) be equal to Mg . See an example in Figure 6.
1 2
In what follows, the directed closed walk is considered not pointed. We let the weight of the
directed closed walk be the product of the weights of its transitions.
Observation 3. There is a weight preserving bijection between the set of the directed cycles of D
of length at least three and the set of the closed directed walks of D2 of a non-zero weight which go
through each directed edge and through each vertex vg at most once.
14
e(u) e(u)
u
u u
u u
g1 g2
vg
v
v
v
e(v) v e(v)
v
Figure 5. Construction of e(v) and vg
e(2)
2
e(2) 2
2
2
1 v({1,2})
e(1)
e(1)
1
1
1
1
v({1,3})
2 3
e(3)
e(3)
D 3 3
3 3
v({2,3})
D
Figure 6. An example of the construction of digraph D
Proof. This follows directly from the construction of D2 .
Definition 4.7. We define the rotation number for each closed walk w of D2 with a non-zero
weight by induction as follows: first order the directed edges of D2 , say as a1, . . . , am, so that the
edges e(v), v " V (D) form the terminal segment. Then
1. If w is a directed cycle then we let r(w) = -1.
2. Let w go at least twice through a directed edge. Let a be the first such edge in the fixed
ordering. Hence w is a concatenation of two shorter closed walks w1, w2, both containing
a. If a = e(v) for some v then we let r(w) = r(w1)r(w2). If a = e(v) then we let r(w) = 0.

3. If none of 1.,2. applies, w must go through a vertex vg (introduced in the definition of D2 )
at least twice. Then we again let r(w) = 0.
Theorem 3.

g2 (M) = (1 - r(p)w(p)),
p
where the product is over all aperiodic closed directed walks p in D2 and w(p) denotes the weight
of p.
Proof. We first show that the coefficients corresponding to the products of variables where at least
one Me, e = e(v), appears with the exponent greater than one, are all equal to zero.

Let us denote W (p) = -r(p)w(p). Let A1 be the set of all non-periodic closed walks p such that
a1 appears in p. Each p " A1 has a unique factorization into words (W1, ..., Wk) each of which
starts with a1 and has no other appearance of a1.
We will need a curious lemma on coin arrangements stated below. It has been introduced by
Sherman [14] in the study of 2D Ising problem.
A lemma on coin arrangements. Suppose we have a fixed collection of N objects of which
m1 are of one kind, m2 are of second kind, · · · , and mn are of n-th kind. Let bk be the number of
exhaustive unordered arrangements of these symbols into k disjoint, nonempty, circularly ordered
sets such that no two circular orders are the same and none are periodic. For example let us have 10
coins of which 3 are pennies, 4 are nickles and 3 are quarters. Then {(p, n), (n, p), (p, n, n, q, q, q)}
is not a correct arrangement since (p, n) and (n, p) represent the same circular order. If N > 1
N
then (-1)i+1bi = 0.
i=1
15
Proof of the lemma on coin arrangements. The lemma follows immediately if we expand
the LHS of the following Witt Identity and collect terms where the sums of the exponents of the
zi s are the same.
Witt Identity (see [11]): Let z1, ..., zk be commuting variables. Then

m1 mk 1
(1 - z1 ...zk )M(m ,...,mk) = 1 - z1 - z2 - ... - zk,
m1,...,mke"0
where M(m1, ...., mk) is the number of different nonperiodic sequences of zi s taken with respect
to circular order.

Let S be a monomial summand in the expansion of (1 + W (p)). Hence S is a product of
p"A1
finitely many W (p), p " A1.
Each p " A1 has a unique factorization into words defined above. Each word may appear several
times in the factorization of p and also in the factorization of different non-periodic closed walks.
Let B(D2 ) be the set-system of all the words (with repetition) appearing in the factorizations of
the aperiodic closed walks of D2 .
It directly follows from the lemma on coin arrangements that the sum of all monomial summands

S in the expansion of (1 + W (p)), which have the same  coins B(D2 ) of more one
p"A1
than
element is zero. Hence the monomial summands S which survive in the expansion of (1 +
p"A1
W (p) all have B(D2 ) consisting of exactly one word. Hence they cannot have a1 with exponent
bigger than one. Now we can repeat the same consideration for the other edges different from
e(v), v " V .
Hence the only terms of the expansion of the infinite product that survive have all Me, e = e(v),

with the exponent at most one.
We know from Observation 3 that the collections of the edge-disjoint directed cycles of length
at least three in D2 correspond to the collections of the directed closed aperiodic walks of D2 where
each edge e = e(v) of D2 appears at most once; by above, these exactly have chance to survive.

Each term of g2 (M) may be expressed several times as a product of aperiodic closed walks of D2 ,
but only one such expression survives in the infinite product since if a closed walk goes through an
edge e(v) or through a vertex vg more than once, its rotation is defined to be zero. Hence g2 (M)
is counted correctly in the infinite product.

Remark 4.8. Let us write r(p) = qrot(p), where q = -1. Without the zero values of r(p), function
rot is additive when we  smoothen p into directed cycles. The integer lattice generated by the
directed cycles has a basis which may be constructed e.g. from the ear-decomposition [9]; the
function rot may be split into contributions of the edge-transitions for the basis, and since it is a
basis, it may be split also for all the directed cycles. Hence if the additivity property holds, rot
may be split into the contributions rot(t) of the edge-transitions t for the aperiodic closed walks.
Hence

(1 - r(p)w(p)) = (1 - (-1)rot(t)w(t)).
p p t"p
This formula transforms the infinite product into the Ihara-Selberg function. It was studied by
Bass in [1] who proved that it is equal to a determinant. A combinatorial proof was given by
Foata and Zeilberger in [8].
Having the zero values of r(p) it is not clear how to split the rotation to individual edge-
transitions. A determinant-type formula, perhaps non-commutative, may however exist. Moreover
the Ihara-Selberg function and its inverse appear frequently in theoretical physics and so the matrix
integral of g2 (M) may have, via the formula of Theorem 3, an interesting physics interpretation.
5. Back to fat graphs
Loopless fat graph F is called cyclic if each face of F is a cycle of G(F ). For cyclic F we define
"
its dual F as the fat graph whose islands are the discs bounded by the faces of F , and whose
"
bridges may be identified with the bridges of F . Note that F is again loopless and thus we have:
16
Observation 4. A fat graph F is cyclic if and only if it is a dual of a cyclic fat graph; in particular
""
F = F .
"
Definition 5.1. A fat graph F is called relevant if it is cyclic and F is a simple fat graph.
By definition a loopless fat graph is relevant if each face is a cycle of G(F ), and each pair of
" "
faces of F shares at most one bridge. (G(F ) does not have multiple edges). Moreover, if W is
simple then W does not have vertices of degree at most two.
A compressed fat graph is a pair (F, P ) where F is a fat graph and P is a partition of the set
of its vertices. We denote by GP (F ) the (abstract) graph which is obtained by the identification
of the vertices of each class of P in G(F ).
Next definition is more technical.
Definition 5.2. A pair (W, Q) where W is a relevant fat graph and Q is a partition of the set of
"
its faces is called relevant if W is relevant and GQ(W ) is a simple graph.
When Q partitions of faces into themselves, we denote it by ".
Proposition 5.3. There is a natural bijection between the set of the relevant pairs (W, Q) such
that W has exactly ri vertices of degree i (i e" 3) and the set of the simple graphs G with a specified
"
DCDC consisting of ri cycles of length i. The bijection sends (W, Q) to GQ(W ).
Proof. We realize each cycle from the DCDC as a disc and glue the discs together along the pairs
of corresponding oppositely oriented edges. We get a surface where some vertices are identified.
When we split the identified vertices, we get an honest compact 2-dimensional orientable surface
2
with a graph G2 embedded on it. We change the embedding of G2 into the fat graph F ; it is cyclic
since its faces are exactly the cycles of the DCDC we started with.
Graph G2 is obtained from G by splitting off some vertices. This defines a partition Q of the
set of vertices of G2 .
2 "
This produces a relevant pair (F , Q).
Moreover, it is not difficult to observe that this construction may be reversed and thus we get
a bijection.
We can write
Corollary 5.4.

N(N - 1) . . . (N - Ä… + 1)
< gr ,...,rk(M) > = ,
3 "
Q
Ne(G (W ))
[(W,Q)]
where (W, Q) is a relevant pair such that W has exactly ri vertices of degree i (i e" 3), and partition
"
Q of its faces into Ä… d" N parts; [.] denotes the isomorphism equivalence class of GQ(W ).
5.1. Extracting the planar graphs. We are grateful to Bojan Mohar for the following charac-
terization of relevant planar fat graphs.
Proposition 5.5. A planar fat graph is relevant iff each of its connected components is 2-connected
and 3-edge-connected.
Proof. A planar graph is 2-connected iff its dual is 2-connected iff each face is a cycle; here
parallel edges in the dual are allowed, but no loops. The parallel edges are eliminated by the
3-edge-connectivity.
A theorem analogous to theorem 1 holds.
Theorem 4. For every zi with |zi| " (0, %EÅ‚i) we have
ri
i
(Nzi)r zi
lim N-2 log < gr ,...(M) > = ,
3
N" ri! ri!
r3,... i
[“]" i
where “ is a 2-connected 3-edge-connected planar fat graph with ri vertices of degree i, i e" 0, and
[]" is the isomorphism equivalence class of “".
17
Proof. From Corollary 5.4 we get
i
(Nzi)r
< gr ,...(M) >
3
ri!
r3,... i
ri

zi
= Nv(W )-e(W )N(N - 1) . . . (N - Ä… + 1)
ri!
i
[(W,Q)]

ri

i zi
(20) = Nv(W )-e(W )+p(W ) 1 - NÄ…-p(W ) .
N ri!
[(W,Q)] 1d"id"Ä…-1 i
As in Proposition 2.4, it is natural to express its logarithm again in terms of connected W in
order to extract the number of connected planar relevant fat graphs in the large N limit. As before
v(W ) - e(W ) + p(W ) = -2g(W ) + 2c(W ) is additive for the operation of the disjoint union, but
the rest is only submultiplicative. Hence we proceed in two steps. First, we upper bound the LHS
of (20):
i
(Nzi)r
log < gr ,...(M) >
3
ri!
r3,... i

ri
(20)
i zi
d" Nv(W )-e(W )+p(W ) 1 - NÄ…-p(W )
N ri!
[(W,Q)]W connected 1d"id"Ä…-1 i

ri

i zi
(21) = N2 N-g(W ) 1 - NÄ…-p(W ) .
N ri!
[(W,Q)] W connected 1d"id"Ä…-1 i
Further using Fatou s lemma as in Theorem 1 we obtain
i
(Nzi)r
lim N-2 log < gr ,...(M) >
3
N" ri!
r3,... i

ri

(21) i zi
= lim N-g(W ) 1 - NÄ…-p(W )
N" N ri!
[(W,Q)]W connected 1d"id"Ä…-1 i

ri

i zi
Fatou
= lim N-g(W ) 1 - NÄ…-p(W )
N" N ri!
[(W,Q)] W connected non-planar 1d"id"Ä…-1 i

ri

i zi
+ lim 1 - NÄ…-p(W )
N" N ri!
[(W,Q)] connected planar 1d"id"Ä…-1 i
ri

zi
(22) = ,
ri!
i
[(W,")] W connected relevant planar
where the last equality follows from Proposition 5.5.
Finally we lower bound the LHS of (20):
i
(Nzi)r
log < gr ,...(M) >
3
ri!
r3,... i
ri
(20)
zi
e" Nv(W )-e(W )+p(W )
ri!
i
[(W,")]W connected
ri

zi
(23) = N2 N-g(W ) .
ri!
i
[(W,")] W connected
The rest of the analysis is the same as for the upper bound, and since the two bounds are equal,
theorem follows.

18
References
[1] H. Bass. The ihara- selberg zeta function of a tree lattice. Internat. J. Math., 3:717  797, 1992.
[2] E. A. Bender and E. R. Canfield. The number of degree-restricted rooted maps on the sphere. SIAM J. Discrete
Math., 7:9 15, 1994.
[3] D. Bessis, C. Itzykson, and J. B. Zuber. Quantum field theory techniques in graphical enumeration. Adv. in
Appl. Math., 1:109 157, 1980.
[4] J. Bouttier, P. Di Francesco, and E. Guitter. Census of planar maps: from the one-matrix model solution to a
combinatorial proof. Nuclear Phys. B, 645:477 499, 2002.
[5] J. Bouttier, P. Di Francesco, and E. Guitter. Combinatorics of hard particles on planar graphs. Nuclear Phys.
B, 655:313 341, 2003.
[6] P. Di Francesco. 2D quantum gravity, matrix models and graph combinatorics. http://arxiv.org/abs/math-
ph/0406013, 2004.
[7] P. Di Francesco. Matrix model combinatorics: applications to folding and coloring. In Random matrix models
and their applications, Math. Sci. Res. Inst. Publ., 40, Cambridge Univ. Press, Cambridge, pages 111 170,
2001.
[8] D. Foata and D. Zeilberger. A combinatorial proof of bass s evaluations of the ihara-selberg zeta function for
graphs. Transactions of the AMS, 351-6:2257  2274, 1999.
[9] A. Galluccio and M. Loebl. (p, q)-odd digraphs. Journal of graph theory, 23:175 184, 1996.
[10] O. Giménez and M. Noy. Asymptotic enumeration and limit laws of planar graphs.
http://arxiv.org/abs/math.CO/0501269, 2005.
[11] H. M. Hall. The Theory of Groups. Macmillan, 1959.
[12] B. Mohar and C. Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences, 2001.
[13] W. Rudin. Real and complex analysis. McGraw-Hill. 3rd ed., 1987.
[14] S. Sherman. Combinatorial aspects of the ising model of ferromagnetism i. J. Math. Phys., 1, 1960.
[15] A. N. Shiryayev. Probability. Springer-Verlag, 1984.
Humboldt-Universität zu Berlin, Institut für Informatik,, Unter den Linden 6, 10099 Berlin, Ger-
many
E-mail address: [e-mail]
Dept. of Applied Mathematics and, Institute of Theoretical Computer Science (ITI), Charles Uni-
versity, Malostranske n. 25, 118 00 Praha 1, Czech Republic.
and Depto. Ing. Matem atica, University of Chile, Chile.
E-mail address: [e-mail]
19