Inequality on permutation polytope

Question

Let $a = (a_1, \cdots, a_n), b = (b_1, \cdots, b_n), c = (c_1, \cdots, c_n) \in \mathbb{R}^n$ with $a_1 \geq \cdots \geq a_n, b_1 \geq \cdots \geq b_n, 0 < c_1 \leq \cdots \leq c_n$.

In addition, assume that $\sum_{i=1}^k b_i \leq \sum_{i=1}^k a_i$ for all $k \in \{1, \cdots, n-1\}$ and $\sum_{i=1}^n b_i = \sum_{i=1}^n a_i$.

Let $A := \{(a_{\sigma(1)}, \cdots, a_{\sigma(n)}) \,|\, \sigma \in S_n\}$ and $K_A$ be the unique minimal convex set containing $A$.

For $b \in K_A$, does $$\sum_{i=1}^n c_i b_i \geq \sum_{i=1}^n c_i a_i$$ hold?

Answer 1

Given two ordered vectors $a_1\geq a_2\geq \cdots \geq a_n$ and $b_1\geq b_2\geq \cdots b_n$ with equal sums $a_1+\cdots a_n=b_1+\cdots +b_n$. The condition that $b\in K_A$ and the inequalities $\sum_{i=1}^k a_i\geq \sum_{i=1}^k b_i$ are equivalent and this is called the majorization order.

A fundamental result is that if $a=(a_i)$ majorizes $b=(b_i)$ then you can obtain $b$ from $a$ by a finite sequence of operations of the form $$R_{ij}(\epsilon)(a)=(a_1,\dots,a_i-\epsilon,\dots,a_j+\epsilon,\dots,a_n)$$ for some $i<j$ and $\epsilon\geq 0$ is small enough not to reverse the order of the entries. That is, there exist several $(i_k,j_k,\epsilon_k)$ with $i_k<j_k$ and $\epsilon_k\geq 0$ such that $$b=\prod R_{i_kj_k}(\epsilon_k)a$$

Thus it suffices to prove your inequality for each step individually. So we can assume $b=R_{ij}(\epsilon)a$. In which case the inequality reduces to $$c_i (a_i-\epsilon)+c_j(a_j+\epsilon)\geq c_ia_i+c_ja_j$$ $$\iff \epsilon (c_j-c_i)\geq 0$$ and we are done.

Answer 2

Write $c_k=p_1+\cdots+p_k$ with $p_k=c_k-c_{k-1}\ge0$. Then $$\sum_ic_ib_i-\sum_ic_ia_i=\sum_kp_k(s_k(b)-s_k(a))$$ with $s_k(a)=a_k+\cdots+a_n$. By assumption, $s_k(b)-s_k(a)\ge0$ and you are gone.

This proof is just Abel's resummation, that is discrete integration by parts.