Use of the integrals in the graph theory I hope to know some good references about the use of integrals to study the graph theory:


*

*For example, it seems that
$$
\int^{\infty}_{-\infty} dx \exp(-x^2/2+\lambda x^3/3!)
$$
whose coefficients in the $V$ powers of $\lambda$, the coefficient of $\lambda^V$ counts the possible trivalent graphs of $V$ vertices.

*For example, it seems that
$$
\int dM \exp(\text{Tr}(-M^2/2+\lambda M^3/3!))
$$
where $M$ is a rank-$N$ Hermitian matrix.
The coefficient of $N^{2-2g}\lambda^V$ counts the possible trivalent graphs of $V$ vertices on a genus-$g$ Riemann surfaces.

  
*
  
*Are there some similar or more general statements of such integrals in the graph theory? Any References are welcome.
  
*Some intuitive way to obtain the above formulas? 

 A: In paper I was reading recently, the author said "it is well known that many enumerative problems in graph theory can be solved using Gaussian integrals," and cited the following book:
Sergei K. Lando and Alexander K. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia of Mathematical Sciences, vol. 141, Springer-Verlag, Berlin, 2004, With an appendix by Don B. Zagier, Low-Dimensional
Topology, II. MR 2036721. (Springer, or Springer Link).
Chapter 3 discusses matrix integral methods.  It gives some examples, for instance a matrix integral for enumerating $1$-vertex graphs that fill a surface of genus $g$, or enumerating planar $4$-regular graphs that are the generic image of a circle.  Perhaps the book describes the techniques well enough that you can figure out the construction of your given integrals.
A note to Proposition 3.2.10 mentions how you can disregard genus information by setting the matrix size to $1\times 1$.  This appears to be the transformation from your second integral to your first.  Given what I've picked up so far, perhaps it ought to be "where $M$ is an $n\times n$ Hermitian matrix" rather than "where $M$ is a rank-$n$ Hermitian matrix."

After looking at a paper by one of the book's authors,
A. Zvonkin, Matrix integrals and map enumeration: an accessible introduction, Mathematical and Computer
Modelling 26 (1997), no. 8-10, 281–304, Combinatorics and physics (Marseilles, 1995). MR 1492512
I think I can tell you what the terms of the integral represent.  The first part is that a Gaussian measure on the space of $n\times n$ Hermitian matrices is given by $d\mu(M)=\exp(\operatorname{tr}(-M^2/2))dM$, though in the paper equation (6) has some more normalization terms.  The second part is $$\exp(\operatorname{tr}(\lambda M^3/3!))=\sum_{k=0}^{\infty}\operatorname{tr}(\lambda M^3/3!)^k/k!=\sum_{k=0}^\infty(\lambda/3!)^{nk}\operatorname{tr}(M^3)^k/k!.$$
I do not understand what the $3!$ is doing in there, except perhaps to remove the dihedral symmetry of a $3$-valent vertex.  The $k!$ is likely to remove the vertex-renaming symmetry.  The paper says that $\int \operatorname{tr}(M^3)^k\,d\mu$ expanded in terms of $N$ has coefficients giving the number of $3$-valent graphs with $k$ vertices in a particular genus.  Integrating the infinite sum makes it so the coefficients of $N$ are power series in $\lambda$, the coefficients of which give the number of graphs of a particular number of vertices.
