¿Cuántos vértices de un politopo se pueden cortar para producir una faceta k-vértice?

Question

Sea P una simple n-faceta d-polytope con la faceta de F, y sea F tiene k vértices. Deje que H sea un halfspace y Q ser un simple (n-1)-faceta polytope tal que H ∩ Q = P.

En términos de k, lo que es un límite superior en el número de vértices de P contenido en (ℝ^d \ H)? De manera informal: ¿cuál es el mayor número de vértices de P que puede ser cortada para producir un k-vértice faceta de F?

He deriva un algoritmo para calcular este valor exactamente en términos de la f-vector de F, pero me gustaría determinar un estrecho límite superior cuando el f-vector no está disponible.

Algunas observaciones: El conjunto de vértices no puede contener una faceta de Q, con lo que parece ser un límite en cuanto a su tamaño. k ≥ d, naturalmente, puesto que el corte de un solo vértice produce d vértices.

Si esta pregunta es particularmente difícil o contiene alguno de los problemas abiertos de la que no soy consciente, yo estaría interesado en saber que, también!

Answer 1

Dudo que esto es en cualquier lugar cerca de apretado, pero he aquí una prueba de que se está acotada. La nueva faceta tiene k vértices, de modo que por el teorema de límite superior se ha $O(k^{\lfloor (d-1)/2\rfloor})$ crestas. Cada faceta de la polytope a cortar es $F$ o una faceta a través de una de estas crestas, por lo que hay $O(k^{\lfloor (d-1)/2\rfloor})$ facetas de la corte polytope. Aplicar el límite superior teorema de nuevo, ha $O((k^{\lfloor (d-1)/2\rfloor})^{\lfloor d/2\rfloor})$ vértices.

Esto funciona sin la asunción de la simplicidad. Utilizando el hecho de que todos sus polytopes son simples puede conseguir en la mayoría k crestas directamente, y $O(k^{\lfloor d/2\rfloor})$ vértices, creo.

Answer 2

En tres dimensiones mirar el prisma de cuyos extremos son dos polígonos regulares con $k$ lados. Mira el plano de cerca de un extremo de forma paralela al plano que contiene un polígono regular que los recortes de los polígonos regulares. A continuación, que cumplan todas las condiciones del problema, excepto uno que se corta de una cara. El avión se puede girar a través de una línea de cerca de un vértice, de modo que se corta todos los vértices, excepto ese vértice. Entonces se cortó $k-1$ puntos y dejar todas las caras originales intactos. Tendrá $k+1$ vértices de Modo que en tres dimensiones, al menos, $k-1$ vértices pueden ser cortados por una faceta con $k+1$ vértices sin perder ninguna de las caras originales. Creo que esta técnica puede ser utilizada en las dimensiones superiores.

Si $v$ vértices está cortado por un plano que intersecta un poliedro en un polígono con $k$ lados con no se enfrenta a cortar, a continuación, la corte poliedro se han $k+1$ caras. Como David Eppstein ha observado en su respuesta a esta pregunta cada faceta de la polytope a cortar es $F$ el rostro formado por la corte hyperplane aquí un plano que corta el poliedro en un polígono con $k$ bordes en sí, o una faceta a través de una de estas crestas,por lo que en las dos dimensiones de este caso da $k+1$ caras.

Los bordes de conectar los vértices cortado se debe formar un árbol. No contienen ciclo o bien una cara sería cortado. Están conectados, ya que la eliminación de los bordes de una la cara del poliedro que sale de la gráfica de los bordes restantes conectado. Así que estos bordes forman un árbol.

Hemos bordes de la gráfica de un poliedro igual a la suma de las caras y la vértices-2. Sabemos que el número de vértices y caras en el poliedro de corte de en el avión. Los vértices se $v + k$, y $k+1$ caras. Así que debemos tener $v + 2k-1$ bordes hemos $k$ bordes formado por los vértices del polígono F y $v-1$ desde el árbol formado por los vértices cortado. La única posibilidad de la izquierda es los vértices entre el corte de los vértices y de los vértices de $F$. Desde cada punto de debe ser adyacente a tres bordes de cada punto del polígono debe tener un borde que toca a la corte de los vértices. No debe ser $v+2$ bordes además de la los bordes de los árboles para hacer cada corte de vértices adyacentes a exactamente tres bordes. por lo tanto $k$ bordes debe ser igual a $v+2$ bordes y $k=v+2$.

Así, en tres dimensiones de cada corte que no quita la cara y se cruza con un poliedro en $k$ vértices cortes de $k-2$ vértices. En las dimensiones superiores no estoy seguro de lo que sucede. Sé que hay ejemplos al $k$ vértices cortado $k-d$ vértices pero más allá de eso no estoy seguro.