Conjetura de Hadwiger (geometría combinatoria) - Hadwiger conjecture (combinatorial geometry)
¿Puede cada cuerpo convexo dimensional estar cubierto por copias más pequeñas de sí mismo?
En geometría combinatoria , la conjetura de Hadwiger establece que cualquier cuerpo convexo en el espacio euclidiano n- dimensional puede estar cubierto por 2 n o menos cuerpos más pequeños homotéticos con el cuerpo original, y que además, el límite superior de 2 n es necesario si y solo si el cuerpo es un paralelepípedo . También existe una formulación equivalente en términos de la cantidad de focos necesarios para iluminar la carrocería.
La conjetura de Hadwiger lleva el nombre de Hugo Hadwiger , quien la incluyó en una lista de problemas no resueltos en 1957; sin embargo, fue estudiado previamente por Levi (1955) e independientemente, Gohberg y Markus (1960) . Además, hay una conjetura de Hadwiger diferente con respecto a la coloración del gráfico, y en algunas fuentes la conjetura geométrica de Hadwiger también se denomina conjetura de Levi-Hadwiger o problema de cobertura de Hadwiger-Levi .
La conjetura permanece sin resolver incluso en tres dimensiones, aunque el caso bidimensional fue resuelto por Levi (1955) .
Declaración formal
Formalmente, la conjetura de Hadwiger es: Si K es cualquier conjunto convexo acotado en el espacio euclidiano n- dimensional R n , entonces existe un conjunto de 2 n escalares s i y un conjunto de 2 n vectores de traslación v i tal que todos s i se encuentran en el rango 0 < s i <1, y
Además, el límite superior es necesario si K es un paralelepípedo, en cuyo caso los 2 n de los escalares pueden elegirse para que sean iguales a 1/2.
Fórmula alternativa con iluminación
Como lo muestra Boltyansky , el problema es equivalente a uno de iluminación: ¿cuántos proyectores deben colocarse fuera de un cuerpo convexo opaco para iluminar completamente su exterior? Para los propósitos de este problema, un cuerpo solo se considera iluminado si para cada punto del límite del cuerpo, hay al menos un reflector que está separado del cuerpo por todos los planos tangentes que cruzan el cuerpo en este punto. ; así, aunque las caras de un cubo pueden estar iluminadas únicamente por dos focos, los planos tangentes a sus vértices y aristas hacen que necesite muchas más luces para que esté completamente iluminado. Para cualquier cuerpo convexo, el número de focos necesarios para iluminarlo por completo resulta ser igual al número de copias más pequeñas del cuerpo que se necesitan para cubrirlo.
Ejemplos de
Como se muestra en la ilustración, un triángulo puede estar cubierto por tres copias más pequeñas de sí mismo y, más generalmente, en cualquier dimensión, un simplex puede estar cubierto por n + 1 copias de sí mismo, escaladas por un factor de n / ( n + 1). Sin embargo, cubrir un cuadrado con cuadrados más pequeños (con lados paralelos al original) requiere cuatro cuadrados más pequeños, ya que cada uno puede cubrir solo una de las cuatro esquinas del cuadrado más grande. En dimensiones superiores, cubrir un hipercubo o más generalmente un paralelepípedo con copias homotéticas más pequeñas de la misma forma requiere una copia separada para cada uno de los vértices del hipercubo o paralelepípedo original; debido a que estas formas tienen 2 n vértices, se necesitan 2 n copias más pequeñas. Este número también es suficiente: un cubo o paralelepípedo puede estar cubierto por 2 n copias, escaladas por un factor de 1/2. La conjetura de Hadwiger es que los paralelepípedos son el peor caso para este problema, y que cualquier otro cuerpo convexo puede estar cubierto por menos de 2 n copias más pequeñas de sí mismo.
Resultados conocidos
El caso bidimensional fue resuelto por Levi (1955) : cada conjunto bidimensional convexo acotado puede cubrirse con cuatro copias más pequeñas de sí mismo, siendo la cuarta copia necesaria sólo en el caso de paralelogramos. Sin embargo, la conjetura permanece abierta en dimensiones superiores salvo algunos casos especiales. El límite superior asintótico más conocido del número de copias más pequeñas necesarias para cubrir un cuerpo determinado es
Para los pequeños, el límite superior de establecido por Lassak (1988) es mejor que el asintótico. En tres dimensiones se sabe que siempre bastan 16 ejemplares, pero esto todavía está lejos de la encuadernación conjeturada de 8 ejemplares.
Se sabe que la conjetura es válida para ciertas clases especiales de cuerpos convexos, incluidos poliedros simétricos y cuerpos de ancho constante en tres dimensiones. El número de copias necesarias para cubrir cualquier zonotopo es como máximo , mientras que para los cuerpos con una superficie lisa (es decir, que tienen un solo plano tangente por punto límite), se necesitan como máximo copias más pequeñas para cubrir el cuerpo, como ya demostró Levi .
Ver también
- La conjetura de Borsuk sobre la cobertura de cuerpos convexos con conjuntos de menor diámetro.
Notas
Referencias
- Boltjansky, V .; Gohberg, Israel (1985), "11. Conjetura de Hadwiger", Resultados y problemas en geometría combinatoria , Cambridge University Press , págs. 44–46.
- Latón, Peter; Moser, William; Pach, János (2005), "3.3 Problema de cobertura e iluminación de Levi-Hadwiger", Problemas de investigación en geometría discreta , Springer-Verlag, págs. 136-142.
- Gohberg, Israel Ts. ; Markus, Alexander S. (1960), "Un cierto problema sobre el recubrimiento de conjuntos convexos con homotéticos", Izvestiya Moldavskogo Filiala Akademii Nauk SSSR (en ruso), 10 (76): 87–90.
- Hadwiger, Hugo (1957), "Ungelöste Probleme Nr. 20", Elemente der Mathematik , 12 : 121.
- Lassak, Marek (1988), "Covering the boundary of a convexo set by tiles", Proceedings of the American Mathematical Society , 104 (1): 269-272, doi : 10.1090 / s0002-9939-1988-0958081-7 , MR 0958081.
- Levi, Friedrich Wilhelm (1955), "Überdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns", Archiv der Mathematik , 6 (5): 369–370, doi : 10.1007 / BF01900507 , S2CID 121459171.