4
$\begingroup$

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v \gamma_v = k$ some integer value. For every vertex $v$ there is also a number $a_v\in [0,1]$. That's the structural setup.

Now, for every $\lambda > 0$ we want to prove the following inequality: $$\frac{1}{k}\sum_v \gamma_v\cdot e^{-(e^\lambda-1)(a_v\gamma_v+\sum_{u\in \delta(v)}a_u\gamma_u)+\lambda a_v} \leq 1.$$ It has a probabilistic interpretation, if you find it helpful: we pick randomly a vertex proportionally to $\gamma_v$ we pick a value $a_v$ then, and remove $a_u\gamma_u$ from every neighbor of $v$, we then look at the expected value of exponentiated change.

The inequality is true, when the graph is a clique and $k=\sum_v \gamma_v=1$. Then we can take advantage of the fact that for every $v$ we have $a_v\gamma_v+\sum_{u\in \delta(v)}a_u\gamma_u = \sum_v a_v\gamma_v$ always the same. In this case the proof goes as follows: \begin{align} \sum_{\gamma_{v}}\gamma_{v}e^{\lambda a_{v}} &\leq \sum_{\gamma_{v}}\gamma_{v}(a_v(e^{\lambda }-1)+1)\\ &= \sum_{\gamma_{v}}\gamma_{v}a_v(e^{\lambda }-1)+1 \\ &\leq e^{\sum_{\gamma_{v}}\gamma_{v}a_v(e^{\lambda }-1)}, \end{align} where we used first $e^{a\lambda}-1 \leq a(e^\lambda -1)$, and then $1+x\leq e^x$ plus $\sum_v \gamma_v=1$. I believe that in the general case it should still be true, but the approach from the simple case doesn't carry over that easily. Any help in proving the inequality will be much appreciated.

$\endgroup$
9
  • $\begingroup$ What is $\delta(v)$? Is it the set of vertices adjacent to $v$? $\endgroup$ Aug 25, 2015 at 14:17
  • $\begingroup$ Yes, the neighbors of $v$. $\endgroup$ Aug 25, 2015 at 14:22
  • 1
    $\begingroup$ LHS is convex in any of variables $a_v$, hence it suffices to take $a_v\in \{0,1\}$ $\endgroup$ Aug 25, 2015 at 15:06
  • $\begingroup$ Good point, can it be combined with the argument below? $\endgroup$ Aug 25, 2015 at 15:11
  • $\begingroup$ Maybe, it makes sense to estimate $\gamma e^{\lambda a}\leq \gamma-1+e^{\gamma a (e^{\lambda}-1)}$ in each summand. At least it becomes more pretty, though maybe false. $\endgroup$ Aug 25, 2015 at 17:24

1 Answer 1

1
$\begingroup$

I have some nice lines, which I think can be pushed to a full proof.

We shall show that $$\sum_v \gamma_v\cdot e^{-(e^\lambda-1)(a_v\gamma_v+\sum_{u\in \delta(v)}a_u\gamma_u)+\lambda a_v} =: f((a_v)_{v\in V})$$ is maximized when all $a$'s are $0$, in which case it's equal to $1$. Denote $$ \Delta_v := e^{-(e^\lambda-1)(a_v\gamma_v+\sum_{u\in \delta(v)}a_u\gamma_u)+\lambda a_v} $$ The partial derivative over $a_v$ is equal to \begin{align} \frac{d f}{d a_v} =&\ \gamma_v \cdot \left(-\gamma_v(e^\lambda -1) + \lambda \right) \cdot e^{-(e^\lambda-1)(a_v\gamma_v+\sum_{u\in \delta(v)}a_u\gamma_u)+\lambda a_v} \\&\ + \sum_{u\in \delta(v)} \gamma_u \cdot (-\gamma_v(e^\lambda -1))\cdot e^{-(e^\lambda-1)(a_u\gamma_u+\sum_{w\in \delta(u)}a_w\gamma_w)+\lambda a_u}\\ =&\ \gamma_v \cdot \left(-\gamma_v(e^\lambda -1) + \lambda \right) \cdot \Delta_v + \sum_{u\in \delta(v)} \gamma_u \cdot (-\gamma_v(e^\lambda -1))\cdot \Delta_u \end{align} Now we want to show that for some $v$, the partial derivative is negative, i.e., for some $v$ we have $$ \left(\gamma_v(e^\lambda -1) - \lambda \right) \cdot \Delta_v + \sum_{u\in \delta(v)} \gamma_u \cdot (e^\lambda -1)\cdot \Delta_u \geq 0\\ \leftrightarrow \\ \gamma_v \cdot \Delta_v + \sum_{u\in \delta(v)} \gamma_u \cdot \Delta_u \geq \frac{\lambda}{e^\lambda -1} \Delta_v \qquad (*) $$ Assume that none of $a_v$ is equal to $0$. Multiply $(*)$ by $\gamma_v$, and sum them up together, then the LHS sums up to \begin{align} &\ \sum_v \gamma_v\cdot \left(\gamma_v \cdot \Delta_v + \sum_{u\in \delta(v)} \gamma_u \cdot \Delta_u \right)\\ =&\ \sum_v \gamma_v\cdot \Delta_v (\gamma_v+\sum_{u\in \delta(v)}\gamma_u)\\ =&\ \sum_v \gamma_v\cdot \Delta_v. \end{align} Now the RHS of $(*)$ sums up to $\frac{\lambda}{e^\lambda -1}\sum_v \gamma_v\cdot \Delta_v < \sum_v \gamma_v\cdot \Delta_v$, and so there has to exist $v$ for which $(*)$ is satisfied.

Once we would account for the fact that some $a_v$-s can be $0$, and prove that there exists such a $v$ for which $a_v>0$, then we could argue that the maximum is obtained when all $a_v$-s are $0$.

$\endgroup$

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.