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

Observations: I think this concentration result might be helpful. Let $X_1, X_2, \ldots, X_{z}$ be the Bernoulli random variables corresponding to any subset of $z$ edges of $E$ with $2\le z\le |E|$ where, for each $i\in\{1,2,\ldots, z\}$, we have $X_i=1$ iff the $i$-th edge of such subset of $E$ is included in $E_T$. Note that $\{X_i\}_{i=1}^{z}$ are negatively correlated as well as the random variables $\{1-X_i\}_{i=1}^{z}$. Let $p_i$ be the parameter of $X_i$, and $p:=\frac{1}{z}\sum_{i=1}^{z}p_i$. Using a Chernoff's bound for negatively correlated random variables we have $$\mathbb{P}\left(\sum_{i=1}^{z} X_i<pz-\lambda\right)\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,,$$ and therefore we also have $$\mathbb{P}\left(\sum_{i=1}^{z} X_i>pz+\lambda\right)\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,.$$

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

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

Observations: I think this concentration result might be helpful. Let $X_1, X_2, \ldots, X_{z}$ be the Bernoulli random variables corresponding to any subset of edges of $E$ with $2\le z\le |E|$ where, for each $i\in\{1,2,\ldots, z\}$, we have $X_i=1$ iff the $i$-th edge of such subset of $E$ is included in $E_T$. Note that $\{X_i\}_{i=1}^{z}$ are negatively correlated as well as the random variables $\{1-X_i\}_{i=1}^{z}$. Let $p_i$ be the parameter of $X_i$, and $p:=\frac{1}{z}\sum_{i=1}^{z}p_i$. Using a Chernoff's bound for negatively correlated random variables we have $$\mathbb{P}\left[\sum_{i=1}^{z} X_i<pz-\lambda\right]\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,,$$ and therefore we also have $$\mathbb{P}\left[\sum_{i=1}^{z} X_i>pz+\lambda\right]\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,.$$

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

Observations: I think this concentration result might be helpful. Let $X_1, X_2, \ldots, X_{z}$ be the Bernoulli random variables corresponding to any subset of $z$ edges of $E$ with $2\le z\le |E|$ where, for each $i\in\{1,2,\ldots, z\}$, we have $X_i=1$ iff the $i$-th edge of such subset of $E$ is included in $E_T$. Note that $\{X_i\}_{i=1}^{z}$ are negatively correlated as well as the random variables $\{1-X_i\}_{i=1}^{z}$. Let $p_i$ be the parameter of $X_i$, and $p:=\frac{1}{z}\sum_{i=1}^{z}p_i$. Using a Chernoff's bound for negatively correlated random variables we have $$\mathbb{P}\left(\sum_{i=1}^{z} X_i<pz-\lambda\right)\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,,$$ and therefore we also have $$\mathbb{P}\left(\sum_{i=1}^{z} X_i>pz+\lambda\right)\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,.$$

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

Observations: I think this concentration result might be helpful. Let $X_1, X_2, \ldots, X_{z}$ be the Bernoulli random variables corresponding to any subset of edges of $E$ with $2\le z\le |E|$ where, for each $i\in\{1,2,\ldots, z\}$, we have $X_i=1$ iff the $i$-th edge of such subset of $E$ is included in $E_T$. Note that $\{X_i\}_{i=1}^{z}$ are negatively correlated as well as the random variables $\{1-X_i\}_{i=1}^{z}$. Let $p:=\frac{1}{z}\sum_{i=1}^{z}p_i$. Using a Chernoff's bound for negatively correlated random variables we have $$\mathbb{P}\left[\sum_{i=1}^{z} X_i<pz-\lambda\right]\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,,$$ and therefore we also have $$\mathbb{P}\left[\sum_{i=1}^{z} X_i>pz+\lambda\right]\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,.$$

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

Observations: I think this concentration result might be helpful. Let $X_1, X_2, \ldots, X_{z}$ be the Bernoulli random variables corresponding to any subset of edges of $E$ with $2\le z\le |E|$ where, for each $i\in\{1,2,\ldots, z\}$, we have $X_i=1$ iff the $i$-th edge of such subset of $E$ is included in $E_T$. Note that $\{X_i\}_{i=1}^{z}$ are negatively correlated as well as the random variables $\{1-X_i\}_{i=1}^{z}$. Let $p_i$ be the parameter of $X_i$, and $p:=\frac{1}{z}\sum_{i=1}^{z}p_i$. Using a Chernoff's bound for negatively correlated random variables we have $$\mathbb{P}\left[\sum_{i=1}^{z} X_i<pz-\lambda\right]\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,,$$ and therefore we also have $$\mathbb{P}\left[\sum_{i=1}^{z} X_i>pz+\lambda\right]\le\exp\left(-\frac{\lambda^2}{2pz}\right)\,.$$