Georgia Institute of Technology College of Sciences

We consider higher order Markov random fields to study independent sets in regular graphs of large girth (i.e. Bethe lattice, Cayley tree). We give sufficient conditions for a second-order homogenous isotropic Markov random field to exhibit long-range boundary independence (i.e. decay of correlations, unique infinite-volume Gibbs measure), and give both necessary and sufficient conditions when the relevant clique potentials of the corresponding Gibbs measure satisfy a log-convexity assumption. We gain further insight into this characterization by interpreting our model as a multi-dimensional perturbation of the hardcore model, and (under a convexity assumption) give a simple polyhedral characterization for those perturbations (around the well-studied critical activity of the hardcore model) which maintain long-range boundary independence. After identifying several features of this polyhedron, we also characterize (again as a polyhedral set) how one can change the occupancy probabilities through such a perturbation. We then use linear programming to analyze the properties of this set of attainable probabilities, showing that although one cannot acheive denser independent sets, it is possible to optimize the number of excluded nodes which are adjacent to no included nodes.