Politopo convexo muy simétrico

Question

Dejemos que $C_n$ sea el politopo convexo en ${\mathbb R}^n$ definido por las desigualdades (en $n$ variables $x_1,x_2, \ldots ,x_n$ ) :

$$x_i \geq 0, x_i+x_j \leq 1$$ (para cualquier índice $i<j$ ).

Denota por $E_n$ el conjunto de puntos extremos de $C_n$ . Tenemos una acción natural del grupo simétrico $G={\mathfrak S}_n$ en $C_n$ y, por tanto, en $E_n$ también. Así que tenemos un conjunto cociente $\frac{E_n}{G}$ . Aquí hay algunas preguntas sobre el tema, en orden decreciente de dificultad :

1) Es una simple descripción de $\frac{E_n}{G}$ ¿se conoce en general?

2) ¿Cuál es el comportamiento asintótico de la secuencia $(|\frac{E_n}{G}|)_{n \geq 2}$ ?

3) ¿Es la secuencia $(|\frac{E_n}{G}|)_{n \geq 2}$ ¿acotado?

Answer 1

Tal vez esté exagerando algo, pero me parece que los puntos extremos de $C_n$ son de tres tipos. (1) El vector cero. (2) Los vectores unitarios estándar, con un $1$ en un solo componente y ceros en el otro $n-1$ componentes. (3) Vectores con la entrada $1/2$ en algún conjunto de tres o más componentes y ceros en los componentes restantes. Si eso es correcto, entonces hay un $G$ -órbita para (1), otra para (2), y $n-2$ órbitas para (3). Cada órbita para (3) se caracteriza por la cardinalidad, entre $3$ y $n$ inclusive, del conjunto de coordenadas donde $1/2$ se produce.

Answer 2

Aquí hay una prueba de que la descripción completa sugerida en la respuesta de Andreas Blass es correcta.

Está claro que todos los puntos enumerados son efectivamente extremos. A la inversa, dejemos que $v=(x_1,x_2,x_3, \ldots ,x_n)$ sea un punto extremo en $C_n$ . Podemos suponer wlog que $x_1\geq x_2 \geq x_3 \geq \ldots x_n$ .

Si $x_1=0$ , $v$ es el vector cero : es el caso (1).

Por lo tanto, podemos suponer $x_1 \gt 0$ . Sea $r$ sea el mayor índice que satisfaga $x_r \gt 0$ .

Si $r\geq 3$ , dejemos que $p_r$ sea el vector con el $r$ las primeras coordenadas son iguales a $\frac{1}{2}$ y todas las demás iguales a $0$ . Entonces $v$ es una combinación convexa del vector cero y $p_r$ . Desde $v$ es extremo, deducimos $v=p_r$ : este es el caso (3).

Si $r=2$ entonces $v$ es una combinación convexa de los dos primeros vectores de la base canónica canónica. Dado que $v$ es extrema, $v$ debe ser uno de esos dos: este es el caso (2).

Por último, si $r=1$ entonces $v$ es una combinación convexa del vector cero y del primer vector de la base canónica. Dado que $v$ es extrema, $v$ debe ser una de esas dos, y estamos en el caso (1) o (2).