skip to content
 

Seminars (CSMW03)

Videos and presentation materials from other INI events are also available.

Search seminar archive

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 2-connected 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 Tree-like 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 two-connected 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 independent-set 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 lattice-gas 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 independent-set 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 q-Bessel functions in two lattice models: the staircase polygons and the Solid-on-Solid 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 loop-erased 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 3-connected components: asymptotic counting and critical phenomena

Fix a family T of 3-connected labelled graphs with moderate growth, and let G be the class of graphs whose 3-connected 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 series-parallel graphs. There are two main regimes, that we call tree-like and map-like. In the tree-like case the largest 2-connected and 3-connected cores are almost surely of constant size, whereas in the map-like 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 Kotecky-Preiss 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 self-avoiding 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 Brydges-Kennedy 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 Glimm-Jaffe-Spencer, 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 state-of-the-art for these cluster expansions has reached a much simpler formulation thanks to the Brydges-Kennedy 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 root-connected orientations, a bijection between spanning forests and score vectors and bijections between spanning trees, root-connected 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 Mayer’s 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 hard-core 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 hard-sphere gas

The talk will present an improved estimate of the radius of analyticity of the pressure of the hard-sphere 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) non-linear sigma-models and spanning forests

In modern language, Kirchhoff Matrix-Tree 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 4-fermion 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 non-linear sigma-model with OSP(1|2) symmetry, which, in Parisi-Sourlas 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(1|2) 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(1|2m) 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 non-resistor 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) Grassmann-Berezin 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 Tutte-like identities with deletion/contraction allowed only for the non-distinguished (resistor) edges, with anticommutative multiplication, and with sign-correction factors. We get as a result $\binom{2p}{p}$ different weigted matrix-tree 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 full-rank 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 Grassmann-Berezin 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 ice-type partition function; the number of the directed cycle double covers as the matrix integral of an Ihara-Selberg-type 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 Ellis-Monaghan Multivariable Tutte and transition polynomials

Tutte polynomial of graph theory is equivalent to the q-state 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 4-regular graphs to unify polynomials given by vertex reconfigurations very similar to the skein relations of knot theory. These include the Martin polynomial (restricted to 4-regular 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 self-dual lattices that are 'natural'; underlying graphs of statistical mechanics.

CSMW03 10th April 2008
11:30 to 12:30
Alexander-Conway polynomial, milnor numbers, and the Pfaffian matrix-tree theorem

The well-know classical theorem of Kirchhoff expresses the spanning-tree polynomial of a graph as a determinant. Motivated by questions from knot theory, A. Vaintrob and I discovered in 2000 a new matrix-tree theorem which expresses the spanning-tree polynomial of a 3-uniform hypergraph as a Pfaffian. Other proofs of our theorem have been given by Abdesselam and Hirschman-Reiner, and generalisations have been obtained by Abdesselam and Caracciolo-Sokal-Sportiello.

In my talk, I plan to go back to the origins and explain how both the classical matrix-tree theorem and our Pfaffian-tree theorem appear naturally in knot theory when studying the Alexander-Conway 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 Rota-Baxter algebras which is shown to encode, among others, this process in the context of Connes-Kreimer's Hopf algebra of renormalization. Glen Baxter originally introduced the notion of commutative Rota-Baxter 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 Rota-Baxter 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 Connes-Kreimer's Hopf algebra of renormalization.

CSMW03 10th April 2008
16:15 to 17:00
A Tanasa Connes-Kreimer Hopf algabra for non-commutative field theory

The re-normalization process in quantum field theory on commutative space-time was expressed in terms of a Hopf algebra structure, the Connes-Kreimer algebra. Recently, some models of field theories on the non-commutative Moyal space were proven to be re-normalizable also. Despite the non-local nature of these models, we construct here the Hopf algebra structure adapted for the process of re-normalization of these non-commutative 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 Forest-root formulas in statistical physics

I will discuss forest-root 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 negative-activity hard-core 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. non-perturbative) field theory. It expresses the pressure of the $\phi^{4}$ model with cut-offs as a convergent sum of terms associated to trees whose vertices are non-perturbative 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 Jean-Bernard 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 2n-set 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^(\alpha-1) + C'' A^n n^(\alpha-2) + \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 D-finite 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 Kotecky-Preiss 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 Fernandez-Procacci cluster expansion condition corresponds to an enriched rooted tree bound. Conclusion: Combinatorics and mathematical physics tell the same story, perhaps in different languages.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons