Let $C_n$ be the convex polytope in ${\mathbb R}^n$ defined by the inequalities (in $n$ variables $x_1,x_2, \ldots ,x_n$) :

$$ x_i \geq 0, x_i+x_j \leq 1 $$ (for any indices $i<j$).

Denote by $E_n$ the set of extremal points of $C_n$. We have a natural action of the symmetric group $G={\mathfrak S}_n$ on $C_n$, and hence on $E_n$ also. So we have a quotient set $\frac{E_n}{G}$. Here are some questions about it, in decreasing order of difficulty :

1) Is a simple description of $\frac{E_n}{G}$ known in general ?

2) What is the asymptotic behaviour of the sequence $(|\frac{E_n}{G}|)_{n \geq 2}$ ?

3) Is the sequence $(|\frac{E_n}{G}|)_{n \geq 2}$ bounded ?


Perhaps I'm overloooking something, but it seems to me that the extreme points of $C_n$ are of three sorts. (1) The zero vector. (2) The standard unit vectors, with a $1$ in a single component and zeros in the other $n-1$ components. (3) Vectors with the entry $1/2$ in some set of three or more components and zeros in the remaining components. If that's right, then there are a single $G$-orbit for (1), another for (2), and $n-2$ orbits for (3). Each orbit for (3) is characterized by the cardinality, between $3$ and $n$ inclusive, of the set of coordinates where $1/2$ occurs.

  • $\begingroup$ I don’t know yet if your guess is true, but its very content suggests some ways as to how to prove (or disprove) it. I’ll think about it. $\endgroup$ – Ewan Delanoy Jun 5 '13 at 19:31

Here is a proof that the complete description suggested in Andreas Blass' answer is indeed correct.

It is clear that all the points listed are indeed extremal. Conversely, let $v=(x_1,x_2,x_3, \ldots ,x_n)$ be an extremal point in $C_n$. We may assume wlog that $x_1\geq x_2 \geq x_3 \geq \ldots x_n$.

If $x_1=0$, $v$ is the zero vector : this is case (1).

We can therefore assume $x_1 \gt 0$. Let $r$ be the largest index satisfying $x_r \gt 0$.

If $r\geq 3$, let $p_r$ be the vector with the $r$ first coordinates are equal to $\frac{1}{2}$ and all the others equal to $0$. Then $v$ is a convex combination of the zero vector and $p_r$. Since $v$ is extremal, we deduce $v=p_r$ : this is case (3).

If $r=2$, then $v$ is a convex combination of the first two vectors of the canonical basis. Since $v$ is extremal, $v$ must be one of those two : this is case (2).

Finally, if $r=1$, then $v$ is a convex combination of the zero vector and the first vector of the canonical basis. Since $v$ is extremal, $v$ must be one of those two, and we are in case (1) or (2).

  • $\begingroup$ It seems there should be some argument for the $r \geq 3$ case for why a point like $v = (.7, .3, .3, \dotsc)$ can't be extremal. $\endgroup$ – Kundor Apr 9 '14 at 2:21

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.