Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph

Abstract

We study pairwise negative correlation for three families of uniform spanning-subgraph measures on the complete graph. In Part~I, we consider the uniform probability measure on connected spanning subgraphs and prove pairwise negative correlation for all sufficiently large complete graphs. In Part~II, we study the uniform measure on spanning forests with a prescribed number of connected components and prove pairwise negative correlation for every fixed number of components when the number of vertices is sufficiently large. In Part~III, we consider connected spanning subgraphs with prescribed excess and establish the analogous result for every fixed excess. The three parts are self-contained and are intended as separate manuscripts.

arXiv commentThis version reorganizes the original manuscript into three self-contained parts, each of which is intended to be submitted separately.The mathematical arguments are essentially those of the original version, with some corrections, reorganization, and additional exposition