<p>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 <a href="https://en.wikipedia.org/wiki/Hypersimplex">hypersimplices</a>. 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.</p>

CC BY-SA 3.0
2015-06-08T04:07:19.027Z
Or more precisely $\approx 2^n/\sqrt{n}$.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-08T07:45:28.990Z
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
CC BY-SA 3.0
2015-06-08T13:03:59.013Z
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
CC BY-SA 3.0
2015-06-08T15:05:10.903Z
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
CC BY-SA 3.0
2015-06-08T15:42:04.290Z
Specifically, to achieve the $k$-level hypersimplex, set $a_i=0$ and $b_i=1/k$.
David Eppstein
CC BY-SA 3.0
2015-06-08T16:04:06.827Z
@ David: Sorry, but I cannot understand the relation of this argument to my posed problem.
Star
CC BY-SA 3.0
2015-06-08T19:17:28.290Z
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
CC BY-SA 3.0
2015-06-07T23:11:06.340Z
2015-06-07T23:11:06.340Z
David Eppstein
<p>Consider the polytope</p>

<p>$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\}$ </p>

<p>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)$?</p>

CC BY-SA 3.0
2015-06-08T07:40:32.857Z
-1 Is this really a research-level question?
user541686
<cc.complexity-theory><linear-algebra><linear-programming><computational-geometry><polytope>
Vertices of a polytope
Star
# Vertices of a polytope

(Asked by: username_0 on 2015-06-07)

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)$?

**Tags:** cc.complexity-theory, linear-algebra, linear-programming, computational-geometry, polytope

> **Comments:**
> **username_1**: -1 Is this really a research-level question?  

---

## 1 answers

### Answer by username_2 on 2015-06-07. Score: 8

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](https://en.wikipedia.org/wiki/Hypersimplex). 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.

> **Comments:**
> **username_3**: Or more precisely $\approx 2^n/\sqrt{n}$.  
> **username_0**: 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}\}$.  
> **username_4**: 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.  
> **username_0**: 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]$.  
> **username_2**: Specifically, to achieve the $k$-level hypersimplex, set $a_i=0$ and $b_i=1/k$.  
> **username_0**: @ David: Sorry, but I cannot understand the relation of this argument to my posed problem.  
> **username_2**: 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?  

---

