Suppose $G$ is a (weighted) connected graph and let $T$ denote a random spanning tree of $G$, chosen uniformly (or respecting the edge weights). It is known that for any distinct edges $e, f$ $$\mathbb P(e\in T \,|\, f \in T) %= \frac{\mathbb P(e,f\in T)}{\mathbb P(f\in T)} \leq \mathbb P(e\in T) .$$ In words, conditioning on one edge being in $T$ can only decrease the probability of $T$ containing another given edge, so we can interpret this as a ''repulsive interaction'' of edges in a random spanning tree. A standard proof of this inequality is to view $G$ as a resistor network, and use the fact that $$ \mathbb P(e\in T) = \text{fraction of current through $e$ when current is sent from $e^-$ to $e^+$ in $G$}$$ where $e^-$, $e^+$ denote the endpoints of $e$. The conditional probability $\mathbb P(e\in T \,|\, f\in T)$ is then interpreted as current flow inside the graph $G/f$ with edge $f$ contracted. Contracting this edge (i.e. sending its resistance to 0) makes it easier for current to flow from $e^-$ to $e^+$ without passing through edge $e$, hence the inequality.
There is also a nice quantitative version of this negative correlation inequality, which is equivalent after rescaling to $$ \mathbb P(e\in T)\mathbb P(f\in T) - \mathbb P(e,f \in T) \geq 0 .$$ Let $H$ denote the ''transfer-impedance matrix'' of $G$, which is the $E \times E$ matrix with entries $$ H(e,f) = \text{fraction of current through $\vec f$ when current is sent from $e^-$ to $e^+$ in $G$}.$$ This requires choosing a preferred orientation for each edge ($H(e,f)$ may be negative), but the choice of orientation will not matter. Note that on the diagonal $H(e,e) = \mathbb P(e\in T)$. The matrix $H$ is actually symmetric: in the unweighted case $H(e,f) = H(f,e)$, while in the weighted case their ratio is equal to the ratio of weights of corresponding edges.
In a paper from 1993 (also on arXiv), Burton and Pemantle showed that the probability $\mathbb P(e_1, \ldots, e_k \in T)$ is equal to the determinant of the corresponding principal minor of $H$ (Theorem 1.1, page 1331). In particular, for a $2\times 2$ minor we have $$ \mathbb P(e\in T)\mathbb P(f\in T) - \mathbb P(e,f \in T) = H(e,f)^2 \geq 0 \tag{$\star$}$$ in the unweighted case, or with a factor of $w(e)/w(f)$ in the weighted case.
We can also phrase this result in more combinatorial terms. For simplicity suppose that $G$ is unweighted. If we let $\kappa(G)$ denote the number of spanning trees of $G$, then $$ \mathbb P(e\in T) = \frac{\kappa(G / e)}{\kappa(G)}. $$ The $2\times 2$ transfer-impedance theorem says that $$ \kappa(G/ e)\kappa(G/ f) - \kappa(G)\kappa(G/ \{ e, f\} ) = N^2 \tag{$*$}$$ for some integer $N = N(G,e,f) = \kappa(G)H(e,f)$. Combinatorially, $N(G,e,f)$ is the signed-count of spanning unicycles of $G$ which contain $\vec e$ and $\vec f$ in the cycle, signed according to whether or not their orientations in the cycle agree.
My questions:
- Are there any known combinatorial / bijective proofs of these results? Are there any useful applications of the fact that we get a perfect square in $(*)$?
From what I understand, the argument used by Burton and Pemantle is not combinatorial. I read Pemantle's expository notes (pages 39-46) rather than the paper.
- What do you get from taking determinants of non-principal minors of the transfer-impedance matrix? Are there any references on this?
I have done some preliminary computations that suggest these may be nice.
- Is any of this useful for arbitrary matroids? How much generalizes?
An arbitrary matroid obviously (?) doesn't exist as an electrical network, since it doesn't have vertices. There are known counterexamples to negative correlation in matroids, e.g. in this preprint of Huh, Schröter, and Wang (page 2). However we can still define a transfer-impedance matrix $H(e,f)$ to satisfy $(\star)$, with possibly imaginary entries. Do the larger minors of this matrix tell us anything useful about the matroid?
