skip to content

Timetable (CSMW05)

Combinatorial and Probablistic Inequalities

Monday 23rd June 2008 to Friday 27th June 2008

Monday 23rd June 2008
08:30 to 10:00 Registration
10:00 to 11:00 D Welsh ([Oxford])
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.

11:00 to 11:30 Coffee at Newton Institute
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)$.

12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 Inequalities with applications to percolation theory and related fields

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

15:00 to 15:30 Tea at Newton Institute
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

16:20 to 17:00 A Gasparyan ([PSI RAS])
Probabilistic hyperdeterminantal inequalities

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

17:00 to 18:30 Welcome Wine Reception at Newton Institute
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Tuesday 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.

11:00 to 11:30 Coffee at Newton Institute
11:40 to 12:20 F Dong ([Nanyang Technological])
Bounds for the real zeros of Chromatic polynomia
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 Negative dependence and the geometry of polynomials

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

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

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

Related Links

15:00 to 15:30 Tea at Newton Institute
15:40 to 16:20 O Holtz ([UC Berkeley/Tech. Univ. Berlin])
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.
16:20 to 17:00 The profile of a relational structure

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

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

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

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

18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Wednesday 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.
11:00 to 11:30 Coffee at Newton Institute
11:40 to 12:20 D Stark ([QMUL])
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.

12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 Linear operators preserving stability and the Lee-Yang program

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

15:00 to 15:30 Tea at Newton Institute
15:40 to 16:20 A Berry-Esseen inequality for student's statistic

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

16:20 to 17:00 C McDiarmid ([Oxford])
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.
19:15 to 23:00 Conference Dinner at Emmanuel College (The Old Library)
Thursday 26th June 2008
10:00 to 11:00 A Sokal ([NYU/UCL])
Correlation nequalities in statistical mechanics

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

Related Links

11:00 to 11:30 Coffee at Newton Institute
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).
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 S Miracle-Sole ([CNRS])
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.
15:00 to 15:30 Tea at Newton Institute
15:40 to 16:20 Resummation of cluster (Mayer) expansions

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

16:20 to 17:00 V Levit ([Ariel University Center of Samaria])
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.

18:30 to 20:00 Cambridge Universtiy Press Reception
Friday 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.

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