# Vertices of a polytope

Consider the polytope

$P=\{(x_1,x_2,...,x_n)\in \mathbb{R}^n| \sum_{i=1}^n x_i=1; 0\leq a_i\leq x_i\leq b_i, i=1,...,n\}$

where $a_i$ and $b_i$ are constant lower and upper bounds for $x_i$. Is it true that the number of extreme points of $P$ is $O(n)$?

• -1 Is this really a research-level question? – user541686 Jun 8 '15 at 7:40

No. Suppose all $a_i$'s are $0$ and all your $b_i$'s are equal; then the polytopes you can get by varying the $b_i$'s are essentially the hypersimplices. But the number of vertices of an $n$-dimensional hypersimplex can be any binomial coefficient $\binom{n}{k}$. In particular choosing $k=n/2$ gives an exponential number of extreme points.
• Or more precisely $\approx 2^n/\sqrt{n}$. – Sariel Har-Peled Jun 8 '15 at 4:07
• I think this is not the case for the polytope $P$ because of the constraint $\sum_{i=1}^n x_i=1$. Another way of looking at $P$ is to consider it as intersection of $\{(x_1,x_2,...,x_n)\in \mathbb{R}^n| 0\leq a_i\leq x_i\leq b_i)\}\cap \{{(x_1,x_2,...,x_n)\in \mathbb{R}_{\geq 0}^n|\sum_{i=1}^n x_i=1}\}$. – Star Jun 8 '15 at 7:45
• The constraint $\sum_{i=1}^n x_i=1$ defines the hypersimplex, which is then intersected with a hypercube with corners $a$ and $b$. This intersection only makes the polytope more complex. Taking $a_i=0$ and $b_i=1$ for all $i$ gives the original hypersimplex. – Tim Jun 8 '15 at 13:03
• A hypersimplex is defined as $H(n,k) = \{(x_1,x_2,...,x_n) \in [0,1]^n | \sum_{i=1}^n x_i =k \}$. The number of extreme points of $H(n,k)$ is $C(n,k)$. Thus, if you put $k=1$, then the number of extreme points would be $n$. Now, my defined polytope is a special case of H(n,1) in which $x_i \in [a_i,b_i]\subseteq [0,1]$. – Star Jun 8 '15 at 15:05
• Set each $a_i=0$ and each $b_i=1/k$, giving you a small cube (scaled by a $1/k$ factor from the unit cube). Then the hyperplane $\sum x_i=1$ will pass through $\binom{n}{k}$ vertices of this small cube (the ones with exactly $k$ nonzero coordinates), and the section of the small cube by this hyperplane will be a convex hull of this set of vertices, which will be of exponential size for $k\approx n/2$. What part of that is unclear? – David Eppstein Jun 8 '15 at 19:17