skip to content
 

Seminars (CSM)

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

Search seminar archive

Event When Speaker Title Presentation Material
CSMW06 14th January 2008
10:00 to 11:00
Graphs and matroids I
CSMW06 14th January 2008
11:30 to 12:30
Combinatorial enumeration I
CSMW06 14th January 2008
14:30 to 15:30
Statistical mechanics I
CSMW06 14th January 2008
16:00 to 17:00
Phase transitions and cluster expansions I
CSMW06 15th January 2008
10:00 to 11:00
Graphs and matroids II
CSMW06 15th January 2008
11:30 to 12:30
Combinatorial enumeration II
CSMW06 15th January 2008
14:30 to 15:30
Statistical mechanics II
CSMW06 15th January 2008
16:00 to 17:00
Phase transitions and cluster expansions II
CSMW06 16th January 2008
10:00 to 11:00
J Jacobsen Conformal field theory I
CSMW06 16th January 2008
11:30 to 12:30
M Jerrum Algorithms and complexity I
CSMW06 16th January 2008
14:30 to 15:30
S Janson Probablistic methods I
CSMW06 16th January 2008
16:00 to 17:00
M Jerrum Algorithms and complexity II
CSMW06 17th January 2008
10:00 to 11:00
G Whittle Graphs and matroids III
CSMW06 17th January 2008
11:30 to 12:30
J Jacobsen Conformal field theory II
CSMW06 17th January 2008
14:30 to 15:30
Statistical mechanics III
CSMW06 17th January 2008
16:00 to 17:00
Phase transitions and cluster expansions III
CSMW06 18th January 2008
10:00 to 11:00
G Whittle Graphs and matroids IV
CSMW06 18th January 2008
11:30 to 12:30
J Jacobsen Conformal field theory III
CSMW06 18th January 2008
14:30 to 15:30
S Janson Probablistic methods II
CSMW01 21st January 2008
10:00 to 11:00
Complex zeros of the chromatic and Tutte polynomials

In this introductory talk, I begin by showing how the chromatic and flow polynomials are special cases of the multivariate Tutte polynomial, and I sketch why it is often advantageous to "think multivariate", even when one is ultimately interested in a univariate specialization. I then explain briefly why the complex zeros of these polynomials are of interest to statistical physicists in connection with the Lee-Yang picture of phase transitions. Finally, I summarize what is known -- and above all, what is _not_ known -- about the complex zeros of these polynomials.

A general reference for this talk is:

arXiv:math/0503607 [math.CO] Alan D. Sokal The multivariate Tutte polynomial (alias Potts model) for graphs and matroids

More details on various aspects can be found in:

arXiv:math/0301199 [math.CO] Gordon Royle, Alan D. Sokal The Brown-Colbourn conjecture on zeros of reliability polynomials is false

arXiv:math/0202034 [math.CO] Young-Bin Choe, James G. Oxley, Alan D. Sokal, David G. Wagner Homogeneous multivariate polynomials with the half-plane property

arXiv:cond-mat/0012369 [cond-mat.stat-mech] Alan D. Sokal Chromatic roots are dense in the whole complex plane

arXiv:cond-mat/9904146 [cond-mat.stat-mech] Alan D. Sokal Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions

CSMW01 21st January 2008
11:30 to 12:30
Real zeros of chromatic and flow polynomials

I will survey proof techniques, results, and open problems concerning the real zeros of chromatic polynomials and flow polynomials of graphs. In particular I will present a multivariate proof, due to Alan Sokal and myself, of the result that chromatic polynomials have no roots in the interval (1,32/27], which is much simpler than my original proof.

A general, but dated, reference for this talk is:

Bill Jackson, Zeros of Chromatic and Flow Polynomials of Graphs, arXiv:math/0205047v2 [math.CO]

CSMW01 21st January 2008
14:00 to 15:00
Chromatic polynomials and a second Hamiltonian cycle

The chromatic polynomial was introduced by Birkhoff in 1912 in order to study the 4-Color Problem. Although the chromatic polynomial has not been very successful for solving coloring problems, it has served as inspiration for other problems in graph theory. In this talk, we describe some graph problems and resuls related to the roots of a chromatic polynomial, in particular the search for a second Hamiltonian cycle. Also a possible list-chromatic polynomial will be discussed.

CSMW01 21st January 2008
15:30 to 16:00
Chromatic roots and fibonacci numbers

We prove that all natural power of golden ratio, cannot be a root of any chromatic polynomial.

We also consider generalized Fibonacci sequences and prove that all 2n-anacci constants and all natural powers of them cannot be root of any chromatic polynomial. Finally, we introduce new numbers related to n-annaci numbers and ask a question similar to Beraha question.

CSMW01 21st January 2008
16:00 to 16:30
K Morgan Chromatic factorisation of graphs

We consider factorisation of the chromatic polynomial as a first step in an algebraic study of the roots of this polynomial. The chromatic polynomial of a graph is said to have a chromatic factorisation if P(G,?)= P(H1,?)P(H2,?)/P(Kr ,?) for some graphs H1 and H2 and clique Kr . It is known that the chromatic polynomial of any cliqueseparable graph, that is, a graph containing a separating rclique, has a chromatic factorisation. We show that there exist other chromatic polynomials that have chromatic factorisations but are not the chromatic polynomial of any cliqueseparable graph and identify all such chromatic polynomials of degree at most 10. We introduce the notion of a certificate of factorisation, which provides an explanation for such a factorisations, and find certificates for all cases of degree ? 9. These certificates are much shorter than the upper bound of O(n 22n/2). Furthermore, we construct an infinite family of noncliqueseparable graphs that have chromatic factorisations and give certificates of factorisation for graphs belonging to this family.

CSMW01 22nd January 2008
10:00 to 11:00
Constructive resolution of two conjectures on real chromatic roots

In this talk I will discuss the recent resolution of two conjectures on the real roots of the chromatic polynomial of a graph, both of which were resolved by the construction of suitable families of graphs.

The first of these is Bill Jackson’s conjecture that 3connected nonbipartite graphs do not have chromatic roots in the interval (1,2), which turns out to be false. The counterexamples to this conjecture all have an intriguing connectivity property that seems unavoidable, lending support to a recent conjecture of Dong & Koh concerning graphs with no chromatic roots in (1,2).

The second conjecture that I discuss is Sami Beraha’s conjecture that there are planar graphs with real chromatic roots arbitrarily close to the point x = 4. For many years, the largest known real planar chromatic root was 3.8267 ...from a graph found by Douglas Woodall that appeared to have no obvious structure. However it turns out that viewed in the right way, this graph is the first member of an infinite sequence of graphs with real chromatic roots converging to 4.

The most wanted conjecture in the study of real chromatic roots is Birkhoff & Lewis’s conjecture that [4,5) is a rootfree interval for planar graphs, but unfortunately the resolution of Beraha’s conjecture appears to give no traction whatsoever on this conjecture.

CSMW01 22nd January 2008
11:30 to 12:00
On the zeros of independence and open set polynomials

While the zeros of chromatic and flow polynomials have attracted much attention in the research literature, there are some other lesser known polynomials on discrete structures whose zeros are also worthy of investigation. Independence polynomials arise as generating functions of the number of independent sets of each cardinality in a graph. Open set polynomials enumerate open sets in a finite topology. We survey what is known about the nature and location of the zeros, with results ranging from bounds on the moduli to density and realness of the zeros, and even including a fractal or two thrown in for good measure.

CSMW01 22nd January 2008
12:00 to 12:30
Bounds for the numner of matchings in regular graphs

In this talk I will first present a group of conjectures on the number of k-edge matchings in a regular graph on n vertices. Next I will present the partial results obtained so far. In order to get lower bounds for the number of matchings for all densities k/n we make use of the fact that the matching polynomial of a graph has real zeros.

CSMW01 22nd January 2008
14:00 to 15:00
FM Dong On graphs whose chromatic polynomials have no zeros in (1,2)

The study of zero distribution of chromatic polynomials has attracted the attention of researchers working in both Mathematics and Physics. In this talk, I shall focus on the study of graphs which have no chromatic zeros in (1, 2). One of the motivations of this study is to find some useful methods to attack the famous conjecture that every plane graph has no chromatic zeros in (4, 5).

Due to Jackson’s and Thomassen’s results, it is now confirmed that there are only three maximal intervals (-?, 0), (0, 1) and (1, 32/27], in which all chromatic polynomials are zero-free. Jackson conjectured in 1993 that every 3-connected non-bipartite graph has no chromatic zeros in (1, 2). It was recently disproved by Royle’s discovery of some counter-examples. However, Jackson’s conjecture triggered the study of graphs which have no chromatic zeros in (1, 2).

Let F be the family of K2 and 2-connected graphs which have no chromatic zeros in (1, 2). We can show that this family is ‘closed’ in some senses under certain operations. Applying this result, we are able to find some subfamilies of graphs which have no chromatic zeros in (1, 2).

A connected graph G is said to be ?-tough if the number of components of G - S is at most Sfor all non-empty independent sets S in G. We observed that, up to now, all 2-connected graphs in F that have been discovered are ?-tough. Based on this observation, we conjectured that every ?-tough graph belongs to F. The condition for this conjecture is weaker than that in Thomassen’s conjecture: every Hamiltonian graph contains no chromatic zeros in (1, 2).

Finally we shall consider non-?-tough graphs that do have chromatic zeros in (1, 2).

CSMW01 22nd January 2008
15:30 to 16:00
New methods for solving high degree polynomial equations that have multiple roots

The determination of the roots of a polynomial is a classical problem in mathematics to which much effort has been devoted. There exist many methods for their computation, but they all fail on high degree polynomials, or polynomials that have multiple roots. In particular, roundoff errors due to finite precision arithmetic are sufficient to cause a multiple root to break up into a cluster of simple roots, and the problems are compounded when the coefficients of the polynomial are subject to error.

In this talk, I will describe a radically new, and significantly better, method of computing the roots of a polynomial. The method has two stages:

Stage 1: Perform a succession of greatest common divisor (GCD) computations to calculate the multiplicity of each distinct root.

Stage 2: Use the information from Stage 1 to calculate the roots, and then refine them using the method of non-linear least squares.

The GCD calculations in Stage 1 use structured matrix methods, algebraic geometry, the least squares equality problem and methods of information theory. The non-linear least squares in Stage 2 is performed by the Gauss-Newton iteration.

Examples will be given to illustrate the success of the method.

CSMW01 22nd January 2008
16:00 to 16:30
The calculus of combinatorial constructions and Hopf algebras

Bergeron, Labelle, and Leroux describe in their book a calculus of combinatorial constructions. This systemizes many of the constructions that lead to exponential generating functions. Many of the ideas are related to Hopf algebra notions; the talk will explore these connections.

CSMW01 23rd January 2008
10:00 to 11:00
R Fernandez Cluster expansions for hard-core systems: I introduction

CLUSTER EXPANSIONS FOR HARD-CORE SYSTEMS: I INTRODUCTION

The talk will be an introductory presentation of cluster expansions for models with self and nearest-neighbour exclusions. It will focus on the following questions: what are cluster expansions?, what type of information they yield?, how are they used? The general abstract framework ---polymer models--- will be introduced, illustrated with a number of classical examples.

CLUSTER EXPANSIONS FOR HARD-CORE SYSTEMS: II CONVERGENCE CRITERIA

The successive convergence criteria proposed for cluster expansions will be presented and compared. The talk will include a discussion of the contrasting conceptual approaches of the different proofs, as well as numerical consequences for benchmark examples. If time permits, an alternative probabilistic scheme will also be reviewed. This scheme, which is not based on expansions, yields weaker results but does not make use of expansion methods and leads to a perfect simulation algorithm.

CSMW01 23rd January 2008
11:30 to 12:30
R Fernandez Cluster expansions for hard-core systems: II convergence criteria

CLUSTER EXPANSIONS FOR HARD-CORE SYSTEMS: I INTRODUCTION

The talk will be an introductory presentation of cluster expansions for models with self and nearest-neighbor exclusions. It will focus on the following questions: what are cluster expansions?, what type of information they yield?, how are they used? The general abstract framework ---polymer models--- will be introduced, illustrated with a number of classical examples.

CLUSTER EXPANSIONS FOR HARD-CORE SYSTEMS: II CONVERGENCE CRITERIA

The successive convergence criteria proposed for cluster expansions will be presented and compared. The talk will include a discussion of the contrasting conceptual approaches of the different proofs, as well as numerical consequences for benchmark examples. If time permits, an alternative probabilistic scheme will also be reviewed. This scheme, which is not based on expansions, yields weaker results but does not make use of expansion methods and leads to a perfect simulation algorithm.

CSMW01 23rd January 2008
14:00 to 14:30
A simple resummation method for cluster expansions

I will present a simple and (possibly) new method of organizing the (+/- cancellations in the) cluster expansions of polymer models, hard repulsion case. The method is suitable for models where polymers are "cycles" or closed paths in a lattice (Kramers-Wannier representation of the Ising model, perturbations of massless Gaussians) also in several cases where expansions are only nonabsolutely summable.

CSMW01 23rd January 2008
14:30 to 15:00
Enumeration of spanning subgraphs with degree constraints

For a finite (multi-) graph G=(V,E) and functions f,g: V ---> N and natural number j, consider the number of (f,g)-factors of G with exactly j edges. We investigate logarithmic concavity properties of such sequences (as j varies with f and g fixed) by considering the location of zeros of their generating functions. The case f==0 and g==1 is that of the Heilmann-Lieb theorem on matching polynomials. The more general case f<=g<=f+1 appears in earlier work of mine, and the case f==0 and g==2 was considered by Ruelle. We provide a unified approach to these cases via the half-plane property and the Grace-Walsh-Szego coincidence theorem. As a byproduct we find a "circle theorem'' for the zeros of a weighted generating function for the set of all spanning subgraphs of G.

CSMW01 23rd January 2008
15:30 to 16:00
On polynomials arising from zonotopal algebra

Given a graph G, we consider its associated (linear) matroid X, and associate X with three kinds of algebraic structures called external, central, and internal. Each algebraic structure is given in terms of a pair of homogeneous polynomial ideals in n variables that are dual to each other. Algebraically, one encodes properties of the (generic) hyperplane arrangement H(X) associated to X, while the other encodes by duality the properties of the zonotope Z(X) built from the matrix X. These algebraic structures are then applied to obtain various statistics for the graph G. In particular, the Hilbert series of each of the three ideals turn out to be ultimately related to the Tutte polynomial of G, and the grading of the ideals turns out to be related to specific counting functions on subforests or on spanning trees of G. This leads to other combinatorial connections and several open problems as well.

Related Links

CSMW01 23rd January 2008
16:00 to 16:30
I Sarmiento The topological Tutte polynomials of Bollobas and Riordan: properties and relations to other graph polynomials

In [BR01], [BR02], Bollob´as and Riordan defined analogs of the Tutte polynomial for graphs embedded in surfaces, thus encoding topological information lost in the classical Tutte polynomial. We pro- vide a ‘recipe theorem’ for these polynomials and use it to relate them to the generalized transition polynomial, the topological Tutte poly- nomials defined in [Las75], [Las78], [Las79], the parametrized Tutte polynomial of [Zas92] and [BR99], and Bouchet’s Tutte-Martin poly- nomial of isotropic systems. Various evaluations of these polynomi- als of Bollob´as and Riordan, as well as insight into the topological information they encode. The relationship between the generalized transition polynomial and the topological Tutte polynomial extends a result of [Jae90] from planar graphs to arbitrary graphs by giving a relationship between the transition and the R polynomials. We also visit the Kauffman bracket in light of these relationships and that es- tablished between it and the topolofical Tutte polynomial in [CP].

CSMW01 23rd January 2008
16:30 to 17:30
Geometry of polynomials and applications

We discuss closely related geometric properties of zero sets of multivariate polynomials such as real stability, the half-plane property, (Gårding) hyperbolicity and the strong Rayleigh property. In particular, using the latter we define a class of probability measures (called strongly Rayleigh) that contains uniform random spanning tree measures, determinantal measures (for contractions) and distributions for symmetric exclusion processes. We develop a theory of negative dependence for this class of measures and settle several conjectures of Liggett, Pemantle and Wagner. Examples and applications include extensions of Lyons' recent results on determinantal measures and the half-plane property for certain matroids studied by Sokal, Wagner et al.

This is joint work with Petter Brändén (KTH) and Thomas M. Liggett (UCLA).

Related Links

CSMW01 24th January 2008
10:00 to 11:00
Independent sets, lattice gases and the Loavsz Local Lemma

The repulsive lattice gas is an important model in equilibrium statistical mechanics, and has been studied extensively by mathematical physicists. In the special case of a hard-core nearest-neighbor exclusion (i.e. no pair of adjacent sites can be simultaneously occupied), the partition function of the lattice gas on a graph coincides with the independent-set polynomial. Much effort has been devoted to finding regions in the complex plane in which this function is nonvanishing

The Lovasz Local Lemma is a valuable tool in probabilistic combinatorics for estimating the probability that none of a collection of "bad" events occurs. It applies when dependence between events can be controlled by a "dependency graph", and is useful when the graph is very sparse.

In this talk, which presents joint work with Alan Sokal, I will examine a connection between these two apparently disparate subjects. I will discuss closely related results of Shearer in probabilistic combinatorics and of Dobrushin in mathematical physics, as well as a "soft" generalization of the Lovasz Local Lemma.

CSMW01 24th January 2008
11:30 to 12:00
S Janson Zeros of truncated binomial polynomials

We study the set of zeros of the truncated binomial polynomials \sum_{k=0}^r \binom{n}{k} z^k and \sum_{k=r+1}^n \binom{n}{k} z^k as n and r tend to infinity with r/n converging to some number a, and show convergence of the zero sets to parts of a certain curve in the complex plane.

This is joint work with Alex Scott and Alan Sokal.

CSMW01 24th January 2008
14:00 to 15:00
R Shrock Zeros of chromatic and Tutte (Potts) polynomials and general Ising model, and their accumulation sets for families of graphs

We discuss results on zeros of chromatic and Tutte polynomials (the latter being equivalent to the Potts model partition function ) in the q and temperature plane, and their accumulation sets for various families of graphs. We also present results on zeros of the q=2 Ising case in the presence of a nonzero magnetic field. This area combines combinatorics and graph theory with complex analysis and algebraic geometry, as well as statistical physics. A numer of areas for further research are suggested.

CSMW01 24th January 2008
15:30 to 16:00
Zeros of graph-counting polynomials and their accumulation sets

We present zeros of several graph-counting polynomials, including flow polynomial F(G,q), reliability polynomial R(G,p) and Jones polynomial. For both flow and reliability polynomials, we consider, among others, square, triangular and honeycomb lattice strips with various fixed widths and arbitrarily great lengths with several different boundary conditions. We study the zeros of F(G,q) and R(G,p) in the complex q and p planes, respectively, and determine exactly the asymptotic accumulation sets of these zeros in the infinite-length limit. We calculate Jones polynomials for several families of alternating knots and links by computing the Tutte polynomials T(G,x,y) for the associated graphs G. For each of these families we determine the zeros of the Jones polynomial and the accumulation set in the limit of infinitely many crossings. A discussion will be given to the calculation of Jones polynomials for non-alternating links. We also calculate exactly the partition function Z(G,Q,v) of the Q-state Potts model for strip graphs with Q and temperature variable v restricted to satisfy conditions corresponding to the ferromagnetic phase transition on the associated two-dimensional lattices. In the infinite-length limit, we determine the continuous accumulation loci of the partition function zeros in the v and Q planes. General features of these loci are discussed and conjectures are given for properties applicable to arbitrarily large width. Finally, we present the zero distributions of the Q-state Potts model partition function for large Q, and show when these zeros take on approximately circular patterns in a complex plane.

CSMW01 24th January 2008
16:00 to 16:30
Chromatic zeros for some recursively defined families of graphs

We consider some infinite families of recursively defined graphs. The explicite formulas for chromatic polynomials of graphs from the families will be presented. We study the problem of the location of their complex zeros.

CSMW01 24th January 2008
16:30 to 17:00
Self-dual spin systems, zeros of partition function, and error correcting codes

A new infinite class of self-dual translation invariant spin ½ systems will be introduced. (Two systems of this class are known to be solvable: Baxter-Wu triangular model and Union Jack model.) Conjectures about distribution of zeros of partition functions of finite volume systems of this class will be formulated. Numerical and rigorous results supporting the conjectures, and connection with the theory of self-dual cyclic codes, will be discussed.

CSMW01 25th January 2008
10:00 to 11:00
N Biggs Complex roots of chromatic polynomials

I shall begin by explaining how the theory of representations of the symmetric group can be applied to the transfer matrix. This leads to explicit formulae for the chromatic polynomials of families of graphs, in which the terms correspond to partitions of positive integers.

The formulae are well-suited to the application of the Beraha-Kahane-Weiss theorem, describing the limit points of zeros of the polynomials. In simple cases the individual terms can be written explicitly as powers of polynomials, and the resulting limit curves are (parts of) closed curves. In the general case the curves can have end-points and singularities, and I shall discuss some of the interesting phenomena that can occur.

CSMW01 25th January 2008
11:30 to 12:30
J Jacobsen Representations and partition function zeros of the Potts model with and without boundaries

We consider the following four classes of models defined on the annulus, listed in order of increasing generality: 1. Restricted height models with face interactions 2. Fully-packed loop models based on the Temperley-Lieb algebra 3. TL loop models with one boundary generator 4. TL loop models with two boundary generators All of these are different formulations of the Potts model (Tutte polynomial), where, for classes 3 and 4, spins on the rims of the annulus are required to take a different number of states than bulk spins. We show how each class reduces to the one preceding it, provided that one of its parameters takes particular, magical values. In an appropriate part of the phase diagram, these reductions lead to partition function zeros in the more general model. In particular, the reduction from class 2 to 1 gives zeros of the chromatic polynomial at the Beraha numbers, provided one is inside the so-called Berker-Kadanoff phase.

CSMW01 25th January 2008
14:00 to 14:30
Dominant traits in the zeros of two-variate two-terminal reliability polynomials

Various polynomials appear in graph theory: chromatic polynomials, flow polynomials, all-terminal reliability polynomials. All these polynomials are special instances of the Tutte polynomial, and the location of their complex zeros has been actively studied (Biggs, Brown & Colbourn, Chang & Shrock, Royle, Sokal, Welsh, to name but a few). General results have been established for the zeros of recursively defined families of polynomials (Beraha, Kahane, and Weiss): the zeros aggregate asymptotically to sets of algebraic curves and sometimes to isolated points.

In this contribution, we address the two-terminal (or end-to-end) reliability polynomial Rel2, which corresponds to the connectivity of two sites of a graph. Admittedly, this is no graph invariant. However, instead of using the variable $p$ for the (uniform) probability for correct operation of the edges of the graph, we may now consider two variables $p$ and $\rho$ for the edge and site reliabilities, respectively. For a given graph and a pair of sites, we can study the location of the complex zeros of Rel2($p$,$\rho$) as a function of $\rho$.

We present results on a few recursive families of graphs for which the two-terminal reliability polynomial may be computed exactly as a function of $p$,$\rho$ and $n$ (the size of the graph); the associated generating functions have also been derived. The asymptotic (for $n$ going to infinity) location of zeros has been investigated and exhibits:

- the usual sets of algebraic curves,

- appearing (or disappearing) sets of isolated zeros in some cases,

- an expansion of the general structure as $\rho$ goes to 0, which can be described by a power law.

The set of zeros also undergoes several structural transitions at specific, critical values $\rho_c$ --- which are algebraic --- as $\rho$ decreases from 1 to 0.

More surprisingly, by slightly changing the building blocks of the recursive graphs, we may also numerically observe:

- particular values of $\rho$ for which the sets of zeros look much smoother,

- existence (or not!) of several prevailing sets of isolated zeros with different symmetries (of orders 3 and 13, for instance),

- different ``exploding'' families of algebraic curves with different symmetries and expansion rates, too.

Asymptotic, analytical expressions for the above phenomena can actually be deduced from the generating function.

CSMW01 25th January 2008
14:30 to 15:00
Integer symmetric matrices with spectral radius at most 2.019

All graphs with spectral radius (of their adjacency matrix) at most sqrt(2+sqrt(5)) = 2.05817... are known. In joint work with James McKee, we try to extend this result to general symmetric matrices with integer entries. As is clear from the title, we do not get quite as far. Apart from some trivial examples, all the matrices described by the title are represented by 'charged signed graphs' having adjacency matrices with entries 0,1 or -1.

CSM 31st January 2008
14:00 to 15:00
Generalisations of the Heilmann-Lieb theorem, with proofs
CSM 7th February 2008
11:00 to 12:30
An inequality for Tutte polynomials
CSM 14th February 2008
11:30 to 12:30
Orbital chromatic and flow polynomials
CSM 14th February 2008
16:00 to 17:00
Generalised Tutte polynomials
CSM 20th February 2008
15:00 to 17:00
M Jerrum Mixing 101
CSM 21st February 2008
16:00 to 17:00
Abstract polymers with general pair interactions
CSM 25th February 2008
11:00 to 12:00
Graphical partitions

In 1962, S. L. Hakimi proved necessary and sufficient conditions for a given sequence of positive integers d_1, d_2, ..., d_n to be the degree sequence of a non-separable graph or that of a connnected graph. Our goal in this talk is to utilize Hakimi's results to provide generating functions for the functions d_{ns}(2m) and d_c(2m), the number of degree sequences with degree sum 2m representable by non-separable graphs and connected graphs (respectively). From these generating functions, we prove nice formulas for d_{ns}(2m) and d_c(2m) which are simple linear combinations of the values of p(j), the number of integer partitions of j. The proofs are elementary and the talk will be accessible to a wide audience.

This is joint work with Oystein Rodseth, University of Bergen, Norway.

Related Links

CSM 26th February 2008
11:00 to 12:00
V Dokchitser Graph polynomials from an algebraic point of view
CSM 4th March 2008
11:00 to 12:00
Graph polynomials from an algebraic point of view
CSM 6th March 2008
11:30 to 12:30
Osculating paths and oscillating tableaux
CSM 6th March 2008
16:00 to 17:00
The Blume-Emery-Griffiths model with infinite range interactions in the low temperature disordered phase
CSM 11th March 2008
11:00 to 13:00
Algebraic aspects of chromatic roots
CSM 12th March 2008
15:15 to 16:00
Connections between combinatorics and statistical mechanics
CSM 13th March 2008
11:30 to 12:30
A Sokal Complete monotonicity for inverse powers of some combinatorially defined polynomials
CSM 18th March 2008
14:00 to 15:00
S Severini Combinatorics and quantum information theory
CSM 18th March 2008
15:00 to 16:00
Algebraic aspects of chromatic roots
CSM 19th March 2008
15:00 to 16:00
S Shlosman Gibbs ensembles of nonintersecting paths, and determinantal processes
CSM 20th March 2008
11:00 to 12:00
Set-theoretic solutions of the Yang-Baxter equation - a combinatorial approach
CSM 20th March 2008
15:00 to 17:00
M Jerrum Mixing 101

A major theme in next week's workshop will be mixing times of stochastic processes, particularly ones arising in statistical physics and the analysis of algorithms. This tutorial aims to provide orientation for the non-specialist.

CSMW02 25th March 2008
10:00 to 11:00
Random colorings

I will give a survey of results on the analysis of MCMC algorithms for randomly sampling proper vertex k-colorings of an input graph with maximum degree D. In the first part of the talk I will explain how such a sampling algorithm implies an algorithm to estimate the number of k-colorings. The standard reduction considers the problem at a sequence of temperatures, where the infinite temperature problem corresponds to colorings of the empty graph and the zero temperature problem corresponds to colorings of the input graph. I will present recent work (with Stefankovic and Vempala) that reduces the number of intermediate temperatures in this reduction to O*(\sqrt{n}).

After the briefest introduction to coupling, I'll show Jerrum's proof of fast convergence of the single-site Glauber dynamics for any graph when k>2D. We'll then look at more sophisticated coupling arguments, beginning with the work of Dyer and Frieze, that utilize so-called local uniformity properties, which are local properties of random colorings. I'll then explain more recent work of Hayes that utilizes the spectral radius to get improved results for colorings of planar graphs. Finally, we'll see recent work (with Hayes and Vera) that combines the uniformity and spectral radius ideas to prove poly-time convergence of the Glauber dynamics on planar graphs when k>D/logD.

CSMW02 25th March 2008
11:40 to 12:30
Can extra updates delay mixing?

We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance and the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a weighted Hamming metric, so does single-site dynamics started at extremal configurations. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite $n$-vertex graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of $\log n$ compared to updates at uniform random locations. (Joint work with Peter Winkler).

CSMW02 25th March 2008
14:00 to 14:30
Asymptotic enumeration of contingency tables

Contingency tables are nonnegative integer matrices with given row and column sums. Such matrices appear in many combinatorial contexts and have applications in statistics. There has been a lot of work on efficient algorithms for approximately counting these matrices using Markov chains or dynamic programming.

Asymptotic formulae for these matrices have recently been obtained for sufficiently sparse matrices (Greenhill & McKay) and for sufficiently dense matrices when all row sums are equal and all column sums are equal (Canfield & McKay). I will discuss these results and ask whether they provide a practical method for approximate counting.

Joint work with Brendan McKay.

CSMW02 25th March 2008
14:35 to 15:05
A Markov chain for certain triple systems

In 1996, M. T. Jacobson and P. Matthews constructed a Markov chain whose limiting distribution is uniform on Latin squares. This has been a useful tool for exploring the properties of random Latin squares. However, very little is known about the rate of convergence of the Markov chain; more information about this would greatly enhance its value.

A feature of the Jacobson-Matthews Markov chain is that it enlarges the search space by adding "improper" Latin squares which have one "fault"; when we move from an improper Latin square we must fix that fault but may create another one.

The method has been extended to other classes of combinatorial structures (Steiner triple systems and 1-factorizations of complete graphs), and to more general versions of these (corresponding to the generalization from Steiner triple systems to BIBDs with an arbitrary value of lambda. Unfortunately, except in the case of orthogonal arrays (the generalization of Latin squares), the connectedness of the Markov chain is conjectured, but not known to hold. If the conjecture is true, then the limiting distribution in each of these cases will be uniform.

Related Links

CSMW02 25th March 2008
15:40 to 16:10
M Luczak Glauber dynamics for the Ising Model on the Complete Graph

We study the Glauber dynamics for the Ising model on the complete graph on n vertices, also known as the Curie-Weiss model. For the high-temperature regime (\beta < 1), we prove that the dynamics exhibits a cutoff: the total variation distance to stationarity drops from near 1 to near 0 in a window of order n centred at [2(1-\beta)]^{-1} n \log n. For the critical case (\beta =1), we prove that the mixing time is of the order n^{3/2}. In the low-temperature case (\beta > 1), we study metastability. In particular, we show that the Glauber dynamics restricted to states of non-negative magnetization has mixing time O(n \log n). This is joint work with David Levin and Yuval Peres.

CSMW02 25th March 2008
16:15 to 16:45
A new probability inequality and some optimal concentration results

The usual Azuma's inequality assumes absolute bounds on the Martingale differences. This is often too pessimistic, but seems inherently required in the usual moment-generating function method. We prove a new general inequality based on bounds on moments of Martingale differences rather than absolute bounds; while the method used is elementary, it is quite different from the m-g f method.

We present two applications - to bin packing and counting the number of triangles in a random graph. In the first, we prove that the number of bins required to pack n i.i.d. items, each with mean a and variance b^2 is concentrated in an interval of length O(a^{3/2} b) which we show is best possible. Then we prove that the number of triangles in a random graph G_{n,p} (with p<n^{-2/3}) is concentrated in an interval of length (np)^{3/2} which is again the best possible, since this is the standard deviation. We also outline applications to counting the number of H in G_{n,p} for any fixed graph H.

CSMW02 25th March 2008
16:50 to 17:20
D Levin Ising Model on Kn: mixing time for Glauber dynamics at critical ϐ

We study the Glauber dynamics for the Ising model on the complete graph on n vertices, in the critical case (\beta =1). We prove that the mixing time is of the order n^{3/2}. This is joint work with Malwina Luczak and Yuval Peres.

CSMW02 26th March 2008
09:30 to 10:30
F Martinelli The east model: a case study from glassy dynamics

The East model is a prototype of a class of spin models widely used in statistical physics to describe some key aspects of the dynamics of glasses. Here I will review some of its features together with a survey of recent results and techniques from the point of view of MCMC.

Related Links

CSMW02 26th March 2008
10:35 to 11:05
A Sly Rapid mixing of Gibbs sampling on graphs that are sparse on average

We overcome an obstacle of most techniques for analysing the mixing time of the Glauber dynamics, that they are stated in terms of the maximal degree and are therefore insufficient for Erdos Renyi random graphs where the maximum degree grows as order (log n)/(log log n). We show that for most natural models defined on G(n,d/n) if the "temperature" is high enough (as a function of d only) then the mixing time of Glauber dynamics is polynomial. This proves in particular a conjecture of Dyer et.al. proving rapid mixing of random colourings on G(n,d/n) with a constant number of colours.

CSMW02 26th March 2008
11:40 to 12:10
On hitting times and fastest strong stationary times for birth-and-death chains and other skip-free chains

An (upward) skip-free Markov chain with the set of nonnegative integers as state space is a chain for which upward jumps may be only of unit size; there is no restriction on downward jumps. In a 1987 paper generalizing a well-known theorem (usually attributed to Keilson) for birth-and-death chains, Brown and Shao determined, for an irreducible continuous-time skip-free chain and any d, the passage time distribution from state 0 to state d. When the nonzero eigenvalues nu_j of the generator are all real, their result states that the passage time is distributed as the sum of d independent exponential random variables with rates nu_j. We give another proof of their theorem. In the case of birth-and-death chains, our proof leads to an explicit representation of the passage time as a sum of independent exponential random variables. Diaconis and Miclo also recently obtained such a representation, but our construction is much simpler.

We obtain similar (and new) results for a fastest strong stationary time T of an ergodic continuous-time skip-free chain with stochastically monotone time-reversal started in state 0, and we also obtain discrete-time analogs of all our results.

Related Links

CSMW02 26th March 2008
14:00 to 14:30
Cutoff in total variation for birth-and-death chains

We prove that a family of continuous-time or lazy discrete-time birth-and-death chains, exhibits the cutoff phenomenon if and only if the product of the mixing-time and spectral-gap tends to infinity; in this case, the cutoff window of at most the geometric mean between the relaxation-time and mixing-time. An analogous result for convergence in separation was proved earlier by Diaconis and Saloff-Coste (2006) for birth-and-death chains started at an endpoint; we show that for any lazy (or continuous-time) birth-and-death chain with stationary distribution $\pi$, the separation $1 - p^t(x,y)/\pi(y)$ is maximized when $x,y$ are the endpoints. Together with the above results, this implies that total-variation cutoff is equivalent to separation cutoff in any family of such chains. (Joint with J. Ding and Y. Peres).

CSMW02 26th March 2008
14:35 to 15:05
R Montenegro A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm

We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G and find that, if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in order |G|^0.5 steps. This is the first proof of the correct order bound which does not assume that every step of the algorithm produces an i.i.d. sample from G.

Related Links

CSMW02 26th March 2008
15:40 to 16:10
Path coupling without contraction

Path coupling is a useful technique for simplifying the analysis of a coupling of a Markov chain. Rather than defining and analysing the coupling on every pair in the state space of the Markov chain, analysis is done on a smaller set S. If the coefficient of contraction b is strictly less than one, no further analysis is needed in order to show rapid mixing. However, if b=1 then analysis (of the variance) is still required for all pairs in the state space. In this paper we present a new approach which shows rapid mixing in the case b=1 with a further condition which only needs to be checked for pairs in S, greatly simplifying the work involved.

CSMW02 26th March 2008
16:15 to 16:45
Colouring random graphs randomly
CSMW02 26th March 2008
16:50 to 17:20
Multiple random walks in random regular graphs

It was shown that (whp), for $r\ge 3$ the cover time $C_G$ of a random $r$-regular graph $G_r$ is asymptotic to $\theta_r n \ln n$, where $\theta_r=({r-1})/({r-2})$. In this talk we study problems arising from multiple random walks on random regular graphs, and prove the following (whp) results. The time for $k$ independent walks to cover $G_r$ is asymptotic to $ C_G/k$.

For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/{k\choose 2}$. If the walks can communicate on meeting at a vertex, we show that (for most starting positions) the expected time for $k$ walks to broadcast a single piece of information is asymptotic to $((2 \ln k)/k)\theta_r n$, as $k,n$ tend to infinity.

We also establish properties of walks where particles interact when they meet at a vertex by coalescing or by exploding and destroying each other. As an example, the expected extinction time of $k$ explosive particles ($k$ even) tends to $(2\ln 2) \theta_r n $ as $k$ tends to infinity.

CSMW02 27th March 2008
09:30 to 10:00
P Tetali Parking functions and acyclic orientations

Given an undirected graph $G=(V,E)$, and a designated vertex $q\in V$, the notion of a $ G$-parking function (with respect to $q$) has recently been developed and studied by vari ous authors. This notion generalizes the classical notion of a parking function associated with the complete graph, and has been approached from the point of view of sandpile models, chipfiring games etc. In this talk, I will describe some of these connections and describe a simple bijection between maximum $G$-parking functions and certain acyclic orientations of $G$. Of special interest will be the graph of the discrete cube. (This is joint work with Brian Benson.)

CSMW02 27th March 2008
10:05 to 10:35
Rapidly mixing Markov chains and the sharp transition in 2D ising percolation

One of the most well-known classical results for site percolation on the square lattice is that, for all values of the parameter p (except its critical value) the following holds: Either a.s. there is an infinite open cluster or a.s. there is an infinite closed `star' cluster. This result is closely related to the percolation transition being sharp.

The analog of this result has been proved by Higuchi in 1993 for two-dimensional Ising percolation (at fixed temperature T > Tc) with external field h, the parameter of the model.

Using a Markov chain and rapid-mixing results of Martinelli and Olivieri, we show that the Ising model can be `decoded' in terms of i.i.d. random variables in such a way that certain general approximate zero-one laws (sharp-threshold results) can be applied. This leads to an alternative proof of Higuchi's result and puts it in a more general framework.

CSMW02 27th March 2008
10:40 to 11:10
A Frieze Log-concave random graphs

We propose the following model of a random graph on n vertices. Let F be a multi-dimensional distribution with a coordinate for every pair ij with i,j in [n]. Then G(F,p) is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X(i,j) < p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine some basic properties such as the connectivity threshold for the case where F is down-monotone and has a log-concave density. We also consider cases where the X(i,j) are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

CSMW02 27th March 2008
11:40 to 12:10
S Shlosman Properties of the interfaces in the multyphase regimes

We review results about the phase diagram of the high entropy systems. They undergo the first order phase transition, and at the transition temperature the phases with different entropy coexist. If the two phases are sharing the same volume, then the interface between them is formed. We will explain the stability property of this random surface. (Joint work with Yvon Vignaud.)

CSMW02 27th March 2008
14:00 to 14:30
D Randall Proving slow mixing with fault lines and fat contours

We show that for several sampling problems, local dynamics require exponential time to converge to equilibrium. In particular, we apply our techniques to the problems of sampling independent sets on the triangular lattice (the hard-core lattice gas model) and the weighted even orientations of the Cartesian lattice (the 8-vertex model). For each problem, there is a single parameter (corresponding to temperature or fugacity) such that local Markov chains are expected to be fast at high temperature and slow at low termpature. However, establishing slow mixing for these models has been a challenge because standard Peierls arguments based on (d-1)-dimensional contours do not seem to work. Here we extend this approach to "fat contours" that have nontrivial d-dimensional volume, and use these to establish slow mixing of the local chains. In addition, we show that restricting the contours to fat contours containing "fault lines" allow us to further simplify these proofs.

CSMW02 27th March 2008
14:35 to 15:05
A Sokal An introduction to dynamic critical phenomena and cluster algorithms

I give an introduction, aimed at mathematicians and computer scientists, to physics lore about dynamic critical phenomena. I then give an introduction to cluster algorithms, notably those of Swendsen--Wang and Chayes--Machta, which can potentially achieve significant reductions in critical slowing-down compared to local algorithms.

CSMW02 27th March 2008
15:40 to 16:10
J Machta Graphical representations and cluster algorithms

In this talk I discuss developments in graphical representations and associated cluster algorithms. After a review of the Edwards-Sokal spin-bond representation for Potts models and the associated Swendsen-Wang algorithm, I discuss graphical representations and cluster algorithms for other systems including random cluster models for real q>1 and Ising spin systems with external fields and/or frustration.

CSMW02 27th March 2008
16:15 to 17:00
Open problem session
CSMW02 28th March 2008
09:30 to 10:00
D Wilson Card shuffling and Diophantine approximation

The "overlapping-cycles shuffle'' mixes a deck of n cards by moving either the nth card or the (n-k)th card to the top of the deck, with probability half each. We determine the spectral gap for the location of a single card, which, as a function of k and n, has surprising behaviour. For example, suppose k is the closest integer to alpha n for a fixed real alpha in (0,1). Then for rational alpha the spectral gap is Theta(n^{-2}), while for poorly approximable irrational numbers alpha, such as the reciprocal of the golden ratio, the spectral gap is Theta(n^{-3/2}).

Related Links

CSMW02 28th March 2008
10:05 to 10:35
Near Boltzmann-Gibbs measure preserving stochastic variational integrator

This talk presents an explicit, structure-preserving probablistic numerical integrator for Langevin systems, and an efficient, structure-preserving integrator for Langevin systems with holonomic constraints. In a nut-shell, the method does for the Boltzmann-Gibbs measure what symplectic integrators do for energy. More precisely, we prove the method very nearly preserves the Boltzmann-Gibbs measure. As a consequence of its variational design, the algorithm also exactly preserves the symplectic area change associated to Langevin processes. The method with supporting theory enables one to take time-step sizes and friction factors at the limit of stability of the integration scheme (e.g., the time-step size must be smaller than the fastest characteristic frequency in the system).

Related Links

CSMW02 28th March 2008
10:40 to 11:10
B Scoppola Randomised algorithms for the maximum clique problem
CSMW02 28th March 2008
11:40 to 12:10
What happens to a random walk before equilibrium?

Since the pioneering work of Diaconis and Shahshahani, much research has been devoted to the study of the cutoff phenomenon, which describes how a random walk on a finite graph reaches its equilibrium distribution over a dramatically short period of time. However, much less is known about how a random walk behaves before it has reached this equilibrium distribution. The purpose of this talk is to study aspects of this question, with an emphasis on the way a random walk gets away from its starting point. In some interesting cases, the growth of the distance exhibits a phase transition from linear to sublinear behaviour. In other examples, there are different regimes with different scalings but no phase transition. While we do not have a theory at the moment, I will discuss some results which relate this phenomenon to the local geometry of the graph (as perceived by a random walker) and state some conjectures.

Partly joint with Rick Durrett.

CSMW02 28th March 2008
12:15 to 12:45
A Czumaj Testing expansion in bounded degree graphs

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an a-expander is a graph G = (V,E) in which every subset U of V of at most |V|/2 vertices has a neighborhood of size at least a|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately O(n^{1/2}).

We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every a-expander with probability at least 2/3 and rejects every graph that is epsilon-far from an a*-expander with probability at least 2/3, where a* = O(a^2/(d^2 log(n/epsilon))), d is the maximum degree of the graphs, and a graph is called epsilon-far from an a*-expander if one has to modify (add or delete) at least epsilon d n of its edges to obtain an a*-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d^2 n^{1/2} log(n/epsilon)/(a^2 epsilon^3)). We will also briefly discuss the recent improvements due to Kale and Seshadhri, Nachmias and Shapira, who reduced the dependency in the expansion of the rejected graphs from O(a^2/(d^2 log(n/epsilon))) to O(a^2/d^2).

Related Links

CSMW02 28th March 2008
14:00 to 14:30
Bank sampling: a practical proposal for sampling from isolated maxima with the Metropolis algorithm

An easy-to-implement form of the Metropolis Algorithm is described which, unlike most standard techniques, is well suited to sampling from multi-modal distributions on spaces with moderate numbers of dimensions (order ten) in environments typical of investigations into current constraints on Beyond-the-Standard-Model physics. The sampling technique makes use of pre-existing information (which can safely be of low or uncertain quality) relating to the distribution from which it is desired to sample. This information should come in the form of a "bank'' or "cache'' of space points of which {\em at least some} may be expected to be near regions of interest in the desired distribution. In practical circumstances such "banks of clues'' are easy to assemble from earlier work, aborted runs, discarded burn-in samples from failed sampling attempts, or from prior scouting investigations. The technique equilibrates between disconnected parts of the distribution without user input.

Related Links

CSMW02 28th March 2008
14:35 to 15:05
Extremality of Gibbs measure for colorings on trees

We consider the problem of extremality of the free boundary Gibbs measure for k-colorings on the tree of branching factor D. Extremality of the measure is equivalent to reconstruction non-solvability, that is, in expectation, over random colorings of the leaves, the conditional probability at the root for any color tends to 1/k as the height of the tree goes to infinity. We show that when k>2D/ln(D), with high probability, conditioned on a random coloring of the leaves, the bias at the root decays exponentially in the height of the tree. This is joint work with Juan Vera and Eric Vigoda.

CSM 2nd April 2008
14:00 to 15:00
Enumeration of the degree sequences of non-separable graphs and connected graphs

In 1962, S. L. Hakimi proved necessary and sufficient conditions for a given sequence of positive integers d_1, d_2, ..., d_n to be the degree sequence of a non-separable graph or that of a connnected graph. Our goal in this talk is to utilize Hakimi's results to provide generating functions for the functions d_{ns}(2m) and d_c(2m), the number of degree sequences with degree sum 2m representable by non-separable graphs and connected graphs (respectively). From these generating functions, we prove nice formulas for d_{ns}(2m) and d_c(2m) which are simple linear combinations of the values of p(j), the number of integer partitions of j. The proofs are elementary and the talk will be accessible to a wide audience.

This is joint work with Oystein Rodseth, University of Bergen, Norway.

Related Links

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.

CSM 16th April 2008
15:00 to 16:00
Matroids with nine elements

A complete catalogue of all the matroids with eight elements was generated (by computer) at Waterloo nearly 40 years ago, but only in the last couple of years has this catalogue been extended beyond eight elements. After a brief introduction to the basic terminology of matroids, I will describe the construction of the catalogue of matroids with nine elements, and discuss some of its possible applications and/or extensions.

CSM 17th April 2008
11:00 to 12:00
M Loebl Some notes on the combinatorial zeta function
CSMW04 21st April 2008
10:00 to 11:00
Partitions, matrix models, and geometry

Sums of partitions with the Plancherel measure appear in various problems of statistical physics and mathematics (crystal growth, point processes, Gromov-Witten invariants). We rewrite such sums as matrix integrals, which allow to compute their large size expansion to all orders. The coefficients in the expansion are geometric objects called symplectic invariants of spectral curves. This makes a link between combinatorics of partitions, matrix models, algebraic geometry, integrability, quantum field theory and topological string theory.

CSMW04 21st April 2008
11:30 to 12:30
The continuous limit of random planar maps

Planar maps are graphs embedded in the two-dimensional sphere $S^2$, considered up to continuous deformation. They have been studied extensively in combinatorics, but they also have significant geometrical applications. Random planar maps have been used as models of random geometry in theoretical physics. Our goal is to discuss the convergence of rescaled random planar maps viewed as random metric spaces. More precisely, we consider a random planar map $M(n)$, which is uniformly distributed over the set of all planar maps with $n$ vertices in a certain class. We equip the set of vertices of $M(n)$ with the graph distance rescaled by the factor $n^{-1/4}$. We then discuss the convergence in distribution of the resulting random metric spaces as $n\to\infty$, in the sense of the Gromov-Hausdorff distance between compact metric spaces. This problem was stated by Schramm in his 2006 ICM paper, in the special case of triangulations. In the case of bipartite planar maps, we first establish a compactness result showing that a limit exists along a suitable subsequence. We then prove that this limit can be written as a quotient space of the so-called Continuum Random Tree (CRT) for an equivalence relation which has a simple definition in terms of Brownian labels assigned to the vertices of the CRT. This limiting random metric space had been introduced by Marckert and Mokkadem and called the Brownian map. It can be viewed as a ``Brownian surface'' in the same sense as Brownian motion is the limit of rescaled discrete paths. We show that the Brownian map is almost surely homeomorphic to the sphere $S^2$, although it has Hausdorff dimension $4$. Furthermore, we are able to give a complete description of the geodesics from a distinguished point (the root) of the Brownian map, and in particular of those points which are connected by more than one geodesic to the root. As a key tool, we use bijections between planar maps and various classes of labeled trees.

Related Links

CSMW04 21st April 2008
14:00 to 15:00
O Bernardi A bijection for covered maps on orientable surfaces

A map of genus g is a graph together with an embedding in the orientable surface of genus g. For instance, plane trees can be considered as maps of genus 0 and unicellular maps (maps with a single face) are a natural generalisation of plane trees to higher genus surfaces.

In this talk, we consider covered maps, which are maps together with a distinguished unicellular spanning submap. We will present a bijection between covered maps of genus g with n edges and pairs made of a plane tree with n edges and a bipartite unicellular map of genus g with n+1 edges. This bijection allows to recover bijectively some very elegant formulas by Mullin and by Lehman and Walsh. We will also show that our bijection generalises a bijection of Bouttier, Di Francesco and Guitter (which, in turns, generalises a previous bijection of Schaeffer) between bipartite maps and some classes of labelled trees.

CSMW04 21st April 2008
15:30 to 16:30
Vacancy localisation in the square dimer model, statistics of geodesic in large quadrangulations

I shall present two independent projects carried out last year, illustrating the interests of a typical combinatorial statistical mechanist.

- I first consider the classical dimer model on a square lattice with a single vacancy, and address the question of the possible motion of the vacancy induced by dimer slidings. Adapting a variety of techniques (Temperley bijection, matrix tree theorem, finite-size analysis, numerical simulations), we find that the vacancy remains localized albeit in a very weak fashion, leading to non-trivial diffusion exponents. [joint work with M. Bowick, E. Guitter and M. Jeng]

- I next consider the statistical properties of geodesics in large random planar quadrangulations. Introducing "spine trees" extending Schaeffer's well-labeled tree construction, we obtain in particular the generating function for quadrangulations with a marked geodesic. We deduce exact statistics for large quadrangulations both in the "local" and "scaling" limits. [joint work with E. Guitter]

CSMW04 21st April 2008
16:30 to 17:30
Large deviation of the top eigenvalue of a random matrix

The statistical properties of the largest eigenvalue of a random matrix are of interest in diverse fields ranging from disordered systems to string theory. In this talk I'll discuss some recent developements on the theory of extremely rare fluctuations of the largest eigenvalue and its various applications.

Related Links

CSMW04 22nd April 2008
09:00 to 10:00
Three colour statistical model with 'domain wall' boundary conditions

In 1970 Baxter considered the statistical three-coloring lattice model satisfying toroidal boundary conditions. He used an appropriate version of the Bethe anzats and found the partition function of the model in the thermodynamic limit. We consider the same model but with specific boundary conditions. We find a functional equation satisfied by the partition function. A similar equation for the six vertex statistical model can be solved, and its solution can be used to prove the refined alternating-sing matrix conjecture.

CSMW04 22nd April 2008
10:00 to 11:00
Alternating sign matrices from a physicist point of view

There has recently been a convergence of interests between combinatorics and physics through the observation due to Razumov and Stroganov that the components of the ground state wave function of the 6-vertex (at a special value of the anisotropy parameter) model enumerate alternating sign matrices. This correspondence is still mysterious. I shall present my approach to the problem which uses the (Macdonald) polynomial representation of affine-Hecke algebras and points towards a connection with the Quantum Hall Effect.

CSMW04 22nd April 2008
11:30 to 12:30
J de Gier Algebraic structure of the q-Knizhnik-Zamolodchikov equation on a segment, partial sums and punctured plane partitions

We show that solutions of the qKZ equation for the link pattern representation of the Temperley-Lieb algebra have the same structure as the canonical basis defined by Lusztig in tensor products of representation modules of U_q(sl_2). This structure gives in a natural way rise to consider partial sums over qKZ solutions. In the context of the Razumov-Stroganov conjecture we show that such partial sums over qKZ solutions of level one are related to weighted transpose complement cyclically symmetric plane partitions with a hole.

Related Links

CSMW04 22nd April 2008
14:00 to 15:00
Gaudin functions of any order

The Gaudin-Izergin-Korepin determinant plays a fundamental role in the 6-vertex model. We consider a more general determinant det( 1/(x-y)(x-ty)..(x-t^r y)), where x,y are indeterminates in two sets of the same cardinality and r is a fixed integer (the Izergin-Korepin determinant is the case r=1). We give specialization properties, as well as a link with Macdonald polynomials.

Related Links

CSMW04 22nd April 2008
15:30 to 16:30
Multivariate generalisation of Hankel determinants of Catalan numbers and middle binomial coefficients

The Hankel determinants of Catalan numbers and middle binomial coefficients are evaluated as products of simple factors. In this talk, I present multivariate determinant identities involving classical group characters, which reduce to the Hankel determinants of Catalan numbers and middle binomial coefficients if all the variables are equal to 1.

CSMW04 23rd April 2008
09:00 to 10:00
Conformal invariance and universality in the 2D lsing model

We will show that on a lage class of planar graphs, Ising model has a conformally invariant scaling limit at critical temperature. Joint work with Dmitry Chelkak (St.Petersburg State University)

CSMW04 23rd April 2008
10:00 to 11:00
B Nienhuis Entanglement in the XXZ chain

We take an antiferromagnetic XXZ chain in its ground state, and consider a small sequence of sites. The spins on these sites are entangled with the other spins. We show results for the entanglement entropy as a function of the length of the segment and the length of the chain.

CSMW04 23rd April 2008
11:30 to 12:30
Exact valence bond entanglement entropy in the XXZ and related spin chains

Valence bond entanglement entropy has recently been proposed as an alternative to the well-known von Neumann entropy, measuring the information density in the ground state of spin chains. It is the mean value of the number N of valence bonds (spin singlets) connecting a subsystem of length L >> 1 to the remainder of the chain. We determine exactly the complete probability distribution of N in the XXZ spin chain, as well as in other related spin chains. At the combinatorial point (bond percolation) we conjecture exact expressions of that same distribution for finite values of L and the chain length.

CSMW04 23rd April 2008
14:00 to 15:00
X Viennot Alternative tableaux, permutations and partially asymmetric exclusion process

We introduce a new combinatorial object called "alternative tableau". This notion is at the heart of different topics: the combinatorics of permutations and of orthogonal polynomials, and in physics the model PASEP (partially asymmetric exclusion process).

The model PASEP have been recently intensively studied by combinatorists, in particular giving combinatorial interpretations of the stationary distribution (works of Brak, Corteel, Essam, Parvianinen, Rechnitzer, Williams, Duchi, Schaeffer, Viennot, ...). Some interpretations are in term of the so-called "permutation tableaux", introduced by Postnikov, followed by Steingrimsson and Williams, in relation with some considerations in algebraic geometry (total positivity on the Grassmannian).

Permutations tableaux have been studied by Postnikov, Steingrimsson, Williams, Burstein, Corteel, Nadeau and various bijections with permutations have been given. The advantage of introducing alternative tableaux is to give a complete symmetric role for rows and columns. We give a bijection between the two kinds of tableaux and a direct bijection between permutations and alternative tableaux. We also give combinatorial interpretation of the stationary distribution of the PASEP in term of alternative tableaux.

Then we show the relation between alternative tableaux and the combinatorial theory of orthogonal polynomials developed by Flajolet and the author. In particular the Françon-Viennot bijection between permutations and "Laguerre histories" (i.e. some weighted Motzkin paths) plays a central role here and enable us to construct another bijection between permutations and alternative tableaux.

This last bijection is in the same vein as the construction of the classical Robinson-Schensted-Knuth correspondence by "local rules" as originally defined by Fomin. The bijection can also be presented in analogy with Schützenberger "jeu de taquin". We finish the talk by giving "la cerise sur le gâteau": the surprising connection between the two bijections relating permutations and alternative tableaux.

Related Links

CSMW04 23rd April 2008
15:30 to 16:30
The asymmetric exclusion process: an integrable model for non-equilibrium statistical mechanics

The Asymmetric Simple Exclusion Process (ASEP) plays the role of a paradigm in Non-Equilibrium Statistical Mechanics: it is one of the simplest interacting N-body systems far from equilibrium that can be solved analytically. By using the Bethe Ansatz, we calculate the spectral gap of the model and predict global spectral properties such as the existence of multiplets. We then discuss the fluctuations of the current in the stationary state. Finally, we explain that the stationary state of the ASEP and of some of its generalizations with multiple classes of particles has an underlying combinatorial structure that leads naturally to a matrix product representation.

CSMW04 24th April 2008
09:00 to 10:00
N Reshetikhin Dimer partition functions on surface graphs of higher genus
CSMW04 24th April 2008
10:00 to 11:00
Boundary partitions in trees and dimers

Given a finite planar graph, a grove is a spanning forest in which every component tree contains one or more of a specified set of vertices (called nodes) on the outer face. For the uniform measure on groves, we compute the probabilities of the different possible node connections in a grove. These probabilities only depend on boundary measurements of the graph and not on the actual graph structure, i.e., the probabilities can be expressed as functions of the pairwise electrical resistances between the nodes, or equivalently, as functions of the Dirichlet-to-Neumann operator (or response matrix) on the nodes. These formulae can be likened to generalizations (for spanning forests) of Cardy's percolation crossing probabilities, and generalize Kirchhoff's formula for the electrical resistance. Remarkably, when appropriately normalized, the connection probabilities are in fact integer-coefficient polynomials in the matrix entries, where the coefficients have a natural combinatorial interpretation. A similar phenomenon holds in the so-called double-dimer model: connection probabilities of boundary nodes are polynomial functions of certain boundary measurements, and as formal polynomials, they are specializations of the grove polynomials. Upon taking scaling limits, we show that the double-dimer connection probabilities coincide with those of the contour lines in the Gaussian free field with certain natural boundary conditions. These results have direct application to connection probabilities for multiple-strand SLE_2, SLE_8, and SLE_4.

Related Links

CSMW04 24th April 2008
11:30 to 12:30
Dimer packings with gaps and electrostatics: boundary interactions

In earlier work we determined the asymptotics of the correlation function of a collection of gaps in a sea of dimers. This turned out to be governed by the laws of two dimensional electrostatics. In this talk we consider dimer systems that cover a half-plane, and determine the interaction of gaps in this system with the boundary. We analyze the cases of constrained and free boundary conditions. They both lead to analogs of the method of images from electrostatics.

CSMW04 24th April 2008
14:00 to 15:00
Exact enumeration of plane partitions and rhombus tilings

Problems of exact enumeration of plane partitions and rhombus tilings have appeared frequently in connection with the Razumov-Stroganov conjecture and related conjectures. In this talk, I shall discuss a miscellany of such problems, older and newer, relations in between, and the main ideas to solve such problems.

CSMW04 24th April 2008
15:30 to 16:30
The bead model
CSMW04 25th April 2008
09:00 to 10:00
Theory of electric networks: the two-point resistance and impedance

We present a new formulation of the determination of the resistance and impedance between two arbitrary nodes in an electric network. The formulation applies to networks of finite and infinite sizes. An electric network is described by its Laplacian matrix L, whose matrix elements are real for resistors and complex for impedances. For a resistor network the two-point resistance is obtained in terms of the eigenvalues and eigenvectors of L, and for an impedance network the two-point impedance is given in terms of those of L*L. The formulation is applied to regular lattices and non-orientable surfaces. For networks consisting of inductances and capacitances, the formulation predicts the occurrence of multiple resonances.

Related Links

CSMW04 25th April 2008
10:00 to 11:00
Prudent and quasi-prudent self-avoiding walks and polygons

Prudent self-avoiding walks and quasi-prudent self-avoiding walks are proper subsets of self-avoiding walks in dimension 2 or greater. Prudent SAW are not allowed to take a step in a direction which, if continued, would encounter a previously visited vertex. Quasi-prudent walks are self-avoiding walks where a step to a neighbouring vertex v can only be taken if there is a prudent way to escape from v (in other words, if v can be seen from infinity). Polygon versions of the walks can be defined as walks (prudent or quasi-prudent) which end at a vertex adjacent to their starting point.

A variety of results, both rigorous and numerical, will be given for these models, mainly for two-dimensional walks, but we also have some preliminary results for walks on a three-dimensional lattice.

CSMW04 25th April 2008
11:30 to 12:30
Counting lattice paths with the kernel method

Models of directed paths have been used extensively in the scientific literature to model linear polymers. In this talk we examine directed path models of a linear polymer in various confining geometries.

We solve these models by showing that the generating function satisfies a functional equation and deriving formal solutions by using the kernel method.

While some generating functions are rational or algebraic, it turns out that in some interesting cases the generating functions are not differentiably finite.

CSM 30th April 2008
11:00 to 12:00
A Grassmann algebra related to spanning forests
CSM 1st May 2008
11:00 to 12:00
Algebraic numbers/chromatic roots working group
CSM 1st May 2008
14:00 to 15:00
S Noble The clustering coefficient of a scale-free random graph
CSM 2nd May 2008
11:00 to 12:00
Can we solve it? Some numerical tests revealing analytic structure.
CSM 2nd May 2008
14:00 to 15:00
Large deviations and quantum gravity
CSM 8th May 2008
16:00 to 17:00
Trees versus connected graphs I

There are many more connected graphs than tress. yet with the weighting used in physics, connected graphs are dominated by trees. This talk will sketch how the problem of parameterizing connected graphs by trees is a geometry problem. It will also present an identity for connected graphs in which a tree structure emerges naturally in the course of the proof.

CSM 9th May 2008
14:00 to 15:00
D Penman Random randomly coloured graphs
CSM 15th May 2008
16:00 to 17:00
Trees versus connected graphs II
There are many more connected graphs than tress. yet with the weighting used in physics, connected graphs are dominated by trees. This talk will sketch how the problem of parameterizing connected graphs by trees is a geometry problem. It will also present an identity for connected graphs in which a tree structure emerges naturally in the course of the proof.
CSM 21st May 2008
10:00 to 11:00
On the shameful conjecture
CSM 29th May 2008
11:00 to 12:00
On the interaction of defects in lattices
CSM 2nd June 2008
17:00 to 18:00
Maps and graphs on surfaces

Graph coloring is a extensively studied subject, partly because of its relation to optimization (time table problems). One of the main sources of inspiration was the 4 Color Problem (now a theorem). In 1890 Heawood considered the analogue for higher surfaces. This problem, known as the Heawood map color theorem, was settled by Ringel and Youngs in 1968. For example, the number of colors needed in the projective plane and the Klein bottle is 6. For the torus it is 7, etc. Although these numbers tend to infinity, there is a 5 color theorem for each surface in the following sense: For every surface S, there exist a finite number of (forbidden) graphs such that an arbitrary graph on S can be 5-colored if and only if it does not contain one of the forbidden graph as a subgraph. There is no 4-color theorem of this type. In the talk these and related results will be discussed.

CSM 5th June 2008
16:00 to 17:00
Zero-free regions for multivariate Tutte polynomials
CSM 10th June 2008
11:00 to 12:00
Negative dependence and zeros of multivariate polynomials I
CSM 12th June 2008
11:00 to 12:00
Bounding chromatic roots of series parallel graphs in terms of maxmaxflow
CSM 17th June 2008
11:00 to 12:00
Negative dependence and zeros of multivariate polynomials II
CSM 18th June 2008
10:00 to 11:00
K Kulesza The upper bound on number of graphs, with fixed number of vertices, that vertices can be coloured with n colours
CSM 18th June 2008
11:00 to 12:00
Negative dependence and zeros of multivariate polynomials III
CSM 19th June 2008
11:00 to 12:00
Negative dependence and zeros of multivariate polynomials IV
CSM 20th June 2008
11:00 to 12:00
A complexity dichtomy for partition functions with mixed signs
CSMW05 23rd June 2008
10:00 to 11:00
D Welsh Harris's inequality and its descendants

In 1960 T.E.Harris proved a fundamental early result about percolation probabilities. As part of his proof he needed an inequality which he described in the following words: "Its truth seems obvious but ...."

In this talk I shall survey some of the classical correlation inequalities which generalise Harris's inequality and were proved in the period 1960 - 1980.

I will also discuss some applications and more recent open problems in the area of combinatorial probability.

CSMW05 23rd June 2008
11:40 to 12:20
An inequality for Tutte polynomials

Let $G$ be a graph without loops or bridges and $T_G(x,y)$ be its Tutte polynomial. We give sufficient conditions for the inequality $T_G(x,y)T_G(y,x)\geq T_G(z,z)^2$ to hold. We deduce in particular that $T_G(x,0)T_G(0,x)\geq T_G(z,z)^2$ for all positive real numbers $x,z$ with $x\geq z(z+2)$. Our result was inspired by a conjecture of Merino and Welsh that $\max\{T_G(2,0),T_G(0,2)\}\geq T_G(1,1)$.

CSMW05 23rd June 2008
14:00 to 15:00
Inequalities with applications to percolation theory and related fields

In this talk I will discuss some inequalities that have been, and still are, quite useful in percolation and certain interacting particle systems. Emphasis will be on disjoint-occurrence inequalities and (applications of) influence inequalities. (These notions will be explained during the talk). I will also state some open problems and conjectures.

CSMW05 23rd June 2008
15:40 to 16:20
Entropy inequalities for sums and applications

A large class of entropy inequalities is developed for sums of random vectors, giving both lower and upper bounds for the entropy of a sum. These inequalities are combinatorial in nature, being indexed by hypergraphs, and have fruitful applications to probability and information theory. One consequence is monotonicity behaviors in limit theorems, including for the entropy in the classical central limit theorem, and for relevant functionals in laws of large numbers for certain random matrix models.

Related Links

CSMW05 23rd June 2008
16:20 to 17:00
A Gasparyan Probabilistic hyperdeterminantal inequalities

Over many years I was interested in possible foundation of a multidimensional matrix theory involving multidimensional determinants and other tensor generalizations of usual matrix structures. As a result one can notify series of hyperdeterminantal identities from which I derive probabilistic inequalities concerning n-ary scalar products, means, correlations and higher moments of random variables. This makes possible generalization of many classical and recent results on Greene functions, Bogoliubov quasimeans, cummulants and some other quantities. Among results we indicate several generalizations of Chebyshev, Griffiths and other FKG-type inequalities.

CSMW05 24th June 2008
10:00 to 11:00
Correlation questions

We will also mention a few results but mainly want to focus on some of the "annoying" problems in this area.

CSMW05 24th June 2008
11:40 to 12:20
F Dong Bounds for the real zeros of Chromatic polynomia
CSMW05 24th June 2008
14:00 to 15:00
Negative dependence and the geometry of polynomials

We present a powerful tool in the emerging theory of negative dependence. The knowledge of the zeros of the generating (partition) function of your discrete probability measure can be of help when it comes to proving negative dependence properties, just as it is in the Lee-Yang program on phase transitions.

The connection with the geometry of zeros of (multivariate) polynomials allows one to use strong results due to Grace-Walsh-Szegö and Gårding. A consequence is that the symmetric exclusion process with product initial distribution is negatively associated at positive times, as conjectured by Liggett and Pemantle. We also generalize recent work of Lyons on determinantal measures.

This is based on joint work with J. Borcea (Stockholm) and T. M. Liggett (UCLA)

Related Links

CSMW05 24th June 2008
15:40 to 16:20
O Holtz Zonotopes and gradings on graphs
The talk is based on joint work with Amos Ron and is a continuation of an earlier talk given within this program. Given a graph G, we consider its associated (linear) matroid X, and associate X with three kinds of algebraic structures called external, central, and internal. Each algebraic structure is given in terms of a pair of homogeneous polynomial ideals in n variables that are dual to each other. Algebraically, one encodes properties of the (generic) hyperplane arrangement H(X) associated to X, while the other encodes by duality the properties of the zonotope Z(X) built from the matrix X. In particular, the Hilbert series of each of the three ideals turn out to be ultimately related to the Tutte polynomial of G, and the grading of the ideals turns out to be related to specific counting functions on subforests or on spanning trees of G. The focus of this talk is on the properties of the gradings on graphs that arise in this fashion.
CSMW05 24th June 2008
16:20 to 17:00
The profile of a relational structure

A relational structure is a set carrying a collection of relations with specified arities. Graphs, partial orders, circular orders, etc. are examples. The age of an infinite relational structure is the class of all finite structures embeddable into it, and the profile is the sequence (f0,f1,f2,...), where fn is the number of n-element structures in the age, up to isomorphism.

Quite a lot is known about the rate of growth of the profile; much less about "local" inequalities relating individual values of fn for different n. It is known that fn<=f{n+1}. There are two proofs, one using finite combinatorics and linear algebra, the other using Ramsey's Theorem.

There is a commutative associative graded algebra, the age algebra, whose Hilbert series is the generating function of the profile. Recently, Maurice Pouzet showed that, if the age of R cannot be made smaller by deleting a point, then the age algebra is an integral domain. It follows, using dimension theory, that f{m+n}>=fm+fn-1. A further conjecture on the age algebra would imply that, under the same assumption, g{m+n}>=gm+gn-1, where gn=f{n+1}-fn.

All these results apply to the situation where G is an infinite permutation group on a set Omega, and fn is the number of G-orbits on the set of n-element subsets of Omega. The assumption in the preceding paragraph translates into the condition that G has no finite orbits on Omega.

CSMW05 25th June 2008
10:00 to 11:00
Projection and entropy inequalities
In the talk I shall review the classical Loomis{Whitney and Shannon inequalities, their extensions by Han; Shearer; Bollob¶as and Thomason; and Madiman and Tetali; and shall present some new inequalities I have proved with Paul Balister.
CSMW05 25th June 2008
11:40 to 12:20
D Stark Poisson approximation of the number of triangles in random intersection graphs

An intersection graph is constructed from a set of vertices and an auxiliary set of objects by assigning subsets of the objects to the vertices and connecting two vertices if their object sets are not disjoint. In a random intersection graph G(n,m,p) there are n vertices, m objects and each object is in the object set of each vertex independently and with probability p. We use Stein's method to approximate the distribution of triangles in G(n,m,p) by a Poisson distribution.

CSMW05 25th June 2008
14:00 to 15:00
Linear operators preserving stability and the Lee-Yang program

We characterize all linear operators on spaces of multivariate polynomials preserving the property of being non-vanishing when the variables are in (products of) prescribed open circular domains, which solves the higher dimensional counterpart of a long-standing classification problem going back to P\'olya-Schur. This also leads to a self-contained theory of multivariate stable polynomials and a natural framework for dealing in a uniform manner with Lee-Yang type problems in e.g. combinatorics, statistical mechanics, complex analysis, which we illustrate with several examples. This is joint work with Petter Brändén.

CSMW05 25th June 2008
15:40 to 16:20
A Berry-Esseen inequality for student's statistic

We present a Berry-Esseen inequality with explicit constants for the distribution of Student's statistic, and give a solution to the Lyapunov problem. We show also that no non-uniform Berry--Esseen inequality may hold for Student's statistic.

CSMW05 25th June 2008
16:20 to 17:00
C McDiarmid Lipschitz functions on graphs
Let G be a connected graph. A real vector x indexed by the vertices is called Lipschitz if the values on the ends of each edge differ by at most 1. Given a suitable function f(x) we are interested in the maximum value of f(x-\bar{x}) over all Lipschitz x. This maximum value f^*(G) is related to certain isoperimetric inequalities.
CSMW05 26th June 2008
10:00 to 11:00
A Sokal Correlation nequalities in statistical mechanics

I present an overview of work done by mathematical physicists, mostly in the 1970s and 1980s, that proves a variety of increasingly sophisticated inequalities for the correlation functions of ferromagnetic Ising and related models. Many of these constructions are ingenious but ad hoc, and cry out for systematization and extension by combinatorialists. I will discuss in particular the duplicate-variables method, the random-current method (and graphical predecessors), and the random-walk method. Moreover, there exist many plausible (and useful) conjectured correlation inequalities that we have no idea how to prove. I hope to interest combinatorialists and probabilists in attacking some of these unsolved problems.

Related Links

CSMW05 26th June 2008
11:40 to 12:20
Abstract polymers with stable pair interactions
A convergence criterion of cluster expansion is presented in the case of an abstract polymer system with stable pair interactions (i.e. not necessarily hard core or repulsive).
CSMW05 26th June 2008
14:00 to 15:00
S Miracle-Sole Mathematical aspects of wetting
Wetting phenomena, as other aspects of the coexistence of phases, can be modeled, from a microscopic point of view, by a lattice gas, like the Ising model, or an interface model. In the first part of the talk, I describe some basic facts and results of the theory, many of which have been obtained with the help of correlation inequalities. In a second part of the talk, I present some recent results of a joint work with K. Alexander and F. Dunlop, that concern an interface model. This system presents a sequence of layering transitions, whose levels increase with the temperature, and complete wetting above a certain value of this quantity.
CSMW05 26th June 2008
15:40 to 16:20
Resummation of cluster (Mayer) expansions

For polymer models, suitable rearrangement (resummation, renormalization) of expansions of their partition functions is often a key step in making them useful, when evaluating their free energy or when estimating their "surface terms". Most interesting is the case, when resummation enables to estimate also sums of non-absolutely converging terms. I will show examples of polymer models (where polymers are cycles resp. walks with hard or soft repulsion) which are close to those appearing in the study of perturbations of massless gaussian models and which allow some interesting resummations, and useful bounds on their convergence

CSMW05 26th June 2008
16:20 to 17:00
V Levit Inequalities involving the coefficients of independence polynomials

In this talk, we survey the most important results referring the inequalities connecting coefficients of independence polynomials of various families of graphs.

CSMW05 27th June 2008
10:00 to 11:00
The guessing number of a graph

The following game was introduced by Soren Riis, as an euqivalent form of a problem in information transfer. A group of people are given dices and each person throws the dice so that everyone else, can see the outcome, but nobody can see their own result. Next everybody has to guess their own results without communicating with the others, and the group wins the game if everybody guesses correctly.. The surprising fact is that the probability of a win in this game is independent of N.

In this talk I will discuss the extension of this game to general graphs, the graph describes whose results an individual can see, and how the fractional chromatic number and entropy inequalities can be used to find the exact win probability for a large class of graphs.

CSMW05 27th June 2008
11:40 to 12:20
Monomer correlations on the square lattice
In 1963 Fisher and Stephenson conjectured that the correlation function of two oppositely colored monomers in a sea of dimers on the square lattice is rotationally invariant in the scaling limit. More precisely, the conjecture states that if one of the monomers is fixed and the other recedes to infinity along a fixed ray, the correlation function is asymptotically $C d^(-1/2)$, where $d$ is the Euclidean distance between the monomers and $C$ is a constant independent of the slope of the ray. In 1966 Hartwig rigorously determined $C$ when the ray is in a diagonal direction, and this remains the only direction settled in the literature. We generalize Hartwig's result to any finite collection of monomers along a diagonal direction. This can be regarded as a counterpart of a result of Zuber and Itzykson on n-spin correlations in the Ising model. A special case proves that two same-color monomers interact in a different way than suggested by physicists in the literature.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons