I am trying to understand the Lovasz-Simonovits Theorem for random walks from this scribe note. For a graph $G$ with $2m$ edges, we have some edge measure $\rho$ and we order the edges according to this edge measure, i.e $\rho(e_1)\geq \cdots\geq \rho(e_{2m})$. Define the Lovasz-Simonovits curve $I:[0,2m]\rightarrow[0,1]$ as follows
For an integer $k\in[0,2m]$, $I(k) = \sum_{i=1}^k\rho(e_i)$.
If $x\in(k,k+1)$, where $k \in \mathbb{Z}\cap[0,2m]$, then $I(x)$ is the linear interpolation between points $(k,I(k))$ and(k+1,I(k+1)), meaning $I(x) = (k+1-x)I(k) + (x-k)I(k+1)$.
This piecewise linear curve is concave and has many interesting properties. One of them is
For any integer $j\in[0,2m]$ and weights $0\leq c_1\leq\cdots\leq c_j\leq 1$, we have $\sum_{i=1}^j c_i\rho(e_i) \leq I(\sum_{i=1}^j c_i)$.
This is Lemma 1 of the scribe note. As the note suggested, the LHS can only increase if we shift some weights to the left, since the edge measures are non-increasing. Hence the sum is maximum if we put as many 1's to the left.
Let $c=\sum_{i=1}^j c_i$ be the sum of weights. Define the new weights $w_1,\cdots,w_{j^\prime}$ where $w_1=\cdots = w_{j^\prime -1} = 1$ and $w_{j^\prime} = c-j^\prime+1$ so that the sum is still $c$. Evidently $j^\prime\leq j$. We have
$\sum_{i=1}^j c_i\rho(e_i) \leq \sum_{i=1}^{j^\prime} w_i\rho(e_i) = \sum_{i=1}^{j^\prime-1} \rho(e_i) + (c-j^\prime+1)\rho(e_{j^\prime})$.
Now I am unable to relate the RHS of the last expression with $I(\sum_{i=1}^j c_i)$. Can anyone please help?
Thanks.
Silly me, I figured out the solution as I was writing the question. As before let $c$ is the sum of the weights. Let $c\in(k,k+1)$ for some integer $k$. As discussed in the question, we can put $k$ 1s and put a weight of (c-k) to edge $e_{k+1}$. Noting that $\rho(e_{k+1}) = I(k+1)-I(k)$, we have