Videos and presentation materials from other INI events are also available.
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 LeeYang 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 BrownColbourn conjecture on zeros of reliability polynomials is false arXiv:math/0202034 [math.CO] YoungBin Choe, James G. Oxley, Alan D. Sokal, David G. Wagner Homogeneous multivariate polynomials with the halfplane property arXiv:condmat/0012369 [condmat.statmech] Alan D. Sokal Chromatic roots are dense in the whole complex plane arXiv:condmat/9904146 [condmat.statmech] Alan D. Sokal Bounds on the Complex Zeros of (Di)Chromatic Polynomials and PottsModel 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 4Color 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 listchromatic 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 2nanacci constants and all natural powers of them cannot be root of any chromatic polynomial. Finally, we introduce new numbers related to nannaci 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 kedge 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 zerofree. Jackson conjectured in 1993 that every 3connected nonbipartite graph has no chromatic zeros in (1, 2). It was recently disproved by Royle’s discovery of some counterexamples. 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 2connected 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 nonempty independent sets S in G. We observed that, up to now, all 2connected 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 nonlinear 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 nonlinear least squares in Stage 2 is performed by the GaussNewton 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 hardcore systems: I introduction CLUSTER EXPANSIONS FOR HARDCORE SYSTEMS: I INTRODUCTION The talk will be an introductory presentation of cluster expansions for models with self and nearestneighbour 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 HARDCORE 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 hardcore systems: II convergence criteria CLUSTER EXPANSIONS FOR HARDCORE SYSTEMS: I INTRODUCTION The talk will be an introductory presentation of cluster expansions for models with self and nearestneighbor 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 HARDCORE 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 (KramersWannier 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 HeilmannLieb 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 halfplane property and the GraceWalshSzego 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 Bouchets TutteMartin 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 halfplane 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 halfplane 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 hardcore nearestneighbor 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 independentset 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 graphcounting polynomials and their accumulation sets We present zeros of several graphcounting 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 infinitelength 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 nonalternating links. We also calculate exactly the partition function Z(G,Q,v) of the Qstate Potts model for strip graphs with Q and temperature variable v restricted to satisfy conditions corresponding to the ferromagnetic phase transition on the associated twodimensional lattices. In the infinitelength 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 Qstate 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 
Selfdual spin systems, zeros of partition function, and error correcting codes A new infinite class of selfdual translation invariant spin ½ systems will be introduced. (Two systems of this class are known to be solvable: BaxterWu 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 selfdual 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 wellsuited to the application of the BerahaKahaneWeiss 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 endpoints 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. Fullypacked loop models based on the TemperleyLieb 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 socalled BerkerKadanoff phase. 

CSMW01 
25th January 2008 14:00 to 14:30 
Dominant traits in the zeros of twovariate twoterminal reliability polynomials Various polynomials appear in graph theory: chromatic polynomials, flow polynomials, allterminal 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 twoterminal (or endtoend) 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 twoterminal 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 HeilmannLieb 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 nonseparable 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 nonseparable 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 BlumeEmeryGriffiths 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 
Settheoretic solutions of the YangBaxter 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 nonspecialist. 

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 kcolorings 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 kcolorings. 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 singlesite 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 socalled 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 polytime 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 singlesite 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 JacobsonMatthews 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 1factorizations 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 CurieWeiss model. For the hightemperature 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 lowtemperature case (\beta > 1), we study metastability. In particular, we show that the Glauber dynamics restricted to states of nonnegative 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 momentgenerating 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 mg 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 birthanddeath chains and other skipfree chains An (upward) skipfree 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 wellknown theorem (usually attributed to Keilson) for birthanddeath chains, Brown and Shao determined, for an irreducible continuoustime skipfree 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 birthanddeath 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 continuoustime skipfree chain with stochastically monotone timereversal started in state 0, and we also obtain discretetime analogs of all our results. Related Links


CSMW02 
26th March 2008 14:00 to 14:30 
Cutoff in total variation for birthanddeath chains We prove that a family of continuoustime or lazy discretetime birthanddeath chains, exhibits the cutoff phenomenon if and only if the product of the mixingtime and spectralgap tends to infinity; in this case, the cutoff window of at most the geometric mean between the relaxationtime and mixingtime. An analogous result for convergence in separation was proved earlier by Diaconis and SaloffCoste (2006) for birthanddeath chains started at an endpoint; we show that for any lazy (or continuoustime) birthanddeath 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 totalvariation 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 selfintersections 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=({r1})/({r2})$. 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 wellknown 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 twodimensional Ising percolation (at fixed temperature T > Tc) with external field h, the parameter of the model. Using a Markov chain and rapidmixing 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 zeroone laws (sharpthreshold 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 
Logconcave random graphs We propose the following model of a random graph on n vertices. Let F be a multidimensional 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 ErdosRenyi model is the special case when F is uniform on the 01 unit cube. We determine some basic properties such as the connectivity threshold for the case where F is downmonotone and has a logconcave 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 trianglefree 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 hardcore lattice gas model) and the weighted even orientations of the Cartesian lattice (the 8vertex 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 (d1)dimensional contours do not seem to work. Here we extend this approach to "fat contours" that have nontrivial ddimensional 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 SwendsenWang and ChayesMachta, which can potentially achieve significant reductions in critical slowingdown 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 EdwardsSokal spinbond representation for Potts models and the associated SwendsenWang 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 "overlappingcycles shuffle'' mixes a deck of n cards by moving either the nth card or the (nk)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 BoltzmannGibbs measure preserving stochastic variational integrator This talk presents an explicit, structurepreserving probablistic numerical integrator for Langevin systems, and an efficient, structurepreserving integrator for Langevin systems with holonomic constraints. In a nutshell, the method does for the BoltzmannGibbs measure what symplectic integrators do for energy. More precisely, we prove the method very nearly preserves the BoltzmannGibbs 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 timestep sizes and friction factors at the limit of stability of the integration scheme (e.g., the timestep 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 vertexexpansion: an aexpander 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 aU. 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 aexpander with probability at least 2/3 and rejects every graph that is epsilonfar 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 epsilonfar 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 boundeddegree 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 easytoimplement form of the Metropolis Algorithm is described which, unlike most standard techniques, is well suited to sampling from multimodal distributions on spaces with moderate numbers of dimensions (order ten) in environments typical of investigations into current constraints on BeyondtheStandardModel physics. The sampling technique makes use of preexisting 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 burnin 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 kcolorings on the tree of branching factor D. Extremality of the measure is equivalent to reconstruction nonsolvability, 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 nonseparable 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 nonseparable 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 nonseparable 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 2connected graphs. Explicit examples. *Note : This lecture is preparatory to the reading of papers of Pierre Leroux and collaborators. These papers are available below. Other material, including a link to the book "Combinatorial Species and Treelike Structures", can be found on Pierre Leroux's web page Introduction to the Theory of Species of Structures, by François Bergeron, Gilbert Labelle, and Pierre Leroux. Papers and slides on Mayer graph weights:
Papers and slides on twoconnected graphs:


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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, GromovWitten 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 twodimensional 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 GromovHausdorff 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 socalled 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, finitesize analysis, numerical simulations), we find that the vacancy remains localized albeit in a very weak fashion, leading to nontrivial 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 welllabeled 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 threecoloring 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 alternatingsing 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 6vertex (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 affineHecke 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 qKnizhnikZamolodchikov 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 TemperleyLieb 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 RazumovStroganov 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 GaudinIzerginKorepin determinant plays a fundamental role in the 6vertex model. We consider a more general determinant det( 1/(xy)(xty)..(xt^r y)), where x,y are indeterminates in two sets of the same cardinality and r is a fixed integer (the IzerginKorepin 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 wellknown 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 socalled "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çonViennot 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 RobinsonSchenstedKnuth 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 nonequilibrium statistical mechanics The Asymmetric Simple Exclusion Process (ASEP) plays the role of a paradigm in NonEquilibrium Statistical Mechanics: it is one of the simplest interacting Nbody 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 DirichlettoNeumann 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 integercoefficient polynomials in the matrix entries, where the coefficients have a natural combinatorial interpretation. A similar phenomenon holds in the socalled doubledimer 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 doubledimer 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 multiplestrand 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 halfplane, 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 RazumovStroganov 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 twopoint 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 twopoint resistance is obtained in terms of the eigenvalues and eigenvectors of L, and for an impedance network the twopoint impedance is given in terms of those of L*L. The formulation is applied to regular lattices and nonorientable 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 quasiprudent selfavoiding walks and polygons Prudent selfavoiding walks and quasiprudent selfavoiding walks are proper subsets of selfavoiding 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. Quasiprudent walks are selfavoiding 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 quasiprudent) 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 twodimensional walks, but we also have some preliminary results for walks on a threedimensional 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 scalefree 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 5colored if and only if it does not contain one of the forbidden graph as a subgraph. There is no 4color theorem of this type. In the talk these and related results will be discussed. 

CSM 
5th June 2008 16:00 to 17:00 
Zerofree 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 disjointoccurrence 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 nary 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 FKGtype 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 LeeYang program on phase transitions. The connection with the geometry of zeros of (multivariate) polynomials allows one to use strong results due to GraceWalshSzegö 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 nelement 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+fn1. A further conjecture on the age algebra would imply that, under the same assumption, g{m+n}>=gm+gn1, 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 Gorbits on the set of nelement 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 LeeYang program We characterize all linear operators on spaces of multivariate polynomials preserving the property of being nonvanishing when the variables are in (products of) prescribed open circular domains, which solves the higher dimensional counterpart of a longstanding classification problem going back to P\'olyaSchur. This also leads to a selfcontained theory of multivariate stable polynomials and a natural framework for dealing in a uniform manner with LeeYang 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 BerryEsseen inequality for student's statistic We present a BerryEsseen inequality with explicit constants for the distribution of Student's statistic, and give a solution to the Lyapunov problem. We show also that no nonuniform BerryEsseen 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 duplicatevariables method, the randomcurrent method (and graphical predecessors), and the randomwalk 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 MiracleSole 
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 nonabsolutely 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 nspin correlations in the Ising model. A special case proves that two samecolor monomers interact in a different way than suggested by physicists in the literature.
