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 \begin{equation} \frac{\mathbb{P}(e\in E(T))\mathbb{P}(f\in E(T))}{\mathbb{P}(e,f\in E(T)) } \end{equation} for all possible choices of $e$ and $f$?
$\begingroup$ $\endgroup$
5 
- 1$\begingroup$ 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$. $\endgroup$Brendan McKay– Brendan McKay2017-10-25 22:52:07 +00:00Commented Oct 25, 2017 at 22:52
- 1$\begingroup$ I am looking for an upper bound not lower bound. e.g. for a triangle we obtain 4/3, so 1 cant do. $\endgroup$SRB– SRB2017-10-25 23:32:43 +00:00Commented Oct 25, 2017 at 23:32
- $\begingroup$ Right, sorry for the noise. $\endgroup$Brendan McKay– Brendan McKay2017-10-26 12:06:38 +00:00Commented Oct 26, 2017 at 12:06
- $\begingroup$ is there some motivation for looking at this ratio in particular? $\endgroup$Harry Richman– Harry Richman2017-10-26 14:22:11 +00:00Commented Oct 26, 2017 at 14:22
- $\begingroup$ 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 $\endgroup$Harry Richman– Harry Richman2017-11-08 22:35:45 +00:00Commented Nov 8, 2017 at 22:35
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
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$.
$\begingroup$
$\endgroup$
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.
