Videos and presentation materials from other INI events are also available.
Event  When  Speaker  Title  Presentation Material 

CSMW03 
7th April 2008 10:00 to 11:11 
Introduction to species and combinatorial equations 1) Elementary introduction to species through examples : Collecting structures into species leading to the general definition of a combinatorial species. Exponential generating series of a species for labelled enumeration. Elementary combinatorial operations and equations between species. 2) More advanced theory : Cycle index and tilda series of a species for unlabelled enumeration. Equipotence versus combinatorial equality. Taking connected components. Combinatorial equations for weighted connected and 2connected graphs. Explicit examples. *Note : This lecture is preparatory to the reading of papers of Pierre Leroux and collaborators. These papers are available below. Other material, including a link to the book "Combinatorial Species and Treelike Structures", can be found on Pierre Leroux's web page Introduction to the Theory of Species of Structures, by François Bergeron, Gilbert Labelle, and Pierre Leroux. Papers and slides on Mayer graph weights:
Papers and slides on twoconnected graphs:


CSMW03 
7th April 2008 11:30 to 12:30 
A Sokal 
An introduction to the Mayer expansion I define the repulsive lattice gas on a vertex set X (which includes the independentset polynomial of a graph G as a special case) and briefly explain its relevance in statistical physics and in combinatorics. I then describe the Mayer expansion for the logarithm of the latticegas partition function, and analyze some of its combinatorial properties. Next, I describe two approaches to proving the convergence of the Mayer expansion in a complex polydisc: the traditional graphical approach and Dobrushin's inductive approach. Finally, I explain briefly the surprising connection between the independentset polynomial and the Lovasz local lemma in probabilistic combinatorics. Related Links


CSMW03 
7th April 2008 14:00 to 15:00 
Introduction to the theory of heaps of pieces with applications to statistical mechanics and quantum gravity The notion of "heaps of pieces" has been introduced by the author in 1985, as a "geometrization" of the algebraic notion of commutation monoids defined by Cartier and Foata. The theory has been developed by the Bordeaux group of combinatorics, with strong interaction with theoretical physics. We state three basic lemmas of the theory: an "inversion lemma" giving generating functions of heaps as the quotient of two alternating generating functions of "trivial" heaps, the "logarithmic lemma", and the "path lemma" saying that any path can be put in bijection with a heap. Many results and explicit formulae or identities in various papers scattered in the combinatorics and physics literature can be unified and viewed as consequence of these three basic lemmas, once the translation of the problem into heaps methodology has been made. Applications and interactions in statistical mechanics will be given with the now classical directed animal models and gas models with hard core interaction, such as Baxter's hard hexagons model; the appearance of some qBessel functions in two lattice models: the staircase polygons and the SolidonSolid model; and some 2D Lorentzian quantum gravity models introduced by Ambjorn, Loll, Di Francesco, Guitter and Kristjansen. Finally, I shall present a heap bijective proof of a new identity of Bauer about looperased walks, in relation with recent work of Brydges and Abdesselam about loop ensembles and Mayer expansion. 

CSMW03 
7th April 2008 15:30 to 16:30 
Cluster expansions (a historical overview) Several approaches to the proof of the cluster expansion theorem will be reviewed and compared. Applications to various expansions for lattice models will be discussed. 

CSMW03 
7th April 2008 16:30 to 17:15 
Graph classes with given 3connected components: asymptotic counting and critical phenomena Fix a family T of 3connected labelled graphs with moderate growth, and let G be the class of graphs whose 3connected components are the graphs in T. We present a general framework for analyzing such graph classes based on singularity analysis of generating functions. This generalizes previously studied cases such as planar graphs and seriesparallel graphs. There are two main regimes, that we call treelike and maplike. In the treelike case the largest 2connected and 3connected cores are almost surely of constant size, whereas in the maplike case they are of linear size. For some of the classes under study we show the presence of critical phenomena as the edge density in the class varies. 

CSMW03 
8th April 2008 09:00 to 10:00 
Improved bounds on cluster expansion of the abstract polymer model (via the Penrose identity) The classical approach to cluster expansions, based on tree graphs, is revisited and a new convergence condition that improves those by KoteckyPreiss and Dobrushin is established, as we show in some examples. The two ingredients of our approach are: (i) a careful consideration of the Penrose identity for truncated functions in the special case of hard core interactions, and (ii) the use of iterated transformations to generate expansions in terms of tree graphs. 

CSMW03 
8th April 2008 10:00 to 11:00 
D Brydges 
Counting with Gaussian integrals and cluster expansions This is a review, beginning with examples of how to express various combinatorial problems, including selfavoiding walks and loops in graphs, in terms of Gaussian integrals. The second half will be a review of techniques such as tree graph formulas for approximating the resulting integrals. 

CSMW03 
8th April 2008 11:30 to 12:30 
Field theoretic cluster expansions and the BrydgesKennedy forest sum formula In the first half of this talk, we will discuss cluster expansions in the context of quantum field theory, using the simple example of a weak phi^4 perturbation of a Gaussian measure with massive, i.e., rapidly decaying covariance, on a lattice. The first methods of this kind, introduced during the early seventies in the groundbreaking work of GlimmJaffeSpencer, were very involved and partly accounted for the reputation of inaccessibility of constructive field theory among mathematicians. Over the years many improvements were introduced, and the stateoftheart for these cluster expansions has reached a much simpler formulation thanks to the BrydgesKennedy forest sum formula and its variations. The second half of the talk will focus on the combinatorics of this identity. We will sketch several methods of proof for this algebraic identity, and doing so, we will point out its connection with Moebius inversion for partition lattices or subarrangements of the A_n hyperplane arrangement. 

CSMW03 
8th April 2008 14:00 to 15:00 
Determinant formulas for pairing matrices of arrangements of hyperplanes Several square matrices are associated with an arrangement of hyperplanes. These are matrices of suitable symmetric bilinear forms or matrices of hypergeometric integrals associated with an arrangement. These matrices are global characteristics of an arrangement. It turns out that the determinant of each of these matrices equals the product of suitable local characteristics of the arrangement, the characteristics associated with edges of the arrangement. 

CSMW03 
8th April 2008 15:30 to 16:15 
O Bernardi 
A bijection between subgraphs and orientations based on the combinatorics of the Tutte polynomial We present bijective correspondences between several structures on graphs. For any graph, we will describe a bijection between connected subgraphs and rootconnected orientations, a bijection between spanning forests and score vectors and bijections between spanning trees, rootconnected score vectors and recurrent sandpile configurations. These bijections are obtained as specializations of a general correspondence between spanning subgraphs and orientations of graphs. The definition and analysis of this correspondence rely on a recent characterisation of the Tutte polynomial and require to consider a \emph{combinatorial embedding} of the graph, that is, a choice of a cyclic order of the edges around each vertex. 

CSMW03 
8th April 2008 16:15 to 17:15 
Mayer polytopes and divided differences We start with a short review of Mayers theory of cluster integrals : first and second Mayer graph weights W(g) and w(c) and their application to virial expansion for non ideal gases. We then describe some basic general methods for the exact or approximate evaluation of w(c) for individual connected graphs c. Emphasis is put on the use of covering rooted trees and Fourier transforms. In the context of hardcore continuous gas in one dimension, the weight w(c) is a signed volume of a multidimensional polytope naturally associated with the graph c. Making use of the extra tool of divided differences we give a recursive algorithm for the exact computation of this volume. Explicit examples, tables and asymptotic formulas are also given. 

CSMW03 
9th April 2008 09:30 to 10:15 
R Fernandez 
Analyticity of the pressure of the hardsphere gas The talk will present an improved estimate of the radius of analyticity of the pressure of the hardsphere gas. It is obtained through a more careful estimation of the convergence of the corresponding cluster expansion, by exploiting Penrose identity for the coefficients of the expansion. 

CSMW03 
9th April 2008 10:15 to 11:00 
Integral equations for cluster expansion sums of polymer models with (soft) repulsion In this note, we derive integral equations for quantities a(P) defined as sums of cluster (Mayer) expansion terms taken over clusters "touching" a given polymer P. Using these quantities, many of the interesting properties of the model, like correlation decay can be evaluated. These relations have a slightly more complicated structure than usual exponential, "K.P." inequalities for quantities a(P) (developed successively by many authors: Cammarota, Seiler, Kotecky, Preiss, Dobrushin, Sokal, Scott, Fernandez, Ueltschi, and others) but they are equations. Their derivation employs quantities a(P,t) of auxiliary models with repulsions around P "softened" by an artificial parameter t, 0 < t < 1. Then at least some of the inequalities mentioned above can be interpreted as sufficient conditions (on the "smallness" of the complex polymer weights w(P)) for the convergence of the fixpoint method of solving such an integral equation. 

CSMW03 
9th April 2008 11:30 to 12:30 
V Rivasseau 
Introduction to non commutative field theory We recall some standard tools of ordinary field theory (Parametric representation, cluster expansions, renormalization) and the interesting related combinatoric aspects (tree matrix theorem, forest formulas, Hopf algebras...). We then outline the basic definitions of non commutative field theory and sketch how to generalize these tools to the non commutative case. This typically leads to even richer combinatoric problems and identities. 

CSMW03 
9th April 2008 14:00 to 15:00 
Potts model, O(n) nonlinear sigmamodels and spanning forests In modern language, Kirchhoff MatrixTree Theorem (of 1847) puts in relation the (multivariate) generating function for spanning trees on a graph to the partition function of the scalar fermionic free field. A trivial corollary concerns rooted spanning forests and the massive perturbation of the free field. We generalize these facts in many respects. In particular, we show that a fermionic theory with a 4fermion interaction gives the generating function for unrooted spanning forests, which are a limit of Potts Model for q > 0. Remarkably, this theory coincides with the perturbative theory originated from a nonlinear sigmamodel with OSP(12) symmetry, which, in ParisiSourlas correspondence, is expected to coincide with the analytic continuation of O(n) model to n > 1. The relation between spanning forests and the fermionic theory can be proven directly with combinatorial methods. However, the underlying OSP(12) symmetry leads to the definition of a subalgebra of Grassmann Algebra (the scalars under global rotations), with a set of surprising properties that quite simplify all the proofs. With some effort we can also generalize the whole derivation to a family of theories with OSP(12m) symmetry, with m a positive integer. 

CSMW03 
9th April 2008 15:30 to 16:15 
An extensor tree theorem and a Tutte identity for graphs with distinguished port edges Suppose Kirchhoff's laws for electricity are expressed by the rows of a matrix, each value of current flow and voltage (drop) along an edge is expressed by a separate variable, and those edges that model resistors each have a weight. Each nonresistor edge is distinguished as a port; each port's voltage and current relate the network to its environment. Each matrix row can be expressed as a linear combination of basis (co)vectors. The basis vectors function as rank 1 extensors which can also be thought of as fermionic (anticommuting) GrassmannBerezin variables. The (anticommutative) exterior product of the rows followed by the operation equivalent to eliminating the resistor current and voltage variables produces the extensor we will study. We prove that the resulting extensor obeys Tuttelike identities with deletion/contraction allowed only for the nondistinguished (resistor) edges, with anticommutative multiplication, and with signcorrection factors. We get as a result $\binom{2p}{p}$ different weigted matrixtree theorems, where $p$ is the number of port edges. One application is a combinatorial but not bijective proof of Rayleigh's inequality alternative to that given by Choe. Our construction and the Tutte identities extend to arbitrary fullrank matrices, but the coefficients in the enumeration fail to be $\pm 1$ without unimodularity. We will also sketch analogies between our exterior algebraic formulation and the GrassmannBerezin Calculus. 

CSMW03 
9th April 2008 16:15 to 17:00 
R Gurau 
Parametric representation of non commutative quantum field theory We present the generalization of the parametric representation of ordinary quantum field theory to the non commutative case. Its derivation reposes largely on the use of Grassmann numbers, variables adapted to the computation of determinants. The non commutative generalization of Symanzik polynomials are found to be sums of positive terms indexed by new topological objects, called "bytrees" which will be discussed in detail. 

CSMW03 
10th April 2008 09:30 to 10:15 
Enumeration of planar graphs by matrix integrals We apply matrix integrals to combinatorially defined functions (not to the functions of the traces) and express: The number of graphs embeddable in the plane as the matrix integral of an icetype partition function; the number of the directed cycle double covers as the matrix integral of an IharaSelbergtype function. The asymptotic analysis of the integrals remains a challenging open problem. (joint work with Mihyun Kang) 

CSMW03 
10th April 2008 10:15 to 11:00 
J EllisMonaghan 
Multivariable Tutte and transition polynomials Tutte polynomial of graph theory is equivalent to the qstate Potts model partition function of statistical mechanics if the temperature and q are viewed as independent variables. Recent work (by, among many others, Sokal, who has done much to popularize the approach) has used a multivariable extension of the Potts model partition function, physically corresponding to allowing the interaction energies on the edges to vary. The Tutte polynomial was fully generalized by Zaslavsky, and, from a different point of view, Bollobas and Riordan, but the generalization requires care with a set of relations arising from three special small graphs. In 1987, Jaeger introduced transition polynomials of 4regular graphs to unify polynomials given by vertex reconfigurations very similar to the skein relations of knot theory. These include the Martin polynomial (restricted to 4regular graphs), the Kauffman bracket, and, for planar graphs via their medial graphs, the Penrose and classical Tutte polynomials. This talk discusses a generalized transition polynomial (developed jointly with I. Sarmiento) that extends the transition polynomials of Jaeger to arbitrary Eulerian graphs, and introduces pair weightings that function analogously to the parameterized edges in the generalized Tutte polynomial. The generalized transition polynomial and the generalized Tutte polynomial (and hence Potts model partition function) are related for planar graphs in much the same way as are Jaeger's transition polynomial and the classic Tutte polynomial. Moreover, the generalized transition polynomials are Hopf algebra maps. Thus, the comultiplication and antipode give recursive identities for generalized transition polynomials. A number of combinatorial identities then arise from these and the relations among these polynomials. Because of the medial graph construction relating these polynomials, the identities are relevant to the selfdual lattices that are 'natural'; underlying graphs of statistical mechanics. 

CSMW03 
10th April 2008 11:30 to 12:30 
AlexanderConway polynomial, milnor numbers, and the Pfaffian matrixtree theorem The wellknow classical theorem of Kirchhoff expresses the spanningtree polynomial of a graph as a determinant. Motivated by questions from knot theory, A. Vaintrob and I discovered in 2000 a new matrixtree theorem which expresses the spanningtree polynomial of a 3uniform hypergraph as a Pfaffian. Other proofs of our theorem have been given by Abdesselam and HirschmanReiner, and generalisations have been obtained by Abdesselam and CaraccioloSokalSportiello. In my talk, I plan to go back to the origins and explain how both the classical matrixtree theorem and our Pfaffiantree theorem appear naturally in knot theory when studying the AlexanderConway polynomial of a link from the point of view of Feynman diagrams. This approach leads to generalizations of our formula involving higher order Milnor numbers. The talk will however be elementary and no previous knowledge of knot theory will be assumed. 

CSMW03 
10th April 2008 15:30 to 16:15 
Solving Bogoliubov's recursion in renormalisation using a simple algebraic identity The Bogoliubov recursion is a particular procedure appearing in the process of renormalization in perturbative quantum field theory. In this talk we present a theory of functional identities for noncommutative RotaBaxter algebras which is shown to encode, among others, this process in the context of ConnesKreimer's Hopf algebra of renormalization. Glen Baxter originally introduced the notion of commutative RotaBaxter algebra to give a more conceptual proof of Spitzer's identity known from fluctuation theory. In the commutative case these identities can be understood as deriving from the theory of symmetric functions. We show that an analogous property holds for noncommutative RotaBaxter algebras. That is, we show that functional identities in the noncommutative setting can be derived from the theory of noncommutative symmetric functions. Lie idempotents, and particularly the Dynkin idempotent play a crucial role in the process. As an application we present a closed formula for Bogoliubov's recursion in the context of ConnesKreimer's Hopf algebra of renormalization. 

CSMW03 
10th April 2008 16:15 to 17:00 
A Tanasa 
ConnesKreimer Hopf algabra for noncommutative field theory The renormalization process in quantum field theory on commutative spacetime was expressed in terms of a Hopf algebra structure, the ConnesKreimer algebra. Recently, some models of field theories on the noncommutative Moyal space were proven to be renormalizable also. Despite the nonlocal nature of these models, we construct here the Hopf algebra structure adapted for the process of renormalization of these noncommutative field theory. 

CSMW03 
10th April 2008 17:00 to 17:45 
Combinatorial identities and the correlation function gaps in dimer packings The correlation function of gaps in dimer packings on a lattice was introduced in the literature by Fisher and Stephenson in 1963. In this talk we explain how for certain geometries of the gap distributions the correlation function can be found exactly, using combinatorial identities. This leads to refinements of the classical problem of determining the asymptotics of the correlation function as the gaps recede away from each other so that the gap distribution maintains its geometry. 

CSMW03 
11th April 2008 09:30 to 10:15 
J Imbrie 
Forestroot formulas in statistical physics I will discuss forestroot formulas as interpolation identities in R^n and in C^n. These identities have applications in cluster expansions and Mayer expansions. They can be used to solve the combinatorics of branched polymers by relating them to negativeactivity hardcore gases in lower dimensions. 

CSMW03 
11th April 2008 10:15 to 11:00 
J Magnen 
Constructive field theory without tears We present a preliminary result of a programme aiming at simplifying the basic arguments of constructive (i.e. nonperturbative) field theory. It expresses the pressure of the $\phi^{4}$ model with cutoffs as a convergent sum of terms associated to trees whose vertices are nonperturbative loops. We give also the expression for a correlation function. 

CSMW03 
11th April 2008 11:30 to 12:30 
Identities for fully packed loop configurations and semistandard tableaux I shall present joint work with Fabrizio Caselli, Bodo Lass and Philippe Nadeau, and work of Johan Thapper in direction of conjectures of JeanBernard Zuber on the enumeration of fully packed loop configurations with a fixed associated matching pattern. 

CSMW03 
11th April 2008 14:15 to 15:00 
Counting partially directed walks in a symmetric wedge The enumeration of lattice paths in wedges poses unique mathematical challenges. These models are not translationally invariant, and the absence of this symmetry complicates both the derivation of a functional recurrence for the generating function, and its solution. We consider a model of partially directed walks from the origin in the square lattice confined to a symmetric wedge defined by Y = ±X. We derive a functional equation for the generating function of the model, and obtain an explicit solution using a version of the Kernel method. This solution shows that there is a direct connection with matchings of an 2nset counted with respect to the number of crossings, and a bijective proof has since been obtained. Related Links


CSMW03 
11th April 2008 15:30 to 16:15 
Enumeration and asymptotics of random walks and maps In this talk, I want to give a brief survey of what I did in analytic combinatorics (=using generating functions to enumerate combinatorial structures, and then using complex analysis to get the asymptotics). This survey will be based on 3 kinds of equations which are often met in combinatorics, the way we solve them, and what kind of generic methods we use to get the full asymptotics/limit laws. By full asymptotics, I mean an expansion like $$f_n \sim C A^n n^\alpha + C' A^n n^(\alpha1) + C'' A^n n^(\alpha2) + \dots$$ where $A$ is the growing rate and $\alpha$ the "critical exponent" of the corresponding combinatorial structure. Namely, I will show that three combinatorial structures are "exactly solvable" :  a directed random walk model (using the kernel method and singularity analysis of algebraic functions),  random walks on the honeycomb Lattice (using an Ansatz and Frobenius method for Dfinite functions),  question of connectivity in planar maps (using Lagrange inversion and coalescing saddle points, leading to a ubiquitous distribution involving the Airy function). This talk is based on an old work with Philippe Flajolet, Michèle Soria, and Gilles Schaeffer, and on work in progress with Bernhard Gittenberger. 

CSMW03 
11th April 2008 16:15 to 17:00 
A rosetta stone: combinatorics, physics, probability The purpose of this talk is to relate enumerative combinatorics, statistical physics, and probability. Specifically, it will explain how the theory of species of structures is exactly what is needed for the equilibrium statistical mechanics of particles. Thus, for example, the condition that the rooted tree equation has a finite fixed point is precisely equivalent to the KoteckyPreiss condition used in the theory of cluster expansions. Furthermore, there is a fixed point equation for rooted connected graphs from which the rooted tree bound follows immediately. The talk will conclude with an indication about how the recent FernandezProcacci cluster expansion condition corresponds to an enriched rooted tree bound. Conclusion: Combinatorics and mathematical physics tell the same story, perhaps in different languages. 