# Very symmetric convex polytope

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.

• 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. – 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).

• 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. – Kundor Apr 9 '14 at 2:21