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.

  • $\begingroup$ What is $\delta(v)$? Is it the set of vertices adjacent to $v$? $\endgroup$ – Steve Huntsman Aug 25 '15 at 14:17
  • $\begingroup$ Yes, the neighbors of $v$. $\endgroup$ – Marek Adamczyk Aug 25 '15 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$ – Fedor Petrov Aug 25 '15 at 15:06
  • $\begingroup$ Good point, can it be combined with the argument below? $\endgroup$ – Marek Adamczyk Aug 25 '15 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$ – Fedor Petrov Aug 25 '15 at 17:24

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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