We continue with our study of random walks on finite graphs via linear algebra. Let 
The linear algebraic setup is as follows. Let 
where 
so that understanding the 
We adopt the same assumptions as in Lecture 4: 
We may thus invoke the spectral theorem to assert that
where
are the distinct eigenvalues of the selfadjoint operator 
so that for the 
So far everything we have said is valid for an arbitrary operator in 
Theorem 1: The largest eigenvalue of
Proof: Let 
We claim that 
Indeed, we have
and the terminal double sum is exactly 
It follows that any eigenvalue of
Now we exhibit an eigenvector of
where
is the sum of the degrees of all vertices of 
— Q.E.D.
The eigenvector 
corresponds to uniform probability measure on 
It is important to note that Theorem 1 does not preclude the possibility that the smallest eigenvalue of the transition operator 
Corollary 1: If
where 
Proof: Let 
by the triangle inequality. But since 
— Q.E.D.
At this point we can finally say something about the probability 
exists. Note that the role of bipartiteness here is quite clear from a combinatorial perspective: if
Continuing on under the assumption that 
which encodes the limit distribution of simple random walk on
Theorem 2: For any 
Proof: We have
— Q.E.D.
Theorem (Markov limit theorem): For
Proof: The statement follows if we can show that 
The proof that the top eigenspace is indeed one-dimensional uses a bit of a deus ex machina, namely the Perron-Frobenius theorem. Look up this theorem, and complete the proof!
— Q.E.D.
arranged in a single row on a table. At each instant of discrete time, choose two cards independently at random and swap them. How long until you can be sure that the order of the cards is uniformly random?
— just write down the labels of the cards one at a time, from left to right, and you obtain a permutation written of 
of 
is encoded by the permutation 
what are the possible states that our system can be in at time 
? An obvious but in fact crucially important fact is that the answer to this question is not just combinatorial, but also algebraic: our configuration space 
. This means that the evolution equation we seek can be represented as multiplication in this group: given that the configuration of cards at time 
the possible states at time 
denotes the 
This is a good time to fix our notational conventions. Permutations in 
and multiplication of permutations means composition of functions. The concatenation of two permutations 
means the following:
is that we are more interested in doing computations “upstairs” where permutations are elements in a group, as opposed to “downstairs” where they are functions acting on points, and it is nice to multiply strings of elements from left to right. 
of all transpositions 
generates 
That is, for any permutation 
, there exists a nonnegative integer 
and transpositions 
such that 
by 
meaning a way to measure the “size” of a permutation, it is very natural to define a corresponding notion of distance between two permutations by 
satisfies the 
and this is afforded by the corresponding 
The vertex set of 
is 
are adjacent if and only if there exists 
such that 
Below is a picture of the Cayley graph of 
as generated by 
-regular, because 
Second, it is a graded graph, meaning that its vertex set decomposes as a disjoint union of independent sets,
is the set of permutations whose 
cycles. Third, from the geometric perspective, the 
th level 
and at each instant of discrete time the particle jumps to a neighboring vertex, with equal probability of selecting any neighbor. We would like to understand how many jumps must be made before the probability to observe the particle at any vertex of the graph is the same as at any other vertex. This is what it means for a deck of cards to be shuffled: every configuration is equally likely, so that a person choosing a card from the deck cannot do anything more than guess what this card is going to be. Now, there is an immediate problem: this will never happen. The reason is annoying but unavoidable: every permutation is either even or odd, meaning that for any 
and at odd times in its complement. But actually, this foible reminds us that we are trying to solve a real world problem in which two cards are selected independently and then swapped — it is possible that the two cards selected are actually the same, and no swap occurs.
transpositions.
You may however not realize that this theory is directly applicable to natural and compelling real world problems, some of which are sufficiently rich and interesting that they can be adopted as a posteriori motivations for the development of the subject.
the numbers 
and 
are the number of edges and vertices of 
respectively, and the “amplitude” 
is the product of the coefficients 
from the perturbation of the Gaussian density on the integral side according to the vertex degree sequence of 
is the 
and 
This means that we can organize the asymptotic expansion of the integral as a generating function for maps sorted by their circuit rank:
then the error is 
because of the Laplace method, which shows that the integral in question really is concentrated in a neighborhood of the minimizer of the integrand. If you take logs, meaning that you are only interested in the order of magnitude of the integral you started with, then the loop expansion only involves connected graphs, which reduces the complexity quite a bit. An unfortunate aspect of the loop expansion is that it misses out on the fact that the relevant diagrams are not just combinatorial objects — graphs — but actually graphs embedded in surfaces. This expansion does not see the surface, meaning that it does not encode its topology.
to its noncommutative counterpart 
the Euclidean space of 
Hermitian matrices. Formally, the expansion from the scalar case is modified to 
is the number of faces of the topological map 
Using the Euler formula,
expansion of the above matrix integral into not a loop expansion, but a genus expansion,
error. The basic problem is that the Laplace principle doesn’t work: the principle relies on the fact that the contribution to an integral over 
is dominated by a small neighborhood of the maximum of 
but if we swap out 
-dimensional Euclidean space has volume 
so that contributions to the integral from Lebesgue measure are on the same scale as contributions from the integrand itself. 
consisting of Hermitian matrices with a given list of eigenvalues,
is a constant depending only on 
Now, each such isospectral set is, by the Spectral Theorem, an orbit of the unitary group 
acting on 
are symplectic manifolds, but we don’t need to pay attention to this here. The point that is relevant for us is the Weyl integration formula, which is just the change of variables formula resulting from Weyl’s volume computation: if 
is a function on 
then 
i.e. the convex set 
is, by abuse of notation, the value of the original function 
on any Hermitian matrix with eigenvalues 
In particular, a matrix integral of the Laplace form 
-dimensional set 
which is a massive reduction in degrees of freedom, and in particular contributions from the Lebesgue measure are now order 
Second, the integrand is of order 
so it seems like the Laplace principle may yet be correct in this context: the main contributions to the integrand come from a small neighborhood of the minimizer of the function 
which was 
last time we met it, but now can be anything. As 
the distribution of these charges will crystallize around the configuration which minimizes the action 
which in particular means that the empirical distribution 
of these 
at each particle — will converge as 
on 
More precisely, in the language of calculus of variations, we have 
the equilibrium measure always exists and is unique. This is the Laplace principle for matrix integrals. Although it is technically very involved, a fine analysis of the convergence to equilibrium measure shows that under reasonable hypotheses the formal genus expansion above is indeed correct, analytically, as an asymptotic expansion. This means that the Feynman diagrams for matrix integrals really are maps on surfaces. It is interesting that this connection is in fact more typically used to say something about maps, not about integrals: there are independent methods for computing the coefficients in the asymptotic expansion of Hermitian matrix integrals based on orthogonal polynomials, and once these coefficients are found in some independent fashion one has also determined the generating function for maps of a given genus. For example, taking the potential 
and calculating the corresponding equilibrium measure, one can obtain an explicit formula for the number of ways to glue a sphere from a given number of squares. A good entry point into all of this is 
Feynman diagram expansion 
to bring this about?
terms by somehow choosing the right action 
which is a function of 
we would integrate over 
for 
It turns out that there is a Laplace method and a corresponding Feynman diagram expansion for the multidimensional integral
i.e. a complex vector space equipped with a scalar product 
, which is required to be complete with respect to the norm induced by the scalar product. We can consider the operator algebra 
as a noncommutative generalization of 
: it actually is 
and in any dimension we can add and multiply operators in a manner analogous to the addition and multiplication of numbers. What subsets of 
and the unit circle 
? Answer: the Hermitian operators
Thus, a noncommutative analogue of the Laplace method would mean a statement on the 
Similarly, a noncommutative analogue of the imaginary version of the Laplace method, which is called the method of 
rather than the line 
is infinite-dimensional, because of the lack of Lebesgue (or Haar) measure in infinite dimensions. So in order to rigorously study the above integrals, we have to restrict to the case that 
is of finite dimension 
in which case we can identify 
with the set 
of 
Hermitian matrices, and 
with the set of 
which is isomorphic to the Euclidean space 
when given the scalar product 
where 
is the usual matrix trace, and the latter is a compact real Lie group of dimension 
So, we are led to study the 
we have
is an explicit number depending only on 
and 
is the number of ways in which the edges of a 
On the right hand side, if we set 
we obtain 
, the (finite) sum is simply counting ways to glue the edges of a 
on the left hand side of Theorem 1 does *not* produce
This simple fact causes massive problems on the analytic side, effectively invalidating the fundamental notion underlying Laplace’s method, which is that the main contribution to an integral containing a large parameter comes from a small neighborhood of a single value of the integrand. We will discuss both the combinatorics and the analysis of this “quantum Laplace method” next week.
is a function of the real variable 
which is smooth in a neighborhood of 
then I write 
So it does not make sense to write 
and trade the formal variable 
you get a good approximation to the real number 
in terms of the formal power series 
What we currently know is that 
the number of fixed point free involutions in 
and 
the conjugacy class in 
and 
So, in completely algebraic language, one could say that we are studying the “Feynman transform”![\mathcal{F} \colon x^3\mathbb{R}[p_1,p_2,p_3,\dots][[x]] \to \mathbb{R}[p_1,p_2,p_3,\dots][[\hbar]]](https://s0.wp.com/latex.php?latex=%5Cmathcal%7BF%7D+%5Ccolon+x%5E3%5Cmathbb%7BR%7D%5Bp_1%2Cp_2%2Cp_3%2C%5Cdots%5D%5B%5Bx%5D%5D+%5Cto+%5Cmathbb%7BR%7D%5Bp_1%2Cp_2%2Cp_3%2C%5Cdots%5D%5B%5B%5Chbar%5D%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
in the algebra of formal power series in 
with coefficients being polynomials in the 
and the codomain is formal power series in 
with coefficients in the same polynomial ring. The problem then is to simplify the output of the Feynman map as a power series in 
i.e. to determine the coefficient of 
for each 
as the cardinality of 
where again 
and 
is the set of fixed point free involutions in 
is the Young diagram with 
rows of length 
Every pair 
is a combinatorial map. Associated to this map are two topological maps, which are dual to one another. To construct these topological maps, we use the following construction. First, for each cycle of 
we draw a polygon whose number of sides is equal to the length of 
and whose edges are labeled counterclockwise in the cyclic order prescribed by 
At the same time, we place into this polygon the corresponding dual object, namely a vertex in the interior of the polygon together with line segments, called “half edges” or “darts,” which emanate from the vertex, one for each edge of the polygon and labeled in the same way. Note that we need only consider the case where 
otherwise, and moreover where all rows of 
have length at least 
meaning that all polygons in this construction have at least three sides, or dually that all stars have degree at least 
Now we glue the sides of the polygons together according to the pairing permutation 
and at the same time pair half edges of stars in the same manner, i.e. using 
This produces a pair of dual topological maps 
on a compact oriented surface 
as the topological map obtained by glueing polygons. The figure below illustrates this construction for the combinatorial map
are the number of vertices and edges in 
depends only on the underlying graph, not actually on its embedding, so that this is a purely combinatorial parameter. Indeed, it is closely related to the so-called 
the number of connected components. This is pretty obvious if you think about it: consider the extremal case where we have one connected component consisting of a tree. In this case the difference 
is obviously equal to zero, and if we start adding edges the circuit rank goes up by one every time we add an edge, and moreover the construction is additive in the number of components (graph theory people – did I get that right?). 
and conjugate it by an arbitrary permutation 
then we get another combinatorial map 
which obviously yields the same topological map when the construction described above is performed, since we have simply relabeled everything by conjugating. Thus we expect that the correspondence between combinatorial and topological maps should be 
-to-one, which would be excellent news, since then the factor
of the symmetric group 
limit comes from graphs which have minimum vertex degree 
![[a,b] \subseteq \mathbb{R}](https://s0.wp.com/latex.php?latex=%5Ba%2Cb%5D+%5Csubseteq+%5Cmathbb%7BR%7D&bg=FFFFFF&fg=000&s=0&c=20201002)
which may be finite or infinite, and let ![S \colon [a,b] \to \mathbb{R}](https://s0.wp.com/latex.php?latex=S+%5Ccolon+%5Ba%2Cb%5D+%5Cto+%5Cmathbb%7BR%7D&bg=FFFFFF&fg=000&s=0&c=20201002)
be a smooth function which attains a global minimum at a unique interior point 
and which is such that the integral 
with 
. Taylor’s theorem with remainder tells us that for any nonnegative integer 
depends on 
the Laplace principle gives us the 
via the Euler integral.
when 
such that 
Writing 
and the product being over the blocks 
of each partition 
An alternative form of the Exponential Formula, which is more useful for our current purpose, arises when we instead write 
In terms of the scaled derivatives 
the formula for 
becomes
can be cyclically ordered in 
ways, we can rewrite the above as
and the product is over the cycles 
of each permutation 
but only their sizes, so that any two permutations of the same cycle type (i.e. any two permutations which are conjugates of one another) give the same contribution to the sum. That is to say, we may rewrite the above as 
is the conjugacy class of permutations of cycle type 
. To simplify the computation, we will make several assumptions on the Laplace side, none of which are essential — these can all be eliminated without too much difficulty and the end result is more or less the same. First, we assume the integration is over the whole real line. Second, we assume that the critical point 
, and that 
Finally, let us assume that the positive number 
is equal to one. 
We factor the integrand as 
. We get the Maclaurin series of 
by integrating this term-by-term against the Gaussian density:
we now want to arrange the sum 
At this point, it is not even clear that the series involves only nonnegative integer powers of 
which seems like it could be negative, but in fact since 
vanishes if 
has more than 
rows. Combining these conditions, we see that the first non-zero exponent of 
, and the only 
which contributes to the sum is 
the diagram with two rows each of length 
Since all rows of 
is 
is 
ways to choose the elements in cycles and 
ways to cyclically arrange each, and this overcounts by a factor of 
which is ten times smaller than 
).
is equal to the number of pairs 
such that 
is a fixed point free involution and 
is a permutation of cycle type 
with 
arbitrary but fixed. Recall that 
which have no increasing subsequence of length 
is the 
rectangular Young diagram. This would be excellent, since the asymptotics of the dimension of a very long rectangle of fixed height are easy to deduce from Frobenius’s formula for 
together with Stirling’s approximation of 
we have 
using our “gluing” intuition. To do this, let us define the notion of the complement 
of a diagram 
This is exactly what you think it is: if 
, then 
— draw yourself a picture. The basis of our gluing trick was that in the case 
every diagram is self complementary: for 
we have
but for any 
is in bijection with the set of pairs 
of SYT in which the shape of 
is a diagram 
and the shape of 
is the complementary diagram 
and subtracting 
from each entry. In formulas, this is
and 
is contained in 
is self-complementary or not,
where the error term is 
reflects the two sources of error in the approximation 
In particular, we have that 
corresponding to Knuth’s theorem, but 
for 
Conjecture 1 says that 
i.e. the rectangle 
So we are hopeful that diagrams in a neighborhood of this rectangle are essentially contributions from a neighborhood of the maximum of 
just like in Laplace’s method.
and 
is a vector such that
is a 
-dimensional convex subset of 
at possibly non-integral numbers, so we are in effect taking Frobenius’s formula as a way to extend the domain of 
just like Euler’s integral extends the domain of 
is capturing the behavior of the dimension function in a neighborhood of the suspected maximizer, which to compare with Laplace’s method is like looking at the Taylor expansion of the 
behaves as 
as we have discussed. We now have to think about the 
, for which we have 
for factorials, which follows from Euler’s integral. Thus 
together with the Maclaurin series of 
to write
. Notice that 
is emerging as the right scaling here — do you see why? Assembling all these calculations into one master estimate, we obtain
, we have 
,
