inequality with exponents

Question

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.

Answer 1

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