3
$\begingroup$

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:

  1. 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.

  1. 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.

  1. 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?

$\endgroup$
1
$\begingroup$

For question 3, the analogue of the transfer-impedance matrix for a linear matroid (more precisely, a linear matroid plus a choice of matrix $M$, whose rows represent it) is treated in Lyons's paper on determinantal probability measures. It is fairly easy to see that there is a probability measure on the bases of the matroid that generalizes the measure on spanning trees of a graph coming from the Kirchhoff matrix-tree theorem (just use Cauchy-Binet on $\det (M^TM)$).

Lyons's paper shows that this measure is determinantal (Theorem 5.1, perhaps already known from earlier work, see Remark 5.2) and also establishes some negative association properties (section 6). The bases now carry weights (equal to the squared determinants of the corresponding square submatrices of $M$) which cannot be made equal in general (unless the matroid is regular and $M$ is unimodular) (see Corollary 5.5), so the measure is typically far from being the uniform one. Note that these measures have applications to e.g. higher-dimensional spanning trees.

The survey "Determinantal Processes and Independence" by Hough, Krishnapur, Peres and Virág has some further useful information, including a farily simple algorithm for sampling bases from the associated probability measure. Unfortunately it's not nearly as nice as e.g. Wilson's algorithm or even Aldous-Broder for sampling random spanning trees; I think one issue is that it's not clear what the analogue of a random walk should be in this generality, though see the papers of Mike Catanzaro, e.g. this one, for some work in that direction in the high-dimensional spanning tree setting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.