Conditional probability that a random spanning tree contains the edge e

Let $G$ be a connected simple graph with two distinct edges $e,f \in E(G)$. Choose a random spanning tree $T\subseteq G$, my question is whether there are any known upper bound for the following $$\frac{\mathbb{P}(e\in E(T))\mathbb{P}(f\in E(T))}{\mathbb{P}(e,f\in E(T)) }$$ for all possible choices of $e$ and $f$?

• If $e$ and $f$ are both bridges, then all three probabilities are equal to 1. So the best general upper bound is 1. You need to impose additional conditions if you want a smaller bound. For example, you could require the graph to be $k$-connected for some $k\ge 2$. – Brendan McKay Oct 25 '17 at 22:52
• I am looking for an upper bound not lower bound. e.g. for a triangle we obtain 4/3, so 1 cant do. – SRB Oct 25 '17 at 23:32
• Right, sorry for the noise. – Brendan McKay Oct 26 '17 at 12:06
• is there some motivation for looking at this ratio in particular? – Harry Richman Oct 26 '17 at 14:22
• Maybe this is already clear (e.g. from the title), but I found it useful and non-immediate to think of this as the ratio between the probability $\mathbb P(e\in T)$ and the conditional probability $\mathbb P(e\in T \,|\, f\in T)$. The fact that this ratio is at least 1 can be thought of as a "repulsive" interaction of edges in a random spanning tree – Harry Richman Nov 8 '17 at 22:35

There is no constant upper bound, as shown by the following example. Take two vertices $v, u$ and connect them with $n \geq 2$ edge-disjoint paths of two edges. This graph has $n 2^{n - 1}$ spanning trees. The number of spanning trees containing any fixed edge $e$ is $(n + 1)2^{n - 2}$. However, for any $v-u$ path $e, f$ the number of spanning trees containing both $e$ and $f$ is only $2^{n - 1}$. The ratio is thus $\frac{(n + 1)^2}{4n} = \Omega(n)$.

It may still be interesting to determine the largest possible ratio among graphs on $n$ vertices as a function of $n$.

I claim an upper bound on this ratio is $O(D)$ where $D$ is the maximum degree of the graph. In a simple graph, this also implies the bounds $O(n)$ and $O(m)$ where the graph has $n$ vertices and $m$ edges.

Recall that the probability $\mathbb P(e\in T)$ is equal to the effective resistance between the ends of $e$, where we interpret the graph $G$ as a resistor network with unit resistances.

Given an edge $f \in G$, let $G/f$ denote the graph with $f$ contracted. The conditional probability $\mathbb P(e\in T \,|\, f\in T)$ is equal to the probability that a random spanning tree in $G/f$ contains $e$, which is the effective resistance between the ends of $e$ in the resistor network $G/f$.

Thus, we are asked to find an upper bound on $$\frac{\mathbb P(e\in T)}{\mathbb P(e\in T \,|\, f\in T)} = \frac{Res_G(e)}{Res_{G/f}(e)} \leq \frac1{Res_{G/f}(e)},$$ since the ends of $e$ are connected by a unit resistor by assumption. Thus it suffices to show that $Res_{G/f}(e) \geq \Omega(1/D)$.

We know the resistance is positive since we are not allowing multiple edges in $G$, and the question comes down to finding a lower bound on the effective resistance between any distinct nodes in a resistor network with maximum degree $O(D)$. (Note that the maximum degree of $G/f$ is bounded by $2D-2$.) We claim that $\Omega(1/D)$ is such a lower bound.

The effective resistance between nodes $s$ and $t$ is equal to the voltage drop when 1 unit of current is sent from $s$ to $t$. Since $s$ has at most $D$ adjacent unit resistors, some resistor must receive at least $1/D$ units of current, so the voltage drop across this resistor will be at least $1/D$. This gives a lower bound for the total voltage drop from $s$ to $t$, as claimed.

Note: I'm pretty sure this argument works for any graph (allowing loops and multiple edges) as long as the edges $e$ and $f$ are contained in some spanning tree.

I'm also pretty sure $2D-2$ works as an upper bound, but I wrote $O(D)$ to be safe. Maybe the $2D$ can be lowered further.