Random partitions from random graphs

Abstract

Given a graph G with some marked nodes a, b, c, ... we get a
set partition over {a, b, c, ...} according to which of the marked
nodes are in the same connected component in G and which are not. If
we choose G from some probability distribution D, we get in this way a
probability distribution E on these set partitions. The focus of this
talk is the image of the map D -> E where D ranges over all
distributions given by independent bond percolation on undirected
graphs containing a, b, c, .... This image gives a unified way of
thinking about several correlation inequalities for paths in graphs. I
will present some old, some new, and some conjectured such
inequalities from this perspective.