In some paper the authors make use of the following inequality without further explanation: Let $x\in\mathbb{R}^n$ with $x\_1\le\cdots\le x\_n$ and $\alpha\in[0,1]^n$ with $\sum\_{i=1}^n \alpha\_i=N\in\{1,2,\ldots,n\}$. Then $$\sum\_{i=1}^n\alpha\_i x\_i\ge\sum\_{i=1}^N x\_i.$$


While I already have found a (quite lengthy) bare-hands-proof, I wonder if this inequality is just (some variant of) some commonly known inequality that I am just unaware of. Any hints?



Does anyone recognize this inequality?
(In a way this is a rephrasing of Iosif's answer, but from a different perspective. My main intention is to point out the connection to matroids.)


The inequality follows from: 


**Fact.** The polytope $K = \Bigl\{\alpha \in [0,1]^n: \sum\_{i = 1}^n\alpha\_i = N\Bigr\}$ is the convex hull of indicator vectors of subsets of $[n] = \{1, \ldots, n\}$ of size $N$. 


Assuming this fact, and because any linear function over a polytope achieves its minimum at a vertex, we have that $\sum\_{i = 1}^n{\alpha\_i x\_i} \ge \sum\_{i \in S} x\_i$ for some set $S$ of size $N$. The right hand side is then clearly minimized for $S = \{1, \ldots, N\}$ if $x\_1 \le x\_2 \le \ldots \le x\_n$.


To show the Fact, we need to show that every extreme point $\alpha$ of $K$ is an indicator vector of a set of size $N$. This is clearly true if $\alpha \in \{0,1\}^n$, so assume, towards contradiction, that for some $i$ we have $0 < \alpha\_i < 1$. Then there must be at least one other $j \neq i$ such that $0 < \alpha\_j < 1$, and we can write $\alpha$ as a convex combination of two vectors in $K$, one in which we add a tiny $h$ to $\alpha\_i$ and subtract $h$ from $\alpha\_j$, and one in which we reverse the signs. This means that $\alpha$ is not an extreme point, a contradiction. You can see that this argument is essentially the same as Iosif's.


Another way to state the Fact is that $K$ is the base polytope of the uniform matroid over $[n]$ of rank $N$. A vast generalization is the characterization of the facets of the base polytope of any matroid, due to Edmonds: see, e.g., Section 10.7 in [these notes](https://homepages.cwi.nl/~lex/files/dict.pdf).


