Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph

Abstract

We investigate the pairwise negative correlation (p-NC) property for uniform probability measures on several families of spanning subgraphs of the complete graph $K_n$. Motivated by conjectured negative dependence properties of the random-cluster model with $q<1$, we focus on three natural families: the set of all connected spanning subgraphs, the set of forests with exactly $k$ components, and the set of connected spanning subgraphs with excess $k$, where $k$ is a fixed integer. We prove that for each of these families, the associated uniform measure satisfies the p-NC property provided $n$ is sufficiently large. Our results extend earlier work on uniform forests and provide the first verification of the p-NC property for uniform connected subgraphs and their truncations on complete graphs.

52 pages plus an appendix. Comments are very welcome