Georgia Institute of Technology College of Sciences

Recently, there has been great interest in understanding the fundamental limits of our ability to sample from the independent sets (i.s.) of a graph. One approach involves the study of the so-called hardcore model, in which each i.s. is selected with probability proportional to some fixed activity $\lambda$ raised to the cardinality of the given i.s. It is well-known that for any fixed degree $\Delta$, there exists a critical activity $\lambda_{\Delta}$ s.t. for all activities below $\lambda_{\Delta}$, the sampled i.s. enjoys a long-range independence (a.k.a. uniqueness) property when implemented on graphs with maximum degree $\Delta$, while for all activities above $\lambda_{\Delta}$, the sampled i.s. exhibits long-range dependencies. Such phase transitions are known to have deep connections to the inherent computational complexity of the underlying combinatorial problems. In this talk, we study a family of measures which generalizes the hardcore model by taking more structural information into account, beyond just the number of nodes belonging to the i.s., with the hope of further probing the fundamental limits of what we can learn about the i.s. of a graph using only local information. In our model, the probability assigned to a given i.s. depends not only on its cardinality, but also on how many excluded nodes are adjacent to exactly $k$ nodes belonging to the i.s., for each $k$, resulting in a parameter for each $k$. We generalize the notion of critical activity to these ``neighborly measures", and give necessary and sufficient conditions for long-range independence when certain parameters satisfy a log-convexity(concavity) requirement. To better understand the phase transitions in this richer model, we view the classical critical activity as a particular point in the parameter space, and ask which directions can one move and still maintain long-range independence. We show that the set of all such ``directions of uniqueness” has a simple polyhedral description, which we use to study how moving along these directions changes the probabilities associated with the sampled i.s. We conclude by discussing implications for choosing how to sample when trying to optimize a linear function of the underlying probabilities.