6
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ The function $f$ is fixed when taking the expectation? $\endgroup$
    – Sophie M
    Apr 18, 2023 at 3:00
  • 1
    $\begingroup$ Also -- do you expect this to be true or false, i.e. do you expect a proof or a counterexample? Where did it come from? $\endgroup$
    – Sophie M
    Apr 18, 2023 at 3:19
  • 3
    $\begingroup$ I believe that the graph with root $v$ to which you attach 3 triangles with vertices (other than $v$) labeled $1$ and two very long loops with vertices labeled $-1$ is a counterexample. Check it! $\endgroup$
    – fedja
    Apr 20, 2023 at 1:43
  • 1
    $\begingroup$ @fedja Beautiful! That's quite similar to what I was trying in my answer below, but the analysis of your graph is a lot simpler! $\endgroup$
    – Sophie M
    Apr 24, 2023 at 19:44
  • 2
    $\begingroup$ @SophieMacDonald Yeah. The key words were actually those by Penelope: " I expect it can be false only when the both the first and the second factor (and therefore their product) are very close to $0$", so I just took a graph for which one expectation was exactly $0$ (a star with $4$ edges instead of two long loops), checked that the other one was negative, and then shifted the zero expectation up a tiny bit without altering the distributions too much. $\endgroup$
    – fedja
    Apr 26, 2023 at 2:07

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for sharing your ideas! Do you think the concentration result I justadded is compatible with the distribution you are trying to define for $D_S(w)$? $\endgroup$ Apr 18, 2023 at 20:18
  • 1
    $\begingroup$ No, probably not! That seems like a good way to prove that what I'm outlining here can't work. $\endgroup$
    – Sophie M
    Apr 19, 2023 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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