-1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ -1 Is this really a research-level question? $\endgroup$ – user541686 Jun 8 '15 at 7:40
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Or more precisely $\approx 2^n/\sqrt{n}$. $\endgroup$ – Sariel Har-Peled Jun 8 '15 at 4:07
  • $\begingroup$ 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}\}$. $\endgroup$ – Star Jun 8 '15 at 7:45
  • $\begingroup$ 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. $\endgroup$ – Tim Jun 8 '15 at 13:03
  • $\begingroup$ 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]$. $\endgroup$ – Star Jun 8 '15 at 15:05
  • 1
    $\begingroup$ 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? $\endgroup$ – David Eppstein Jun 8 '15 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.