Tutte seminar - Arun Mani

Some observation on correlations in graphs

Abstract:

It is known that if e,f are two distinct non-loop edges of a connected graph G and T is a spanning tree of G selected uniformly at random, then the two events  e ∈ T and f ∈ T are negatively correlated. Similar negative correlations have also been observed and conjectured for randomly chosen spanning forests and spanning connected subgraphs of G, and more generally, such negative correlation inequalities have been conjectured for the Tutte polynomial of G. In this talk, I will give an overview of these conjectures, some partial results and an interesting application to obtaining bounds for the asymptotic growth rate of the Tutte polynomial of the square lattice as its dimensions tend to infinity.