B Eynard
email: eynard@spht.saclay.cea.fr

Formal matrix integrals and combinatorics of maps

integrals, and combinatorics of maps.

Introduction

This article is a short review on the relationship between convergent matrix integrals, formal matrix integrals, and combinatorics of maps. We briefly summarize results developed over the last 30 years, as well as more recent discoveries.

We recall that formal matrix integrals are identical to combinatorial generating functions for maps, and that formal matrix integrals are in general very different from convergent matrix integrals. Both may coincide perturbatively (i.e. up to terms smaller than any negative power of N), only for some potentials which correspond to negative weights for the maps, and therefore not very interesting from the combinatorics point of view.

We also recall that both convergent and formal matrix integrals are solutions of the same set of loop equations, and that loop equations do not have a unique solution in general.

Finally, we give a list of the classical matrix models which have played an important role in physics in the past decades. Some of them are now well understood, some are still difficult challenges.

Matrix integrals were first introduced by physicists [START_REF] Wigner | [END_REF], mostly in two ways: -in nuclear physics, solid state physics, quantum chaos, convergent matrix integrals are studied for the eigenvalues statistical properties [START_REF] Mehta | Random Matrices[END_REF][START_REF] Guhr | Random matrix theories in quantum physics: Common concepts[END_REF][START_REF]Random Matrix Models and Their Applications[END_REF][START_REF] Van Moerbeke | Random Matrices and their applications[END_REF]. Statistical properties of the spectrum of large random matrices show some amazing universal behaviours, and it is believed that they correspond to some kind of "central limit theorem" for non independent random variables. This domain is very active and rich, and many important recent progresses have been achieved by the mathematicians community. Universality was proved in many cases, in particular using the Riemann-Hilbert approach of Bleher-Its [START_REF] Bleher | Semiclassical asymptotics of orthogonal polynomials, Riemann-Hilbert problem, and universality in the matrix model[END_REF] and Deift Venakides Zhou Mac Laughlin [START_REF] Deift | Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory[END_REF], and also by large deviation methods [START_REF] Guionnet | Large deviations asymptotics for spherical integrals[END_REF][START_REF] Guionnet | Combinatorial aspects of matrix models[END_REF].

-in Quantum Chromodynamics, quantum gravity, string theory, conformal field theory, formal matrix integrals are studied for their combinatorial property of being generating functions of maps [START_REF] Di Francesco | 2D Gravity and Random Matrices[END_REF]. This fact was first discovered by t'Hooft in 1974 [START_REF] Hooft | [END_REF], then further developed mostly by BIPZ [12] as well as Ambjorn, David, Kazakov [START_REF] Di Francesco | 2D Gravity and Random Matrices[END_REF][START_REF] David | Planar diagrams, two-dimensional lattice gravity and surface models[END_REF][START_REF]Two dimensional quantum gravity and random surfaces[END_REF][START_REF] Kazakov | Bilocal regularization of models of random surfaces[END_REF][START_REF] Kazakov | Critical Properties Of Randomly Triangulated Planar Random Surfaces[END_REF]. For a long time, physicist's papers have been ambiguous about the relationship between formal and convergent matrix integrals, and many people have been confused by those ill-defined matrix integrals. However, if one uses the word "formal matrix integral", many physicist's results of the 80's till now are perfectly rigorous, especially those using loop equations. Only results regarding convergency properties were non rigorous, but as far as combinatorics is concerned, convergency is not an issue.

The ambiguity in physicist's ill-defined matrix integrals started to become obvious when E. Kanzieper and V. Freilikher [42], and later Brezin and Deo in 1998 [11] tried to compare the topological expansion of a formal matrix integral derived from loop equations, and the asymptotics of the convergent integral found with the help of orthogonal polynomials. The two results did not match. The orthogonal polynomial's method showed clearly that the convergent matrix integrals had no large N power series expansion (it contained some (-1) N ). The origin of this puzzle has now been understood [START_REF] Bonnet | Breakdown of universality in multi-cut matrix models[END_REF], and it comes from the fact that formal matrix integrals and convergent matrix integrals are different objects in general. This short review is only about combinatoric properties of formal matrix integrals. Matrix models is a very vast topic, and many important applications, methods and points of view are not discussed here. In particular, critical limits (which include asymptotics of combinatoric properties of maps), the link with integrable systems, with conformal field theory, with algebraic geometry, with orthogonal polynomials, group theory, number theory, probabilities and many other aspects, are far beyond the scope of such a short review.

Definition 2.1 Q is an invariant non-commutative monomial of M 1 , . . . , M p , if Q = 1 or if Q is of the form: Q = R r=1 1 N Tr (W r ) (2-2)
where each W r is an arbitrary word written with the alphabet M 1 , . . . , M p . Q is the equivalence class of Q under permutations of the W r 's, and cyclic permutations of the letters of each W r .

The degree of Q is the sum of lengths of all W r 's. Invariant non-commutative polynomials of M 1 , . . . , M p are complex finite linear combinations of monomials:

V = Q t Q Q , t Q ∈ C (2-3)
The degree of a polynomial is the maximum degree of its monomials. They are called invariant, because they are left unchanged if one conjugates all matrices M i → UM i U -1 with the same invertible matrix U.

Invariant polynomials form an algebra over C.

Let V (M 1 , . . . , M p ) be an arbitrary invariant polynomial of degree d in M 1 , . . . , M p , which contains only monomials of degree at least 3. Proposition 2.1 Let C be a p×p symmetric positive definite matrix, then the following Gaussian integral

A k (t) = H N ×...×H N dM 1 dM 2 . . . dM p N 2k t -k k! V k e -N 2t Tr p i,j=1 C ij M i M j H N ×...×H N dM 1 dM 2 . . . dM p e -N 2t Tr p i,j=1 C ij M i M j (2-4)
where dM i is the usual Lebesgue (U(N) invariant) measure on the space of hermitian matrices H N , is absolutely convergent and has the following properties:

A k (t) is a polynomial in t, of the form:

A k (t) = k/2≤j≤kd/2-k A k,j t j (2-5) A k (t) is a Laurent polynomial in N. A 0 (t) = 1.
proof:

A 0 = 1 is trivial. Let d = deg V . Since
V is made of monomials of degree at least 3 and at most d, then V k is a sum of invariant monomials whose degree l is between 3k and dk. According to Wick's theorem, the Gaussian integral of a monomial of degree l is zero if l is odd, and it is proportional to t l/2 if l is even. Since 3k ≤ l ≤ dk we have:

0 ≤ k/2 ≤ l/2 -k ≤ dk/2 -k (2-6)
Thus A k (t) is a finite linear combination of positive integer powers of t, i.e. it is a polynomial in t, of the form of eq.2-5.

The matrix size N's dependence comes in several ways. First there is the factor N 2k . The matrix size also appears in the matrix products (each matrix product is a sum over an index which runs from 1 to N), in the traces (it means the first and last index of a matrix product have to be identified, thus there is a Kroenecker's δ ij of two indices). And after Gaussian integration over all matrix elements, the Wick's theorem pairings result in N -l/2 times some product of Kroenecker's δ of pairs of indices (times some elements of the matrix C -1 which are independent of N). The matrix indices thus appear only in sums and δ ′ s, and the result of the sum over indices is an integer power of N. Thus, each A k (t) is a finite sum (sum for each monomial of V k , and the Gaussian integral of each monomial is a finite sum of Wick's pairings) of positive or negative powers of N, i.e. a Laurent polynomial in N.

Definition 2.2

The formal matrix integral Z formal (t) is defined as the formal power series:

Z formal (t) = j Z j t j , Z j = 2j k=0 A k,j (2-7)
and each Z i is a Laurent polynomial in N. Notice that Z 0 = 1.

By abuse of notation, Z formal (t) is often written:

Z formal (t) = formal dM 1 dM 2 . . . dM p e -N t p i,j=1 C ij 2 Tr M i M j -N V (M 1 ,...,Mp) H N ×...×H N dM 1 dM 2 . . . dM p e -N 2t Tr p i,j=1 C ij M i M j (2-8)
but it does not mean that it has anything to do with the corresponding convergent (if it converges) integral. In fact, the integral can be absolutely convergent only if deg(V ) is even and if the t Q corresponding to the highest degree terms of V have a negative real part. But as we shall see below, the relevant case for combinatorics, corresponds to all t Q 's positive, and in that case, the formal integral is NEVER a convergent one.

Definition 2.3 The formal free energy F formal (t) is defined as the formal log of Z formal .

F formal (t) = ln (Z formal (t)) = j F j t j (2-9)
We have F 0 = 0. Each F j is a Laurent polynomial in N.

Combinatorics of maps

Recall that an invariant monomial is a product of terms, each term being the trace of a word in an alphabet of p letters. Thus, an invariant monomial is given by: • the number R of traces, (R -1 is called the crossing number of Q),

• R words written in an alphabet of p letters. The R words can be permuted together, and in each word the letters can be cyclically permuted. We label the invariant monomials by the equivalence classes of those permutations.

Another graphical way of coding invariant monomials is the following:

Definition 2.4
To each invariant monomial Q we associate biunivoquely a Q -gon (generalized polygon) as follows:

• to each word we associate an oriented polygon (in the usual sense), with as many edges as the length of the word, and whose edges carry a "color" between 1 and p, given by the corresponding letter in the word.

• the R words are glued together by their centers on their upper face (in accordance with the orientation), so that they make a surface with R -1 crossings.

• R -1 which is the number of traces minus one (i.e. one trace corresponds to a crossing number zero), is called the crossing number of the Q-gon.

• The degree deg(Q) of the Q-gon is the total number of edges (sum of lengths of all words).

• to Q-gon we associate a symmetry factor s Q = #Aut(Q) which is the number of symmetries which leave Q unchanged.

An example is given in fig. 1. Notice that we allow a Q-gon to be made of polygons with possibly one or two sides. We will most often call the Q-gons polygons. The usual polygons are Q-gons with no crossing i.e. R = 1.

Q = N -3 Tr(M 2 1 M 2 ) Tr(M 3 3 ) Tr(M 2 2 M 4 M 2 1
) of degree 11, is represented by 2 triangles and one pentagon glued together by their center. The dashed lines mean that the 3 centers should actually be seen as only one point. Its symmetry factor is s Q = 3 because we can perform 3 rotations on the triangle of color (3,3,3). Definition 2.6 Let S l,d,p be the set of oriented discrete surfaces such that #edges-#Qgons+#crossings = l, and obtained by gluing together polygons (belonging to Q d,p ) by their sides (following the orientation). The edges of the polygons carry colors among p possible colors (thus each edge of the surface, is at the border of two polygons, and has two colors, one on each side).

Let S l,d,p be the subset of S l,d,p which contains only connected surfaces.

Such surfaces are also called "maps".

Proposition 2.2 S l,d,p is a finite set.

proof:

Indeed, since all polygons of Q d,p have at least 3 sides, we have #edges ≥ 3 2 #polygons, and thus #edges ≤ 2l and #polygons ≤ 4l/3, and thus the number of discrete surfaces in S l , is finite. We can give a very large bound on #S l,d,p . We have:

#S l,d,p ≤ (4dl/3) p (2dl/3)! (4dl/3)! ≤ (4dl/3) p (2dl)! (2-10)
Theorem 2.1 (t'Hooft 1974 and followers): If the potential V is an invariant polynomial given by

V = Q∈Q d,p t Q s Q Q (2-11) then: Z l = S∈S l,d,p 1 #Aut(S) N χ(S) Q t n Q (S) Q i,j (C -1 ) i,j E i,j (S)/2
(2-12)

F l = S∈S l,d,p 1 #Aut(S) N χ(S) Q t n Q (S) Q i,j (C -1 ) i,j E i,j (S)/2 (2-13)
where Z l and F l were defined in def.2.2, def.2.3, and where:

• n Q (S) is the number of Q-gons in S, • E ij (S)
is the number of edges of S which glue two polygons whose sides have colors i and j,

• χ(S) is the Euler characteristic of S.

• Aut(S) is the group of automorphisms of S, i.e. the group of symmetries which leave S unchanged. #Aut(S) is called the symmetry factor.

In other words, Z l is the formal generating function which enumerates discrete surfaces of S l,d,p , according to their Euler characteristics, their number of polygons, number of edges according to their color, number of crossings... F l is the formal generating function for the same surfaces with the additional condition that they are connected.

An example is given in fig. 2. proof:

It is a mere application of Feynman's graphical representation of Wick's theorem2 . The only non-trivial part is the power of N, because N enters not only in the weights but also in the variables of integrations. It was the great discovery of t'Hooft to recognize that the power of N is precisely the Euler characteristics. Let us explain it again.

First, V k is decomposed into a combination of monomials:

V = Q t Q s Q Q , V k = G T k,G G (2-14)
where G is a product of Q's, and

T k,G = Q 1 ∪Q 2 ∪...∪Q k =G t Q 1 t Q 2 . . . t Q k 1 i s Q i
. G is thus a collection of polygons, some of them glued by their centers. So far the polygons of 00 11 00 11

Figure 2: If V = t 4 4 1 N Tr M 4 1 + t4 4 1 N Tr M 4 2 + t 4,4
32N 2 ( Tr M 4 1 ) 2 , the above surface contributes to the term

N 0 t 3 4 t4 t 4,4 (C -1 ) 4 1,1 (C -1 ) 4 1,2 . Indeed M 1 is represented in blue, M 2 in red, so that Tr M 4
1 corresponds to blue squares, Tr M 4 2 corresponds to red squares, and ( Tr M 4 1 ) 2 corresponds to pairs of blue squares glued at their center. Its Euler characteristic is χ = 0 (it is a torus), and this surface has no automorphism (other than identity), i.e. #Aut=1. It corresponds to l = 7.

G

are not yet glued by their sides to form a surface. Remember that each

Q carries a factor N -R if Q is made of R traces.
Then, for each G, the Gaussian integral is computed by Wick's theorem and gives a sum of Wick's pairings, i.e. it is the sum over all possible ways of pairing two M's, i.e. it is the sum over all possible ways of gluing together all polygons by their sides, i.e. corresponds to the sum over all surfaces S. The pairing < M i ab M j cd > of the (a, b) matrix element of M i and the (c, d) matrix element of M j gives a factor:

< M i ab M j cd >= t N (C -1 ) ij δ ad δ bc (2-15)
The double line notation for pairings (see [START_REF] Di Francesco | 2D Gravity and Random Matrices[END_REF]) allows to see clearly that the sum over all indices is N #vertices(S) . The total power of N is thus:

2k - Q R Q + #vertices -#edges -#polygons (2-16) Now, notice that #polygons = Q R Q = k + Q (R Q -1) = k + #crossings (2-17)
Thus the total power of N is:

#vertices -#edges + #polygons -2#crossings = χ (2-18)
which is the Euler characteristic of S.

We leave to the reader to see in the literature how to find the symmetry factor.

Corollary 2.1 N -2 F l is a polynomial in N -2 : F l = l+1 g=0 N 2-2g F l,g (2-19)
proof: Indeed the Euler characteristic of connected graphs is of the form χ = 2 -2g where g is a positive integer and is the genus (number of handles). The fact that it is a polynomial comes from the fact that F l is a finite sum.

It is easy to find some bound on g. We have:

2g -2 = -#vertices + #edges -#polygons + 2#crossings = -#vertices + 2l -#edges + #polygons (2 -20)
and using #edges ≥ 3/2#polygons, we have:

2g -2 ≤ -#vertices + 2l - 1 2 #polygons ≤ 2l (2-21)

Topological expansion

Definition 2.7 We define the genus g free energy as the formal series in t:

F (g) (t) = - ∞ l=0 t l+2-2g F l,g (2-22)
F (g) is the generating function for connected oriented discrete surfaces of genus g.

Remark: the minus sign in front of F (g) is there for historical reasons, because in thermodynamics the free energy is -ln Z.

There is no reason a priori to believe that F (g) (t) might have a finite radius of convergence in t. However, for many classical matrix models, it is proved that ∀g, F (g) has a finite radius of convergence because it can be expressed in terms of algebraic functions.

There is also no reason a priori to believe that the F (g) 's should be the limits of convergent matrix integrals. There are many works which prove that the number of terms in F (g) grows with g like (βg)! for some β. If t and all t Q 's are positive (this is the interesting case for combinatorics and statistical physics because we want all surfaces to be counted with a positive weight), then F (g) is positive and grows like (βg)!, and therefore the sum of the topological series CANNOT be convergent (even under Borel resummation). For negative t, it is only an asymptotic series, and at least in some cases, it can be made convergent using Borel transforms.

Loop equations

Loop equations is the name given to Schwinger-Dyson equations in the context of random matrices [START_REF] Spenta | On The Dyson-Schwinger Equations Approach To The Large N Limit: Model Systems And String Representation Of Yang-Mills Theory[END_REF]. The reason for that name is explained below. Let us recall that Schwinger-Dyson equations are in fact nothing but integration by parts, or the fact that the integral of a total derivative vanishes.

In particular, in the context of convergent matrix integrals we have:

0 = i<j H p N dM 1 dM 2 . . . dM p ∂ ∂ReM k i,j -i ∂ ∂ImM k i,j (G(M 1 , . . . , M p ) + G(M 1 , . . . , M p ) † ) ij e -N t p i,j=1 C ij 2 Tr M i M j -N V (M 1 ,...,Mp) + i H p N dM 1 dM 2 . . . dM p ∂ ∂M k i,i (G(M 1 , . . . , M p ) + G(M 1 , . . . , M p ) † ) ii e -N t p i,j=1 C ij 2 Tr M i M j -N V (M 1 ,...,Mp) (3 -1)
where G is any non commutative polynomial, and k is an integer between 1 and p.

Therefore, Schwinger-Dyson equations for matrix integrals give relationships between expectation values of invariant polynomials. Namely:

N t Tr j C kj M j -ND k (V ) G = K k (G) (3-2)
where D k is the non commutative derivative with respect to M k , and K k (G) is some invariant polynomial which can be computed by the following rules:

• Leibnitz rule K k (A(M 1 , . . . , M k , . . . , M p )B(M 1 , . . . , M k , . . . , M p )) = (K k (A(M 1 , . . . , M k , . . . , M p )B(M 1 , . . . , m k , . . . , M p ))) m k →M k + (K k (A(M 1 , . . . , m k , . . . , M p )B(M 1 , . . . , M k , . . . , M p ))) m k →M k (3-3)
• split rule

K k (A(M 1 , . . . , m k , . . . , M p )M l k B(M 1 , . . . , m k , . . . , M p )) = l-1 j=0 Tr (A(M 1 , . . . , m k , . . . , M p )M j k ) Tr (M l-j-1 k B(M 1 , . . . , m k , . . . , M p ))(3-4)
• merge rule

K k (A(M 1 , . . . , m k , . . . , M p ) Tr (M l k B(M 1 , . . . , m k , . . . , M p ))) = l-1 j=0 Tr (A(M 1 , . . . , m k , . . . , M p )M j k B(M 1 , . . . , m k , . . . , M p )M l-j-1 k ) (3-5) • no M k rule K k (A(M 1 , . . . , m k , . . . , M p )) = 0 (3-6)
Since each rule allows to strictly decrease the partial degree in M k , this set of rules allows to compute K k (G) for any G.

For any G and any k we get one loop equation of the form eq.3-2.

Definition 3.1

The formal expectation value of some invariant polynomial P (M 1 , . . . , M k ) is the formal power series in t defined by:

A k,P (t) = H N ×...×H N dM 1 dM 2 . . . dM p N 2k t -k k! P V k e -N 2t Tr p i,j=1 C ij M i M j H N ×...×H N dM 1 dM 2 . . . dM p e -N 2t Tr p i,j=1 C ij M i M j (3-7)
A k,P (t) is a polynomial in t, of the form:

A k,P (t) = deg(P )/2+k/2≤j≤deg(P )/2+kd/2-k A k,P,j t j (3-8)
and we define the following quantity

A P,j (t) = 2j-deg P k=0 A k,P,j (3-9)
and the formal series

A P (t) = ∞ j=deg P/2
A P,j t j (3-10)

Again, each A k,P , A k,P,j , A P,j is a Laurent polynomial in N.

The formal expectation value of P is defined as:

P (M 1 , . . . , M k ) formal = A P (t) Z formal (t) (3-11)
where the division by Z formal is to be taken in the sense of formal series, and it can be performed since Z formal (t) = ∞ j=0 Z j t j with Z 0 = 1.

The formal expectation value is often written by abuse of notations

< P > formal = formal dM 1 dM 2 . . . dM p P e -N t p i,j=1 C ij 2 Tr M i M j -N V (M 1 ,...,Mp) formal dM 1 dM 2 . . . dM p e -N t p i,j=1 C ij 2 Tr M i M j -N V (M 1 ,...,Mp) (3-12)
Theorem 3.1 The formal expectation values of the formal matrix integral satisfy the same loop equations as the convergent matrix integral ones, i.e. they satisfy eq.3-2 for any k and G.

proof:

It is clear that Gaussian integrals, and thus formal integrals satisfy eqs.3-1. The remainder of the derivation of loop equations for convergent integrals is purely algebraic, and thus it holds for both convergent and formal integrals.

On a combinatoric point of view, loop equations are the generalisation of Tutte's equations for counting planar maps [START_REF] Tutte | A census of planar triangulations[END_REF][START_REF] Tutte | A census of planar maps[END_REF]. This is where the name "loop equations" comes from: indeed, similarly to theorem.2.1, formal expectation values of traces are generating functions for open discrete surfaces with as many boundaries as the number of traces (and again the power of N is the Euler characteristic of the surface). The boundaries are "loops", and the combinatorical interpretation of Schwinger-Dyson equations is a recursion on the size of the boundaries, i.e. how to build discrete surfaces by gluing loops à la Tutte [START_REF] Tutte | A census of planar triangulations[END_REF][START_REF] Tutte | A census of planar maps[END_REF].

Notice that in general, the loop equations don't have a unique solution. One can find a unique solution only with additional constraints not contained in the loop equations themselves. Thus, the fact that both convergent and formal matrix models obey the same loop equations does not mean they have to coincide. Many explicit examples where both do not coincide have been found in the literature. It is easy to see on a very simple example that Schwinger-Dyson equations can't have a unique solution: consider the Airy function γ e 1 3 t 3 -tx dt where γ is any path in the complex plane, going from ∞ to ∞ such that the integral is convergent. There are only two homologicaly independent choices of γ (one going from +∞ to e 2iπ/3 ∞ and one from +∞ to e -2iπ/3 ∞). Schwinger-Dyson equations are: < nt n-1 + t n+2 -xt n >= 0 for all n. It is clear that loop equations are independent of the path γ, while their solution clearly depends on γ.

Theorem 3.2 The formal matrix integral is the solution of loop equations with the following additional requirements:

-the expectation value of every monomial invariant is a formal power series in N -2 .

-the t → 0 limit of the expectation value of any monomial invariant of degree ≥ 1 vanishes:

lim t→0 < Q >= 0 if Q = 1 (3-13)
proof:

The fact that all expectation values have a formal N -2 expansion follows from the construction. The fact that lim t→0 < Q >= 0 if Q = 1, follows from the fact that we are making a formal Taylor expansion at small t, near the minimum of the quadratic part, i.e. near M i = 0, i = 1, . . . , p.

However, even those requirements don't necessarily provide a unique solution to loop equations. Notice that there exist formal solutions of loop equations which satisfy the first point (there is a formal N -2 expansion), but not the second point (lim t→0 < Q >= 0). Those solutions are related to so-called "multicut" solutions, they also have a known combinatoric interpretation, but we don't consider them in this short review (see for instance [START_REF] Eynard | The 2-matrix model, biorthogonal polynomials, Riemann-Hilbert problem, and algebraic geometry[END_REF][START_REF] Bonnet | Breakdown of universality in multi-cut matrix models[END_REF]

for examples).

There is a conjecture about the relationship between different solutions of loop equations: Conjecture 3.1 The convergent matrix integral (we assume V to be such that the integral is convergent, i.e. the highest t Q 's have negative real part)

Z conv = H p N dM 1 dM 2 . . . dM p e -N t p i,j=1 C ij 2 Tr M i M j -N V (M 1 ,...,Mp) (3-14)
is a finite linear combination of convergent formal solutions of loop equations (i.e. a formal solution of loop equations ln Z = -∞ g=G N 2-2g F (g) , such that the N -2 series is convergent.), i.e.

Z conv = i c i Z i , ln Z i = - ∞ g=0 N 2-2g F (g) i (3-15)
Hint: It amounts to exchanging the large N and small t limits. First, notice that convergent matrix integrals are usualy defined on H p N , but can be defined on any "integration path" in the complexified of H p N , which is M N (C) p , as long as the integral is convergent. The homology space of such contours is of finite dimension (because there are a finite number of variables p × N 2 , and a finite number of possible sectors at ∞ because the integration measure is the exponential of a polynomial). Thus, the set of "generalized convergent matrix integrals" defined on arbitrary paths, is a finite dimensional vector space which we note: Gen. The hermitian matrix integral defined on H p N is only one point in that vector space. Second, notice that every such generalized convergent matrix integral satisfies the same set of loop equations, and that loop equations of type eq.3-1 are clearly linear in Z. Thus, the set of solutions of loop equations is a vector space which contains the vector space of generalized convergent matrix integrals.

Third, notice that formal integrals are solutions of loop equations, and therefore, formal integrals which are also convergent, belong to the vector space of generalized convergent matrix integrals.

Fourth, one can try to compute any generalized convergent matrix integral by small t saddle point approximation (at finite N). In that purpose, we need to identify the small t saddle points, i.e. a set of matrices (M 1 , . . . , M p ) ∈ M N (C) p such that ∀i, j, k one has:

∂ ∂M k i,j l,m Tr ( 1 2 C l,m M l M m ) -V (M 1 , . . . , M p ) Mn=M n = 0 (3-16)
and such that Im l,m

Tr (

1 2 C l,m M l M m ) -V (M 1 , . . . , M p ) = Im l,m Tr ( 1 2 C l,m M l M m ) -V (M 1 , . . . , M p ) (3-17) and Re l,m Tr ( 1 2 C l,m M l M m ) -V (M 1 , . . . , M p ) ≥ Re l,m Tr ( 1 2 C l,m M l M m ) -V (M 1 , . . . , M p ) (3-18)
If such a saddle point exist, then it is possible to replace exp N 2 t V by its Taylor series expansion in the integral and exchange the summation and the integration (because both the series and the integral are absolutely convergent, this is nothing but WKB expansion). This proves that saddle points are formal integrals and at the same time they are generalized convergent integrals, thus they are formal convergent integrals.

The conjecture thus amounts to claim that saddle points exist, and that there exist as many saddle points as the dimension of Gen, and that they are independent, so that the saddle points form a basis of Gen.

Notice that a linear combination of convergent formal solutions has no N -2 expansion in general, and thus the set of convergent formal integrals is not a vector space. This conjecture is proved for the 1-matrix model with real potential [START_REF] Deift | Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory[END_REF][START_REF] Ercolani | Asymptotics of the partition function for random matrices via Riemann-Hilber technics and applications to graphical enumeration[END_REF], and for complex potentials it can be derived from Bertola-Man Yue [3] (indeed, the asymptotics of the partition function follow from those of the orthogonal polynomials). It is the physical intuition that it should hold for more general cases. It somehow corresponds to the small t saddle point method. Each saddle point has a WKB expansion, i.e. is a convergent formal solution, and the whole function is a sum over all saddle points. The coefficients of the linear combination reflect the homology class of the path (here H p N ) on which Z is defined. This path has to be decomposed as a linear combination of steepest descent paths. The coefficients of that linear combination make the c i 's of eq.3-15 (this is the generalisation of the idea introduced in [START_REF] Bonnet | Breakdown of universality in multi-cut matrix models[END_REF]).

Examples 4.1 1-matrix model

Z formal = dMe -N t Tr (V(M )) dMe -N t Tr ( C 2 M 2 ) (4-1)
where

V(M) = C 2 M 2 -V (M) is a polynomial in M, such that V (M) contains only terms with degree ≥ 3.
For any α and γ, let us parametrise the potential V as:

x(z) = α + γ(z + 1/z) V ′ (x(z)) = d j=0 v j (z j + z -j ) (4-2)
We determine α and γ by the following conditions:

v 0 = 0 , v 1 = t γ (4-3)
i.e. α and β are solutions of an algebraic equation and exist for almost any t, and they are algebraic functions of t. In general, they have a finite radius of convergence in t.

We chose the branches of α(t) and γ(t) which vanish at t = 0:

α(t = 0) = 0 , γ(t = 0) = 0 (4-4)
Then we define:

y(z) = 1 2 d j=1 v j (z j -z -j ) (4-5)
The curve (x(z), y(z)) z ∈ C is called the spectral curve. It is a genus zero hyperelliptical curve y 2 = Polynomial(x). It has only two branch points solutions of x ′ (z) = 0 which correspond to z = ±1, i.e. x = α ± 2γ. y as a function of x has a cut along the segment [α -2γ, α + 2γ]. Notice that we have:

Res z→∞ ydx = t = -Res z→0 ydx (4-6) Res z→∞ V ′ (x)ydx = 0 , Res z→∞ xV ′ (x)ydx = t 2 (4-7)
Then one has [START_REF] Bertola | Second and Third Order Observables of the Two-Matrix Model[END_REF]:

F (0) = 1 2 Res z→∞ V(x)ydx -t Res z→∞ V(x) dz z - 3 2 t 2 -t 2 ln γ 2 C t = 1 2 - j≥1 γ 2 j (v j+1 -v j-1 ) 2 - 2γt j (-1) j (v 2j-1 -v 2j+1 ) - 3 2 t 2 -t 2 ln (Cγ 2 /t) (4 -8)
and: [START_REF] Chekhov | Genus one corrections to multi-cut matrix model solutions[END_REF][START_REF] Eynard | Genus one contribution to free energy in hermitian two-matrix model[END_REF]]

F (1) = - 1 24 ln γ 2 y ′ (1)y ′ (-1) t 2 (4-9)
Expressions are known for all F (g) 's and we refer the reader to [START_REF] Eynard | Topological expansion for the 1-hermitian matrix model correlation functions[END_REF][START_REF] Chekhov | Hermitean matrix model free energy: Feynman graph technique for all genera[END_REF]. Those expressions are detailed in the next section about the 2-matrix model, and one has to keep in mind that the 1-matrix model is a special case of the 2-matrix model with

V 1 (x) = V(x) + x 2
2 and V 2 (y) = y 2 2 . As a fore-taste, let us just show an expression for F (2) :

-2F (2) = Res

z 1 →±1 Res z 2 →±1
Res

z 3 →±1 Φ(z 1 )E(z 1 , z 2 )E(1/z 1 , z 3 ) 1 (z 2 -1 z 2 ) 2 1 (z 3 -1 z 3 ) 2 +2 Res z 1 →±1 Res z 2 →±1 Res z 3 →±1 Φ(z 1 )E(z 1 , z 2 )E(z 2 , z 3 ) 1 ( 1 z 1 -1 z 2 ) 2 1 (z 3 -1 z 3 ) 2 +2 Res z 1 →±1 Res z 2 →±1 Res z 3 →±1 Φ(z 1 )E(z 1 , z 2 )E(z 2 , z 3 ) 1 ( 1 z 1 -1 z 3 ) 2 1 ( 1 z 2 -z 3 ) 2 (4 -10)
where the residue is first evaluated for z 3 then z 2 then z 1 , and where:

E(z, z ′ ) = 1 4γ 1 z ′ (z -z ′ )(z -1 z ′ )y(z ′ ) (4-11) Φ(z) = - 1 4γ 1 zy(z)(z -1 z ) z 1/z ydx (4-12)

Example triangulated maps

Consider the particular case V (x) = t 3 3 x 3 .

Let T = tt 2 3 C 3 , and a be a solution of:

a -a 3 = 4T (4-13)
and consider the branch of a(T ) which goes to 1 when T = 0. If we parametarize:

T = tt 2 3 C 3 = sin 3φ 6 √ 3 (4-14)
we have:

a = cos ( π 6 -φ) cos ( π 6 ) (4-15)
We have:

α = C 2t 3 (1 -a) , γ 2 = t aC (4-16
)

v 0 = 0 , v 1 = t γ , v 2 = -t 3 γ 2 (4-17)
which gives:

F (0) = 5 12 t 2 - t 4C + C 6t 1 a - t 2 2 ln a (4-18)
F (1) = - 1 24 ln 1 -2a √ 1 -a 2 a 2 (4-19)
The radius of convergence of

F (g) is |T | < 1 6 √
3 for all g.

Example square maps

Consider the particular case V (x) = t 4 4 x 4 , and write

T = t t 4 C 2 . Define: b = √ 1 -12T (4-20)
We find

α = 0 , γ 2 = 2t C(1 + b) (4-21) v 1 = t γ , v 2 = 0 , v 3 = -t 4 γ 3 (4-22)
We find:

F (0) = t 2 2 - (1 -b) 2 12(1 + b) 2 + 2(1 -b) 3(1 + b) + ln 1 + b 2 (4-23) F (1) = - 1 12 ln 2b 1 + b (4-24)
The radius of convergence of F (g) is |T | < 1 12 for all g.

2-Matrix model

The 2-matrix model was introduced by Kazakov [START_REF] Kazakov | Ising model on a dynamical planar random lattice: exact solution[END_REF], as the Ising model on a random map.

Z formal = dM 1 dM 2 e -N t Tr (V 1 (M 1 )+V 2 (M 2 )-C 12 M 1 M 2 ) dM 1 dM 2 e -N t Tr ( C 11 2 M 2 1 + C 22 2 M 2 2 -M 1 M 2 ) (4-25)
where

V 1 (M 1 ) = C 11 2 M 2 1 -V 1 (M 1 ) is a polynomial in M 1 , such that V 1 (M 1
) contains only terms with degree ≥ 3, and where

V 2 (M 2 ) = C 22 2 M 2 2 -V 2 (M 2 ) is a polynomial in M 2 , such that V 2 (M 2
) contains only terms with degree ≥ 3, and we assume C 12 = 1:

C = C 11 -1 -1 C 22 (4-26)
Indeed, it generates surfaces made of polygons of two possible colors (call them polygons carrying a spin + or -) glued by their sides (no crossing here). The weight of each surface depends on the number of neighbouring polygons with same spin or different spin, which is precisely the Ising model. If

C 11 = C 22 and V 1 = V 2 ,
this is an Ising model without magnetic field, otherwise it is an Ising model with magnetic field.

Let us describe the solution.

Consider the following rational curve

x(z) = γz + deg V ′ 2 k=0 α k z -k y(z) = γz -1 + deg V ′ 1 k=0 β k z k (4-27)
where all coefficients γ, α k , β k are determined by:

y(z) -V ′ 1 (x(z)) ∼ z→∞ - t γz + O(z -2 ) x(z) -V ′ 2 (y(z)) ∼ z→0 - tz γ + O(z 2 ) (4-28)
The coefficients γ, α k , β k are algebraic functions of t, and we must choose the branch such that γ → 0 at t = 0. The curve (x(z), y(z)) z ∈ C is called the spectral curve. It is a genus zero algebraic curve. There are deg V 2 branch points solutions of x ′ (z) = 0.

Notice that we have: Res

z→∞ ydx = t = -Res z→0 ydx (4-29)
Then one has [START_REF] Bertola | Second and Third Order Observables of the Two-Matrix Model[END_REF]:

F (0) = 1 2 Res z→∞ V 1 (x)ydx + Res z→0 (xy -V 2 (y))ydx -t Res z→∞ V 1 (x) dz z -t Res z→0 (xy -V 2 (y)) dz z - 3 2 t 2 -t 2 ln γ 2 det C t (4 -30)
and [START_REF] Eynard | Genus one contribution to free energy in hermitian two-matrix model[END_REF]:

F (1) = - 1 24 ln ( tdeg(V 2 ) ) 2 t 2 deg V 2 i=1 γy ′ (a i ) (4-31)
where a i are the solutions of x ′ (a i ) = 0, and tdeg(V 2 ) is the leading coefficient of V 2 .

The other F (g) 's are found as follows [START_REF] Chekhov | Free energy topological expansion for the 2-matrix model[END_REF]: Let a i , i = 1, . . . , deg V 2 be the branch points, i.e. the solutions of x ′ (a i ) = 0. If z is close to a branch-point a i , we denote z the other point such that

z → a i , x(z) = x(z) and z → a i (4-32)
Notice that z depends on the branch-point, i.e. z is not globally defined. We also define:

Φ(z) = z z 0 ydx (4-33)
Φ(z) depends on the base-point z 0 and on the path between z and z 0 , but the calculations below don't depend on that.

We define recursively:

W (0) 1 (p) = 0 (4-34) W (0) 2 (p, q) = 1 (p -q) 2 (4-35) W (g) k+1 (p, p 1 , . . . , p k ) = - 1 2 i Res z→a i (z -z)dz (p -z)(p -z)(y(z) -y(z)x ′ (z) W (g-1) k+2 (z, z, p 1 , . . . , p k ) + g h=0 I⊂{1,2,...,k} W (h) 1+|I| (z, p I )W (g-h) 1+k-|I| (z, p K/{I} ) (4 -36)
This system is a triangular system, and all W (g) k are well defined in a finite number of steps ≤ g(g+1) 2 + k. Then we have [START_REF] Chekhov | Free energy topological expansion for the 2-matrix model[END_REF]:

F (g) = 1 2 -2g i Res z→a i Φ(z)W (g) 1 (z) dz , g > 2 (4-37)
The 1-matrix case is a special case of this when the curve is hyperelliptical (in that case z is globally defined), it corresponds to deg V 2 = 2.

Chain of matrices

Z formal = dM 1 . . . dM p e -N t Tr ( p i=1 V i (M i )-p-1 i=1 M i M i+1 ) dM 1 . . . dM p e -N t Tr ( p i=1 C ii 2 M 2 i -p-1 i=1 M i M i+1 ) (4-38)
where

V i (M i ) = C ii 2 M 2 i -V i (M i ) is a polynomial in M i , such that V i (M i
) contains only terms with degree ≥ 3. The matrix C is:

C =     C 11 -1 -1 C 22 -1 . . . -1 C pp -1     (4-39)
Consider the following rational curve

x i (z) = r i k=-s i α i,k z k ∀i = 0, . . . , p + 1 (4-40)
where all coefficients γ, α k , β k are determined by:

x i+1 + x i-1 = V ′ (x i ) ∀i = 1, . . . , p x 0 (z) ∼ z→∞ t γz + O(z -2 ) x p+1 (z) ∼ z→0 tz γ + O(z 2 ) (4 -41)
The coefficients γ, α i,k are algebraic functions of t, and we must choose the branch such that γ → 0 at t = 0. The curve (x 1 (z), x 2 (z)) z ∈ C is called the spectral curve. It is a genus zero algebraic curve.

Notice that we have ∀i = 1, . . . , p -1:

Res z→∞ x i+1 dx i = t = -Res z→0 x i+1 dx i (4-42)
Then one has [START_REF] Eynard | Master loop equations, free energy and correlations for the chain of matrices[END_REF]:

F (0) = 1 2 p i=1 Res z→∞ (V i (x i ) - 1 2 x i V ′ i (x i ))x i+1 dx i -t p i=1 Res z→∞ (V i (x i ) - 1 2 x i V ′ i (x i )) dz z -t 2 ln γ 2 det C t (4 -43)
F (1) and the other F (g) 's have never been computed, but it is strongly believed that they should be given by the same formula as in the 2-matrix case.

Closed Chain of matrices

Z formal = dM 1 . . . dM p e -N t Tr ( p i=1 V i (M i )-p-1 i=1 M i M i+1 -MpM 1 ) dM 1 . . . dM p e -N t Tr ( p i=1 C ii 2 M 2 i -p-1 i=1 M i M i+1 -MpM 1 ) (4-44)
It is the case where the matrix C of quadratic interactions has the form:

C =     C 11 -1 -1 -1 C 22 -1 . . . -1 -1 C pp -1     (4-45)
This model is yet unsolved, apart from very few cases (p = 2, p = 3 (Potts Model), p = 4 with cubic potentials), and there are also results in the large p limit. This model is still a challenge.

O(n) Model

Z formal = dM dM 1 . . . dM n e -N t Tr ( C M 2 M 2 + C 2 n i=1 M 2 i -V (M )-n i=1 M M 2 i ) dM dM 1 . . . dM n e -N t Tr ( C M 2 M 2 + C 2 n i=1 M 2 i ) (4-46)
where V contains at least cubic terms. We write:

V(x) = -V (-(x + C 2 )) + C M 2 (x + C 2 ) 2 (4-47)
This model can easily be analytically continued for non integer n's. Indeed, combinatoricaly, it is the generating function of a loop gas living on the maps. n is the "fugacity" of loops, i.e. the n dependence of the weight of each configuration is n # loops , and the C dependence is C -length of loops . One often writes:

n = 2 cos (νπ) (4-48)
The O(n) model was introduced by I. Kostov in [START_REF] Kostov | O(n) vector model on a planar random lattice: spectrum of anomalous dimensions[END_REF] then in [START_REF] Kostov | Strings with Discrete Target Space[END_REF]21], and it plays a very important role in many areas of physics, and lately, it has started to play a special role in string theory, as an effective model for the check of ADS-CFT correspondence.

The leading order 1-cut solution of this model is well known [START_REF] Eynard | The O(n) model on a random surface: critical points and large order behaviour[END_REF][START_REF] Eynard | Exact solution of the O(n) model on a random lattice[END_REF][START_REF] Eynard | More on the exact solution of the O(n) model on a random lattice and an investigation of the case -n-¿2[END_REF].

For any two distinct complex numbers a and b, define:

m = 1 - a 2 b 2 , τ = iK ′ (m) K(m) (4-49)
where K(m) = K ′ (1 -m) are the complete elliptical integrals ( [START_REF] Abramowitz | Handbook of Mathematical Functions[END_REF]). We also consider the following elliptical function (defined on the torus (1, τ )):

x(u) = ib cn(2K(m)u, m) sn(2K(m)u, m) (4-50)
4.8 6-vertex model

Z formal = dM dM † e -N t Tr (M M † -M 2 M 2 † +cos β(M M † ) 2 ) dM dM † e -N t Tr (M M † ) (4-70)
where M is a complex matrix. The loop equations have been written and solved to leading order, in particular in [START_REF] Zinn-Justin | The six-vertex model on random lattices[END_REF][START_REF] Kostov | Exact Solution of the Six-Vertex Model on a Random Lattice[END_REF].

ADE models

Given a Dynkin diagram of A, D or E Lie algebra, and let A be its adjacency matrix (A ij = A ji =# links between i and j). We define:

Z formal = i dM i i<j dB ij e -N T Tr ( i 1 2 M 2 i -g 3 M 3 i + 1 2 i,j B ij B t ij + K 2 i,j A ij B ij B t ij M i ) (4-71)
where B ji = B t ij are complex matrices, and M i are hermitian matrices. The loop equations have been written and solved to leading order, in particular in [START_REF] Kostov | Strings with Discrete Target Space[END_REF][START_REF] Kostov | Gauge Invariant Matrix Model for the ADE Closed Strings[END_REF].

ABAB models

Z formal = n 1 i=1 dA i n 2 j=1 dB j e -N T Tr ( i A 2 i 2 + i B 2 i 2 +g i,j A i B j A i B j (4-72)
This model is yet unsolved, apart from few very special cases [START_REF] Kazakov | Two-Matrix model with ABAB interaction[END_REF]. However, its solution would be of great interest in the understanding of Temperley Lieb algebra.

Discussion

Summary of some known results

We list here some properties which are rather well understood.

• The fact that formal matrix integrals are generating functions for counting discrete surfaces (also called maps) is well understood, as was explained in this review.

• The fact that formal matrix integrals i.e. generating functions of maps satisfy Schwinger-Dyson equations is well understood.

• The fact that formal matrix integrals and convergent integrals don't coincide in general is well understood. In the examples of the 1-matrix model, 2-matrix Ising model or chain of matrices, it is understood that they may coincide only in the "1-cut case", i.e. if the classical spectral curve has genus zero.

• The fact that the formal 1-matrix, 2-matrix or chain of matrices integrals are τ functions of some integrable hierarchies is well understood too.

• For the formal 1-matrix model and 2-matrix Ising model, all F (g) 's have been computed explicitly. The result is written in terms of residues of rational functions.

• For the chain of matrices, F (0) is known explicitly [START_REF] Eynard | Master loop equations, free energy and correlations for the chain of matrices[END_REF], and it is strongly believed that all F (g) 's are given by the same expression as for the 2-matrix model.

• Multi-cut formal matrix models are well studied too, and they can be rewritten in terms of multi-matrix models. For the 1 and 2 matrix models, the expressions of the F (g) 's are known explicitly (in terms of residues of meromorphic forms on higher genus spectral curves).

Some open problems

• the large N asymptotics of convergent matrix integrals, are not directly relevant for combinatorics, but are a very important question for other applications, in particular bi-orthogonal polynomials, universal statistical properties of eigenvalues of large random matrices, and many other applications. This question is highly non-trivial, and so far, it has been solved only for the 1-matrix model [START_REF] Bleher | Semiclassical asymptotics of orthogonal polynomials, Riemann-Hilbert problem, and universality in the matrix model[END_REF][START_REF] Deift | Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory[END_REF][START_REF] Ercolani | Asymptotics of the partition function for random matrices via Riemann-Hilber technics and applications to graphical enumeration[END_REF], and a few other cases (e.g. the 6-vertex model [START_REF] Bleher | Exact Solution of the Six-Vertex Model with Domain Wall Boundary Conditions. Disordered Phase[END_REF]). The method mostly used to prove the asymptotic formulae is the Riemann-Hilbert method [START_REF] Bleher | Semiclassical asymptotics of orthogonal polynomials, Riemann-Hilbert problem, and universality in the matrix model[END_REF][START_REF] Deift | Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory[END_REF], which consists in finding a Riemann-Hilbert problem for the actual matrix integral and for its conjectured asymptotics, and compare both. There is a hope that probabilists' methods like large deviations could be at leats as efficient.

• For the 2-matrix model and chain of matrices, the topological expansion of formal "mixed" expectation values (e.v. of invariant monomials whose words contain at least 2 different letters) has not yet been computed. This problem is a challenge in itself, and has applications to the understanding of "boundary conformal field theory". In terms of combinatorics, it corresponds to find generating functions for open surfaces with boundaries of prescribed colors.

• Many matrix models have not yet been solved, even to planar order. For instance the closed chain of matrices where C ij = δ i,j+1 + δ i,j-1 + C i • Limits of critical points are still to be understood and classified. Only a small number of critical points have been studied so far. They have been related to KdV or KP hierarchies. Critical points, i.e. radius of convergence of the t-formal power series, are in relationship with asymptotics numbers of large maps (through Borel's transform), and thus critical points allow to count maps made of a very large number of polygons, i.e. they can be interpreted as counting continuous surfaces (this was the idea of 2D quantum gravity in the 80's and early 90's). This is yet to be better understood [START_REF] Cicuta | Phase transitions and random matrices[END_REF][START_REF] Bleher | Double scaling limit in random matrix models and a nonlinear hierarchy of differential equations[END_REF].

• extensions to other types of matrices (non-hermitian) have been very little studied compared to the hermitian case, and much is still to be understood. For instance real symmetric matrices or quaternion-self-dual matrices have been studied from the begining [START_REF] Mehta | Random Matrices[END_REF], and they count non-orientable maps. Complex matrices, and normal complex matrices have played an increasing role in physics, because of their relationship with Laplacian growth problems [START_REF] Wiegmann | Large N expansion for normal and complex matrix ensembles[END_REF], or some limits of string theory [4]. Complex matrices count maps with arrows on the edges (see the 6vertex model [START_REF] Zinn-Justin | The six-vertex model on random lattices[END_REF]). Other types of matrix ensembles have been introduced in relationship with symmetric spaces [START_REF] Zirnbauer | Riemannian symmetric superspaces and their origin in random matrix theory[END_REF], and it is not clear what they count.

• And there are so many applications of random matrices to physics, mathematics, biology, economics, to be investigated...

Figure 1 :

 1 Figure 1: The invariant monomial Q= N -3 Tr(M 2 1 M 2 ) Tr(M 3 3 ) Tr(M 2 2 M 4 M 2 1) of degree 11, is represented by 2 triangles and one pentagon glued together by their center. The dashed lines mean that the 3 centers should actually be seen as only one point. Its symmetry factor is s Q = 3 because we can perform 3 rotations on the triangle of color(3,3,3).

Definition 2 . 5

 25 Let p ≥ 1 and d ≥ 3 be given integers. Let Q d,p be the set of all invariant monomials Q (or polygons) of degree 3 ≤ deg(Q) ≤ d. Q d,p is clearly a finite set.

  δ ii and C p1 = C 1p = 1. For the Potts model, 6-vertex model, 3-color model, O(n) model, ADE models, only the planar resolvent is known. For the A n B m A n B m , almost nothing is known, although this model describes the combinatorics of Temperly Lieb algebra.

Although Feynman's graphs are sometimes regarded as non-rigorous, let us emphasize that it is only when Feynman's graphs and Wick's theorem are used for functional integrals that they are non-rigorous. Here we have finite dimensional Gaussian integrals, and Wick's theorem and Feynman's graphs are perfectly rigorous.

Acknowledgements

I would like to thank Philippe Di Francesco for his critical reading of the manuscript. This work is partly supported by the Enigma European network MRT-CT-2004-5652, by the ANR project Géométrie et intégrabilité en physique mathématique ANR-05-BLAN-0029-01, and by the Enrage European network MRTN-CT-2004-005616.

where sn and cn are the elliptical sine and cosine functions.

Then we define the following function on the universal covering (i.e. on the complex plane):

where H is a normalization constant such that:

It satisfies:

Then we define:

where Pol means the polynomial part in x at large x (i.e. at u → 0), and the subscript + and -mean the even and odd part, and where

A and B are polynomials of x 2 . Then, a and b are completely determined by the 2 conditions:

Once we have determined a, b, m, A, B, we define the resolvent:

which is the first term of the formal large N expansion of:

and which satisfies:

The free energy is then found by:

where

All this is described in [START_REF] Eynard | Gravitation quantique bidimensionnelle et matrices alatoires[END_REF]. The special cases of n integer, and in general when ν is rational, can be computed with more details.

Potts model

or equivalently:

The Random lattice Potts model was first introduced by V. Kazakov in [START_REF] Kazakov | Exactly solvable Potts models, bond-and tree-like percolation on dynamical (random) planar lattice[END_REF][START_REF] Kazakov | Percolation On A Fractal With The Statistics Of Planar Feynman Graphs: Exact Solution[END_REF]. The loop equations have been written and solved to leading order, in particular in [START_REF] Daul | [END_REF][START_REF] Zinn-Justin | The dilute Potts model on random surfaces[END_REF][START_REF] Bonnet | The Potts-q random matrix model : loop equations, critical exponents, and rational case[END_REF].

3-color model

dM 1 dM 2 dM 3 e -N t Tr ( 1 2 (M 2 1 +M 2 2 +M 2 3 ))

(4-69)

The loop equations have been written and solved to leading order, in particular in [START_REF] Eynard | An iterative solution of the three colour Problem on a random lattice[END_REF][START_REF] Kostov | Exact Solution of the Three-color Problem on a Random Lattice[END_REF].


Yacoubou Salissou
email: yacoubou.salissou@usherbrooke.ca

Raymond Panneton Gaus

COMPARISON OF METHODS FOR CHARACTERIZING SOUND ABSORBING MATERIALS

INTRODUCTION

Open-cell porous materials are widely used as acoustic absorbent media in the transport industry. In order to have a prior knowledge of their acoustic behaviour, different models have been developed [1][2][3][4]. Among all these models, the Johnson-Champoux-Allard [2,4] is widely used because of it simplicity and accuracy. This model uses five parameters (open porosity, static airflow resistivity, tortuosity, viscous characteristic length and thermal characteristic length) which describe the internal structure of porous materials at the macroscopic scale. Different methods have been developed in order to characterize those parameters. Some of them are based on the physical and mathematical definition of the parameters. However, these methods, qualified as direct methods, require dedicated equipments. The second approach is based on the acoustical model from which analytical expressions linking the material parameters to acoustical measurements are derived. The methods using this approach are qualified as analytical inversion or indirect methods. Finally, the last approach is based on an optimisation problem where the material parameters are adjusted in the acoustic model to reproduce acoustical measurements. The methods of this group are qualified as inverse methods.

In this paper, three samples of metal foam are characterized using direct, indirect and inverse methods. The objective is to highlight that the methods may yield large variability in the found parameters. A discussion is given to explain the observed variability and the limitations of the methods.

CHARACTERIZATION METHODS

Direct measurement of the open porosity is performed using the Archimedes principle following the in-air missing mass method [5]. This method gives a direct measured value of open porosity through measurement of sample weight in vacuum and in air, and predicts the measurement error. In this study, because of the lack of material, the three samples will be put together (as one sample) to satisfied the minimum material volume required by the method. The direct method used to measure the static airflow resistivity is based on the method proposed by Stinson & Daigle [6].

The indirect method (IM) used in this work is based on the technique developed by Panneton & Olny [7,[START_REF] Olny | Proc. of Forum Acusticum[END_REF]. Assuming dynamic density, dynamic bulk modulus, and open porosity known, analytical solutions are used to determine the static airflow resistivity, tortuosity, viscous characteristic dimension (VCD), and thermal characteristic dimension (TCD) of the material.

The inverse method is based on an optimization problem where unknown parameters are adjusted to fit measured acoustic data (ex.: sound absorption coefficient) [START_REF] Atalla | [END_REF]. This method is first applied to find the tortuosity and the two characteristic lengths by assuming porosity and static resistivity known from direct measurements. Second, the algorithm is applied to find simultaneously the five parameters assuming that none of the parameters are known. The acoustical measurements required for the indirect and inverse methods were obtained using an impedance tube following ASTM E 1050 and ISO 10534-2 standards.

RESULTS AND DISCUSSION

The dimensions of the samples are summarized in table 1. Direct measured porosity is 0.89±0.03. Using this value, the four other parameters obtained from indirect method are summarized in table 2. In general, the parameters values are in good agreement from one sample to another and the deviation from mean values are acceptable. The deviation of tortuosity and characteristics length may appear a little bit high, but since these parameters are difficult to measure with an accurate precision, these deviations are acceptable. Table 3 shows that the method yields stable results inside the accepted values of porosity, and finally, the static airflow resistivity given by this method fits well with those measured directly (table 4). Using the directly measured porosity and mean value of airflow resistivity, the threeparameter inverse method (3-PIM) yields results summarized in table 5. As the indirect method, the results fit quite well from one sample to another and this method yields stable results inside the accepted values of porosity (table 6) and airflow resistivity (table 7), but seems to depend on frequencies range (table 8). In term of behaviour, the five-parameter inverse method (5-PIM) yields similar results as the three-parameter method (see tables 9 and 10).

Table 11 presents a comparison of the results obtained from the different methods. We observe a significant difference between the porosity value giving by the direct and inverse methods. Moreover, the airflow resistivity obtained by inverse method seems to be over estimated. Finally, the results of the 3-PIM and IM compare well; however they diverge slightly from those giving by the 5-PIM. As 3-PIM and 5-PIM rely only on acoustical measurements, their accuracy exclusively depends on their quality and reproducibility. Usually because of experimental conditions (room temperature, sample fixing, etc), those measurements present a small deviations. The 5-PIM may be strongly vulnerable to those deviations and this may explain its variability. The two other methods (3-PIM and IM) are also affected by acoustical measurement deviations (this may explain their small variability), but less strongly than the 5-PIM since they use some known parameters. Furthermore, because both indirect and inverse methods rely on acoustical measurements, they are less accurate than the direct method. Finally, since both are based on the Johnson-Champoux-Allard model which supposes a motionless frame, they may yield wrong parameters when this condition is not satisfied. These results support the need of: 1) developing nonacoustical and direct methods (mainly for tortuosity and characteristic lengths), or 2) developing more accurate measurements in impedance tube for inverse and indirect characterization purposes.

ACKNOWLEDGEMENTS

N.S.E.R.C. supported this work.

The porosity value was 0.89± 0.03 measured with missing mass method [5] on the three samples at a same time. Uncertainty is predicted by method.

Sample Tortuosity


Cecilia Fuentealba
email: ceciliafuentealba@yahoo.com

Denise Choffel
email: denise.choffel@cran.uhp-nancy.fr

Patrick Charpentier
email: patrick.charpentier@cran.uhp-nancy.fr

Non destructive Control tool for wood traceability

Keywords: wood product, automatic identification, traceability, k-nearest neighbor

Introduction

The complete follow-up of products from its origin to its final use has been strongly developed lately, especially in food and automotive industries. The capacity to perform a complete followup of products in industries has been possible with the implementation of systems of automatic identification, which are able to establish a link among the product, the database of the product and of process. This follow-up process is currently named "traceability" and many technical solutions have been developed to carry it out, e.g. sticky labels and bar codes that allow a good identification of products and their traceability. However, according to the type of manufacturing process and products these techniques induce the utilization of high quantities of "consumables", thus increasing costs.

In the case of wood industries, the implementation of ordinary identification systems used in other industries presents implantation problems, mainly due to the extremely variable nature of the material and the particular features of the manufacturing process. Currently, identification systems as the code bars and marking techniques are used for the follow-up of wood products.

The whole of the techniques suitable for wood follow-up is listed by [Drykstra 2002]. It appears that it concerns only wood products from the forests to the input of the sawmills. Indeed, during the next processes (figure 1), effects due to: the loss of raw material in the cutting or planing steps, the diversity of products, the divergent character at the beginning and convergent at the end of the process, the usual loss of the FIFO order (First In First Out), and the high implementation cost, have led to slow down implementation of the fore-mentioned techniques.

However, if follow-up of products were assured, it would be possible :

• to control and differ finished products elaborated with raw material coming from sustainable managed forest. This situation was the first indication of the necessity for developing and implementing systems of products follow-up [START_REF] Stevens | Forest Products Certification: A survey of manufacturers[END_REF]].

• to increase the efficiency of the process and its technologies, [START_REF] Töyrylä | Realizing the potential of traceability-A case study research[END_REF]] highlights that it is possible to improve the logistics chain, the management, the supply and the optimization of raw material.

Figure 1. Divergent and convergent flow in the wood industries

In order to follow-up products, new solutions have been considered by the use of nondestructive control techniques. We implemented an identification system based of the biometrical technique. This denomination is used as it makes reference to personal identity and it takes into account the biological variability of the materials when making the identification. The similar point of view was developped by [Chiorescu 2003] utilizing of scanner information. Indeed wood is a heterogeneous and anisotropic material, showing a high variability in its structure.

Features such as knots, pitch pockets, and cross grain may be found in different degrees in wood [Kollman 1968]. Therefore, the extremely variable nature of wood promotes the existence of unique characteristics, just as the genetic human code. Charpentier and Choffel have shown that these characteristics can be used as a pattern to recognize [Charpentier 2003]. Moreover, some manufacturing processes would not support the addition of equipment on the product as proposed by the other identification systems.

Identification system

This paper present a biometrical technique based on the use of a micro-wave sensor which allows to acquire a intrinsic signature of the wood products. This sensor was first employed in the laboratory for the detection of the features of wood such as knots, cross grain [Charpentier 2003] and also the determination of the mechanical characteristics of timber [START_REF] Choffel | Interaction between wood and microwaves -Automatic grading application[END_REF]]. The results obtained in this utilization have established the bases of the current work. Indeed, microwaves interact with the material according to its dielectric properties [START_REF] Torgovnikov | Dielectric properties of wood and wood-based materials[END_REF]].

The propagation of this type of waves through the wood is mainly influenced by the moisture content and the presence of features (knots, cross grain, etc.). The moisture content has to be maintained constant to highlight the other factors. Indeed they are more variable from one board to another, consequently more interesting for the automatic identification.

The sensor is composed of an emitting part (10 GHz frequency, 100 mW power) and 16 aligned receivers. The product circulates between the emitter and receivers, then its signature is digitized to be processed on a computer as shown in figure 2. Two photoelectric cells allow detection of the product. Its length is known by the addition of an encoder. The lengthways resolution of the sampling has been fixed to 5 mm. The characteristics of the test sample are the following: 81 boards of Pinus sylvestris of 25 x 110 x 1500 mm, specific gravity of 0,5 and average moisture content of 9%. A factor affecting the signature is the distance between emitter-wood and receiver-wood. These distances can be modified, for example, in a warped board where there is no stability of the product during measurement, which results in additional features or perturbations with the consequent identification problems. In particular, a part of the data processing presented in the next section is dedicated to this problem.

Principle of identification

In the domain of pattern recognition, there is a large number of methods [START_REF] Dubuisson | Diagnostic and pattern recognition[END_REF]].

Similarities may be found between handwritten signatures and microwaves signatures. Then, the recognition of signatures consists in defining a numerical criterion that specifies the level of resemblance between two signatures inside a space [START_REF] Dubuisson | Diagnostic and pattern recognition[END_REF]], [START_REF] Parker | Simple distance between handwritten signatures[END_REF]]. This can be considered as a problem of k-nearest neighbor (knn) inside the defined space of characteristics.

In the present case, the algorithm based on the statistical approach using the knn method has been developed. Two types of representation spaces (reference spaces) were analyzed. The first space corresponds to the vector formed by statistical characteristics of the signal. Parameters such as the average, standard deviation, average curvature, maximum and minimum value, signal length are extracted on the signal and compose this vector. The second space is the vector formed by all the points composing the signal, here each point of the signal represents a particular characteristic. The signatures measured are made up of 310 points, therefore the dimension of the vector is 310. When a product is to be identified it will see its signal positioned and the nearest signal will be located (figure 3).

Figure 3. Reference space for identification

The distance between the unknown signal and the referenced one is computed as the Euclidean distance. It will set the criterion of decision and it will represent the degree of proximity. The equation of the Euclidean distance is given hereafter:

Euclidean distance ( ) ( ) 2 1 310 1 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ - - = ∑ = i i i i i xy y x M y x d (1)
Where:

x is the unknown signature of a product and y the known signature among those of reference.

x i and y i are the i-esime characteristic of the signature x and y and M is the weighing matrix taking into account the variability on the signatures.

Space of n dimensions

Unknown point to identify

Point of reference and assigned as identified k-nearest neighbor changes with regard to the reference space. As first stage, the identification problem was focalized into the storage operation. The classic manufacturing processes present FIFO queue of products, but in our case the intermediate stocks are not ensuring that any order of products will be respected. Additionally, it is not guaranteed to measure a product neither in the same face nor orientation. Figure 4 shows the four possibilities for the input of product on the machine and figure 5 presents the associated signatures. We note that the signatures coming from different sides in the same wooden piece are not completely similar, although measurement was made in the same area. To validate the performance of this algorithm, a criterion to evaluate the identification decision is defined. This is performed using the concept of confusion coefficient (CC). For this, an index of vicinity between the identified signal and the second next to her is calculated, i.e. the ratio of the two smallest values of distance. The CC fluctuates between [0,1]; one have that the nearer to value 1 the more ambiguous the decision will be and consequently with a higher risk.

Results and discussion

Treatment of signals

Treatment of signatures was carried out for increasing the algorithm performance in view of the difficulty found in the identification of signatures. To begin, a first low-pass filter on the signatures allowed to eliminate the inherent measurement of noise due to the conveyor belt motion.

The signatures acquired by the system shows fluctuations at the beginning and end due to changes in air-wood medium when the product enters and goes out of the system, this effect is named "edge effect" (Figure 6). Also, we observed the appearance of a curvature on the signatures in warped products, as the signals measured on each side of the same piece of wood were different. This situation is explained because the process of microwave measurement works by transmission-projection; the effect of turning the piece entails a difference of positioning to the plane of the conveyor belt system. The general appearance of the signature is then modified because the intensity of the received signal depends on distances produced between emitterproduct and product-receiver (Figure 7). This variability of the measurements produces a high probability of error in the decision.

The signal processing for eliminating the edge effect is a simple elimination of these zones.

The appearance of curvature on the signatures is eliminated by estimating the general curvature through a polynomial of degree 7, afterwards this general curve is subtracted from the signatures resulting in the straighten signature centered around zero (Figure 8). The polynomial degree has been heuristically selected from the general curvature observations of the signals.

In spite of removing these particular characteristics in the signatures for the identification process that were previously mentioned, we observed a least consistency in the lateral zones compared to central zones. For this reason we decided to ponder the values so as to put the central points forward. The weighing coefficients are introduced by mean of the diagonal matrix M in the equation (1) and (2). The variation of the weighing coefficients varies from 0.5 to 1 according to the position of the points of the signal. vector formed by the direct use of its measurements gave a better performance with an identification error of 1,5%. We focalized the next discussion on the second vector analyzed.

Although we obtained a high degree of identification, the confusion coefficient attained for each decision allows to see that an important quantity of good and bad decisions obtained were made with a high risk (Figure 9). We supposed that CC≥0,75 implies the ambiguous decision.

Conclusions

Through the results obtained we showed the high potential of biometrical approach for the identification of products by using the intrinsic characteristics of wood.

The algorithm developed is capable of a high degree of recognition in wood products. We know, for the time being, the different aspects to consider for increasing the actual performance of this algorithm. Certainly, the developed algorithm will depend closely on the transformation type that suffers the wood product, however, the algorithm developed in this first stage will be the base for future works. It is important to note the importance and the advantages that this type of identification system does have for current industries of wood, as it can be used during an important extension in the production line. The success of implementing this type of identification process will depend on finding the highest performance and reliability for the algorithm.

Figure 2 .

 2 Figure 2. The microwave system for wood identification

Figure 4 .Figure 5 .

 45 Figure 4. Four possibilities the input of product

Figure 6 .Figure 7 .Figure 8 . The corrected signatures 4 . 2 .

 67842 Figure 6. The signature obtain by means the microwaves system

  , P. and Choffel, D, 2003, "The feasibility of intrinsic signature identification for the traceability of pieces of wood", Forest Products Journal, 53( 9): 40-46. 2. Chiorescu S, Berg P, 2003, "The fingerprint approach: Using data generated by a 2-axis log scanner to accomplish traceability in the sawmill's", Forest Products Journal, 53(2): 78-86.