3
$\begingroup$

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$?

$\endgroup$
  • 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 Oct 25 '17 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 Oct 25 '17 at 23:32
  • $\begingroup$ Right, sorry for the noise. $\endgroup$ – Brendan McKay Oct 26 '17 at 12:06
  • $\begingroup$ is there some motivation for looking at this ratio in particular? $\endgroup$ – Harry Richman Oct 26 '17 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 Nov 8 '17 at 22:35
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\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.