Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph

This paper proves that for sufficiently large $n$, the uniform probability measures on three specific families of spanning subgraphs of the complete graph $K_n$—namely connected spanning subgraphs, forests with exactly $k$ components, and connected spanning subgraphs with excess $k$—satisfy the pairwise negative correlation property.

The Gist

Imagine you have a giant party with $n$ guests. Every pair of guests could shake hands, but they haven't yet. The "Complete Graph" ($K_n$) is the list of all possible handshakes.

Now, imagine a magical rule: we randomly decide which handshakes actually happen. We are interested in two specific scenarios:

1. The Connected Party: We only look at the handshakes where everyone is connected to everyone else, either directly or through a chain of friends. (No one is left out in the cold).
2. The Forest Party: We look at handshakes where no one forms a "loop" (like A shakes B, B shakes C, and C shakes A). This creates a "forest" of trees. We might want exactly 2 separate groups of friends, or 3, etc.

The paper investigates a specific question about friendship dynamics in these scenarios: Does knowing that two people shook hands make it more or less likely that two other people shook hands?

The Big Question: "Do Friends Make More Friends?"

In probability, this is called correlation.

• Positive Correlation: If A shakes B's hand, it makes it more likely that C shakes D's hand. (Maybe they are all part of a popular clique).
• Negative Correlation: If A shakes B's hand, it makes it less likely that C shakes D's hand. (Maybe the "handshake budget" is limited, or the structure of the group forces a trade-off).

The authors are looking for Pairwise Negative Correlation (p-NC). They want to prove that in these specific "party" scenarios, if two edges (handshakes) exist, it slightly reduces the chance that two other specific edges exist.

The Three Main Findings (The "Party Rules")

The paper proves that for a sufficiently large number of guests ($n$), the following three "party rules" always exhibit this negative correlation:

1. The "Everyone Must Be Connected" Rule

The Scenario: We pick a random set of handshakes, but we only keep the ones where the whole group is connected.
The Finding: If you know that Guest A shook hands with Guest B, it makes it slightly less likely that Guest C shook hands with Guest D.
The Analogy: Imagine the group is a single giant web. If you pull on one strand (A-B), the tension spreads through the web, making it slightly harder for a distant, unrelated strand (C-D) to hold its own weight without breaking the balance. The paper proves that for big enough parties, this "tension" effect always wins.

2. The "Exactly $k$ Groups" Rule

The Scenario: We pick a random set of handshakes that form exactly $k$ separate groups (forests). For example, $k=2$ means the party splits into two distinct cliques with no handshakes between them.
The Finding: Even when we force the party to split into specific numbers of groups, the negative correlation holds.
The Analogy: Think of a school with $k$ different lunch tables. If two students sit at Table 1, it slightly reduces the "room" or "probability" for two other specific students to sit at Table 2, because the total number of handshakes is fixed by the rules of the forest.

3. The "Exactly $k$ Extra Loops" Rule

The Scenario: We look at connected groups that have exactly $k$ "loops" (cycles). A loop is when A-B-C-A happens. $k=0$ means no loops (a tree); $k=1$ means exactly one loop (a unicyclic graph).
The Finding: Even when we allow for a specific number of loops, the negative correlation persists.
The Analogy: Imagine the party is a rollercoaster track. If you add a specific number of loops to the track, the geometry of the track forces a trade-off. Adding a loop here restricts where you can build a loop there.

How Did They Solve It? (The Detective Work)

The authors didn't just guess; they used two main detective tools:

1. The "Almost Connected" Trick (For Rule #1):
   They realized that if you randomly pick handshakes with a 50/50 chance, the group is almost always connected if the party is big enough. The only time it isn't connected is if someone is totally isolated (no handshakes at all).

   • The Metaphor: They treated the problem like a game of "Is anyone alone?" They calculated the odds of someone being isolated. They found that knowing A and B are connected makes it slightly less likely that C is isolated, which mathematically proves the negative correlation.

2. The "Counting Machine" (For Rules #2 and #3):
   For the forest and loop scenarios, they used advanced math (generating functions and complex analysis) to count exactly how many ways the party can be arranged.

   • The Metaphor: Imagine a super-computer that lists every possible way the guests can shake hands without forming loops. The authors used this list to calculate the exact probability of two specific handshakes happening together versus apart. They found that for large $n$, the math always tilts toward negative correlation.

Why Does This Matter?

This isn't just about party handshakes. These mathematical structures appear in:

• Physics: Modeling how magnets align or how fluids flow through porous rocks.
• Network Science: Understanding how the internet or social networks hold together.
• Computer Science: Designing algorithms that need to avoid loops or ensure connectivity.

The "Random Cluster Model" (the physics background) suggests that for certain settings, things should be negatively correlated. This paper confirms that for these specific, highly symmetric "Complete Graph" parties, the math holds up perfectly when the party is big enough.

The "But..." (The Caveat)

The paper also points out a funny twist: This doesn't work for small, weirdly shaped parties.
If you have a small graph that isn't a perfect "Complete Graph" (where everyone can shake hands with everyone), the negative correlation can break.

• The Metaphor: In a small, awkward party with only 4 people, if A shakes B's hand, it might actually force C and D to shake hands to keep the group connected. The "budget" of handshakes is so tight that the rules change. But once the party gets huge (large $n$), the "Complete Graph" symmetry takes over, and the negative correlation rule becomes universal.

Summary

In simple terms: In a large, perfectly connected society, if two people are linked, it slightly reduces the likelihood that two other specific people are linked, provided we are looking at specific types of group structures (like forests or connected webs). The authors proved this using a mix of probability tricks and heavy-duty counting math.

Technical Summary

Here is a detailed technical summary of the paper "Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph" by Pengfei Tang and Zibo Zhang.

1. Problem Statement and Motivation

The paper investigates the Pairwise Negative Correlation (p-NC) property for uniform probability measures on specific families of spanning subgraphs of the complete graph $K_n$.

• Context: The study is motivated by the Random-Cluster Model (Fortuin-Kasteleyn-Ginibre model) with parameter $q \in (0, 1)$. It is conjectured that for $q < 1$, the random-cluster measure satisfies the p-NC property, meaning that for any two distinct edges $e$ and $f$, the probability that both are open is less than or equal to the product of their individual probabilities of being open:
  $$\mu(\omega(e)=1, \omega(f)=1) \leq \mu(\omega(e)=1) \cdot \mu(\omega(f)=1)$$

• The Limiting Cases: As $q \to 0$, the random-cluster measure converges to uniform measures on specific subgraph families:

  1. Uniform Spanning Trees (UST): Well-known to satisfy p-NC.
  2. Uniform Spanning Forests (USF): The p-NC property was conjectured and verified for large $n$ by Stark (2026) and numerically for small graphs.
  3. Uniform Connected Subgraphs ($P_{UC}$): The measure on all connected spanning subgraphs.
  4. Truncated Measures: Uniform measures on forests with exactly $k$ components ($P_{k}^{UF}$) and connected subgraphs with excess $k$ ($P_{k}^{UC}$).

• The Gap: While the p-NC property is established for USTs and large-$n$ USFs, the property for uniform connected subgraphs and their truncations (specifically $k$-forests and $k$-excess connected subgraphs) on complete graphs was an open problem. Furthermore, it is known that p-NC does not hold for these measures on arbitrary graphs, making the symmetry of $K_n$ crucial.

2. Methodology

The authors employ distinct mathematical techniques tailored to the specific structure of each family of subgraphs:

A. Uniform Connected Subgraphs ($P_{UC}$)

• Percolation Reformulation: The authors reformulate the p-NC inequality for $P_{UC}$ using Bernoulli(1/2) bond percolation on $K_n$. Since the uniform measure on connected subgraphs is the conditional measure of Bernoulli(1/2) percolation given connectivity, the problem reduces to estimating conditional disconnection probabilities.
• Asymptotic Analysis: They utilize results from Erdős–Rényi random graph theory ($G(n, 1/2)$). The key insight is that for large $n$, the probability of disconnection is dominated by the existence of isolated vertices.
• Inclusion-Exclusion: They perform precise estimates of the probability that the graph is disconnected, conditioned on specific edges being open, using inclusion-exclusion principles and Bonferroni inequalities to bound higher-order terms.

B. Uniform $k$-Component Forests ($P_{k}^{UF}$)

• Combinatorial Counting: The proof relies on an explicit counting formula for the number of $k$-forests in $K_n$ derived by Liu and Chow (2000).
• Graph Contraction: To count forests containing specific edges, the authors use the technique of edge contraction. The number of $k$-forests containing edges $e$ and $f$ is equated to the number of $k$-forests in the contracted graph $K_n / \{e, f\}$.
• Moment Methods: They compare the joint probability $P(\omega(e)=1, \omega(f)=1)$ with the square of the marginal probability $P(\omega(e)=1)^2$. This involves calculating the first and second moments of the degree distribution in random $k$-forests.
• Asymptotic Expansions: They derive high-order asymptotic expansions for the number of $k$-forests and those containing specific edges as $n \to \infty$.

C. Uniform $k$-Excess Connected Subgraphs ($P_{k}^{UC}$)

• Singular Analysis: This is the most technically demanding part. The authors use singularity analysis of exponential generating functions (EGF).
• Generating Functions: They utilize the relationship between the EGF for connected graphs with excess $k$ ($W_k(z)$) and the tree function $T(z)$ (where $T(z) = z e^{T(z)}$).
• Wright's Recursion: They employ recursive relations developed by Wright to express $W_k(z)$ as rational functions of $T(z)$ (or $\theta = 1-T(z)$).
• Coefficient Extraction: Using the transfer theorems from Flajolet and Sedgewick (specifically for functions with algebraic singularities), they extract the asymptotic behavior of the coefficients $[z^n]W_k(z)$, which correspond to the number of subgraphs $C_{n, n+k}$.
• Case-by-Case Analysis: They explicitly compute asymptotic expansions for small $k$ ($0 \leq k \leq 5$) and provide a general recursive framework for$k \geq 6$ to prove the leading order behavior.

3. Key Contributions and Results

The paper establishes the following main theorems for the complete graph $K_n$:

1. Theorem 1.4 (Uniform Connected Subgraphs):
   There exists a constant $N$ such that for all $n \geq N$, the uniform measure on connected spanning subgraphs of $K_n$ satisfies the p-NC property.

   • Significance: This is the first verification of p-NC for uniform connected subgraphs on any graph family.

2. Theorem 1.5 (Uniform $k$-Forests):
   For any fixed integer $k \geq 2$, there exists $N(k)$ such that for all $n \geq N(k)$, the uniform measure on $k$-component forests of $K_n$ satisfies p-NC.

   • Note: For small $k$ (e.g., $k=2,3,4$), the property holds for all $n$ where the measure is defined.

3. Theorem 1.6 (Uniform $k$-Excess Connected Subgraphs):
   For any fixed integer $k \geq 0$, there exists $N(k)$ such that for all $n \geq N(k)$, the uniform measure on connected subgraphs with excess $k$ (i.e., $n+k$ edges) satisfies p-NC.

   • Significance: This covers unicyclic subgraphs ($k=0$) and higher excess cases.

4. Technical Details of the Proofs

• Disconnection Probabilities: For Theorem 1.4, the authors show that the dominant term in the disconnection probability is $n(1/2)^{n-1}$ (isolated vertices). By conditioning on edges being open, they show the "cost" of disconnection increases slightly, leading to the negative correlation.
• Asymptotic Ratios: For Theorems 1.5 and 1.6, the core of the proof involves showing that the ratio of the joint probability to the product of marginals is strictly less than 1 for large $n$.
  • For $k$-forests, they show $p_1 \approx \frac{3}{n^2}$ while the product of marginals is $\approx \frac{4(n-k)^2}{n^2(n-1)^2}$. The asymptotic expansion reveals the inequality holds.
  • For $k$-excess connected subgraphs, they derive the asymptotic form:
    $$P_{k}^{UC}(\omega(e)=\omega(f)=1) = \frac{3}{n^2} + \frac{9(k+1)}{n^3} + O(n^{-7/2})$$
    Comparing this with the marginal product confirms the inequality for large $n$.

5. Significance and Open Questions

• Validation of Conjectures: The results provide strong evidence for the conjecture that random-cluster measures with $q < 1$ exhibit negative dependence, specifically in the $q \to 0$ limit.
• Truncation Behavior: The paper highlights that while p-NC holds for the full measures on $K_n$, it is not preserved under truncation in general graphs (Example 5.5 shows a counterexample for 2-forests on a specific graph). However, the high symmetry of $K_n$ ensures the property holds for its truncations.
• Future Directions:
  • The authors conjecture that the p-NC property holds for all $n$ (not just sufficiently large $n$) for these measures on $K_n$, though proving this requires tedious finite case checking.
  • They suggest extending these methods to other highly symmetric graphs, such as the hypercube $\{0,1\}^n$, where the critical probability for connectivity is exactly $1/2$.

In summary, this paper resolves the p-NC property for three fundamental families of spanning subgraphs on complete graphs using a blend of probabilistic percolation arguments, combinatorial enumeration, and advanced analytic combinatorics (singularity analysis). It significantly advances the understanding of negative dependence in random graph models.