Probabilistic problem on random spanning trees

Question

Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$.

Let $T(E_T,V)$ be a uniformly generated random spanning tree of $G$, where $E_T\subseteq E$ denotes its edge set. Given any vertex $v\in V$, we denote by $D_T(v)$ its degree in $T$ and by $S_T(v)$ the sum of $f(v')$ over all vertices $v'$ adjacent to $v$ in $T$.

---

Question: How can we prove (or disprove) that, for all connected simple graphs $G(V, E)$, all vertices $v\in V$, and all functions $f:V\to\{1,-1\}$, we have $$\mathbb{E}[S_T(v)]\cdot\mathbb{E}\left[\frac{S_T(v)}{D_T(v)}\right]\ge 0\,,$$ where the expectation is taken over the generation of the random spanning tree $T$ of $G$?

Answer 1

This is not really an answer, but it's a suggestion of where to look for a counterexample. I played around for a few hours and couldn't quite get the parameters working, and it's possible they're unworkable. I'd be really interested in seeing a proof showing that no example like the one I'm outlining could serve as a counterexample.

Let $H$ be a (simple, connected) graph and let $w$ be a vertex in $H$ such that e.g. $\mathbb{E} D_S(w) \approx r/2$ but $P(D_S(w) < r/4) > 2/3$, where $S$ is the uniform spanning tree on $H$. That is, most spanning trees on $H$ include a fairly small fraction of the edges incident to $w$, but enough of them a lot of the edges to give the distribution of $D_S(w)$ a pretty substantial positive skew. (The parameters $1/2, 1/4, 2/3$ here are probably not right.)

Construct $G$ and $f$ as follows. Start with a vertex $v$, glue $m$ copies $H_1, \dots, H_m$ of $H$ to $v$ (identifying each $w_j$, the copy of $w$ in $H_j$, with $v$). Let $f = -1$ on all the vertices in the $H_j$'s. Add an additional $n$ vertices of degree $1$, connected only to $v$. Let $f = 1$ on these degree $1$ vertices. Here $m$ and $n$ are natural number parameters that one would have to tune. Note that $v$ has degree $n+mr$ in $G$.

Let $T$ be the uniform spanning tree on $G$. $T$ always contains the $n$ dangling edges connected to $v$, as well as $m$ spanning trees $S_j$ of the $H_j$, which are iid copies of the uniform spanning tree on $H$.

Clearly $\mathbb{E} S_T(v) = n - m \mathbb{E} D_S(w) \approx n - mr/2$. If $n < mr/2$, then this is negative.

On the other hand, $$ \frac{S_T(v)}{D_T(v)} = \frac{n - \sum_{j=1}^m D_{S_j}(w_j)}{n + \sum_{j=1}^m D_{S_j}(w_j)} $$ This is positive if $\frac{n}{m} > \frac{1}{m} \sum_{j=1}^m D_{S_j}(w_j)$. If $m$ is small enough, and the distribution of $D_S(w)$ is skewed enough, that this average still has a decently sized left tail, then it may be possible to have $\mathbb{E} \frac{S_T(v)}{D_T(v)} > 0$. Achieving this by balancing the parameters $m,n$ and the distribution of $D_S(w)$ has so far eluded me.