MARK KAC SEMINAR

The multivariate Tutte polynomial (known to physicists as the Potts-model partition function) can be defined on an arbitrary finite graph G, or more generally on an arbitrary matroid M, and encodes much important combinatorial information about the graph (indeed, in the matroid case it encodes the full structure of the matroid). It contains as a special case the familiar two-variable Tutte polynomial – and therefore also its one-variable specializations such as the chromatic polynomial, the flow polynomial and the reliability polynomial – but is considerably more flexible. I begin by giving an introduction to all these problems, stressing the advantages of working with the multivariate version. I then discuss some questions concerning the complex zeros of the multivariate Tutte polynomial, along with their physical interpretations in statistical mechanics (in connection with the Yang–Lee approach to phase transitions) and electrical circuit theory. Along the way I mention numerous open problems.

Reference

A.D.S., The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, arXiv:0503607.

In the first part of the talk, I will present the parallel chip firing model. In this model, we start with some number of chips on each vertex of a graph, and evolve by parallel firing: in each time step, every vertex that has at least as many chips as neighbors, fires one chip to each neighbor. It has been observed that if we start with the chips uniformly at random placed on a large graph, then the 'density' (average number of chips per vertex) suffices to predict with high accuracy the 'activity' (average number of firing vertices per time step). A plot of the activity as a function of the density reminds one of a staircase. I will show several examples and the proof of our staircase theorem for the flower graph.

The second part of the talk will be about a popular theory of self-organized criticality, that relates the critical behavior of driven dissipative systems to that of systems with conservation. In particular, this theory predicts that the stationary density of the driven abelian sandpile model should be equal to the threshold density of the corresponding parallel chip firing model. This "density conjecture" has been proved for the underlying graph Z. Research into this conjecture has focused mainly on the underlying graph Z²: the stationary density was proved to be equal to 17/8 to at least twelve decimals, while the threshold density was simulated to be 2.125 to three decimals.

We have investigated both the driven sandpile model and the parallel chip firing model for several graphs, and we show (by large-scale simulation or by proof) that the stationary density is not equal to the threshold density when the underlying graph is any of Z², the complete graph K_n, the Cayley tree, the ladder graph, the bracelet graph, or the flower graph.

(joint work with Lionel Levine and David Wilson)