Conjetura de Hadwiger (geometría combinatoria)

Un triángulo puede estar cubierto por tres copias más pequeñas de sí mismo; un cuadrado requiere cuatro copias más pequeñas

Problema no resuelto en matemáticas :

¿ Puede todo cuerpo convexo de dimensiones estar cubierto por copias más pequeñas de sí mismo? ${\displaystyle n}$ ${\displaystyle 2^{n}}$

(más problemas sin resolver en matemáticas)

En geometría combinatoria , la conjetura de Hadwiger establece que cualquier cuerpo convexo en el espacio euclidiano de n dimensiones puede estar cubierto por 2 ⁿ o menos cuerpos más pequeños homotéticos con el cuerpo original, y que además, el límite superior de 2 ⁿ es necesario si y sólo si el cuerpo es un paralelepípedo . También existe una formulación equivalente en términos del número de focos necesarios para iluminar el cuerpo.

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 por Gohberg y Markus (1960). Además, existe una conjetura de Hadwiger diferente sobre la coloración de gráficos , y en algunas fuentes la conjetura geométrica de Hadwiger también se llama conjetura de Levi-Hadwiger o problema de cobertura de Hadwiger-Levi .

La conjetura sigue sin resolverse 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 de n dimensiones R ⁿ , entonces existe un conjunto de 2 ⁿ escalares s _i y un conjunto de 2 ⁿ vectores de traducción vi _tales que todos s _i se encuentran en el rango 0 <  s _i  < 1, y

${\displaystyle K\subseteq \bigcup _{i=1}^{2^{n}}s_{i}K+v_{i}.}$

Además, el límite superior es necesario si y solo si K es un paralelepípedo, en cuyo caso se puede elegir que los 2 ⁿ de los escalares sean iguales a 1/2.

Formulación alternativa con iluminación.

Como 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 por sólo dos focos, los planos tangentes a sus vértices y aristas hacen que necesite muchas más luces para estar completamente iluminado. Para cualquier cuerpo convexo, el número de focos necesarios para iluminarlo completamente resulta igual al número de copias más pequeñas del cuerpo que se necesitan para cubrirlo. ^[1]

Ejemplos

Como se muestra en la ilustración, un triángulo puede estar cubierto por tres copias más pequeñas de sí mismo y, de manera más general, 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 ⁿ vértices, son necesarias 2 ^{n copias más pequeñas.} Este número también es suficiente: un cubo o un paralelepípedo puede estar cubierto por 2 ⁿ 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 ⁿ copias más pequeñas de sí mismo. ^[1]

Resultados conocidos

El caso bidimensional fue resuelto por Levi (1955): cada conjunto convexo acotado bidimensional puede cubrirse con cuatro copias más pequeñas de sí mismo, siendo necesaria la cuarta copia sólo en el caso de paralelogramos. Sin embargo, la conjetura permanece abierta en dimensiones superiores excepto en algunos casos especiales. El límite superior asintótico más conocido para el número de copias más pequeñas necesarias para cubrir un cuerpo determinado es ^[2]

${\displaystyle \displaystyle 4^{n}\exp \left({\frac {-cn}{\log(n)}}\right)}$

donde es una constante positiva. Para valores pequeños, el límite superior establecido por Lassak (1988) es mejor que el asintótico. En tres dimensiones se sabe que 16 copias siempre son suficientes, pero esto aún está lejos de la cifra conjeturada de 8 copias. ^[1] ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle (n+1)n^{n-1}-(n-1)(n-2)^{n-1}}$

Se sabe que la conjetura es válida para ciertas clases especiales de cuerpos convexos, incluidos, en dimensión tres, poliedros centralmente simétricos y cuerpos de ancho constante . ^[1] El número de copias necesarias para cubrir cualquier zonotopo (que no sea un paralelepípedo) es como máximo , mientras que para cuerpos con una superficie lisa (es decir, que tienen un solo plano tangente por punto límite), como máximo se necesitan copias más pequeñas para cubrir el cuerpo, como ya demostró Levi . ^[1] ${\displaystyle (3/4)2^{n}}$ ${\displaystyle n+1}$

Ver también

• La conjetura de Borsuk sobre cubrir cuerpos convexos con conjuntos de menor diámetro

Notas

1. Brass, Moser y Pach (2005).
2. Campos y col. (2023).

Referencias

• Boltjansky, V.; Gohberg, Israel (1985), "11. Conjetura de Hadwiger", Resultados y problemas de geometría combinatoria , Cambridge University Press , págs..
• Latón, Peter; Moser, William; Pach, János (2005), "3.3 Levi-Hadwiger Covering Problem and Illumination", Problemas de investigación en geometría discreta , Springer-Verlag, págs. 136-142.
• Campos, Marcelo; van Hintum, Peter; Morris, Robert ; Tiba, Marius (2023), "Hacia la conjetura de Hadwiger mediante el corte de Bourgain", Avisos internacionales de investigación en matemáticas , arXiv : 2206.11227 , doi :10.1093/imrn/rnad198.
• Gohberg, Israel Ts. ; Markus, Alexander S. (1960), "Un cierto problema sobre la cobertura 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.
• Huang, Han; Slomka, Boaz A.; Tkocz, Tomasz; Vritsiou, Beatrice-Helen (2022), "Límites mejorados para el problema de cobertura de Hadwiger mediante estimaciones de capa fina", Revista de la Sociedad Matemática Europea , 24 (4): 1431–1448, arXiv : 1811.12548 , doi : 10.4171/jems/1132 , ISSN  1435-9855.
• Lassak, Marek (1988), "Cubriendo el límite de un conjunto convexo mediante mosaicos", Actas de la Sociedad Matemática Estadounidense , 104 (1): 269–272, doi : 10.1090/s0002-9939-1988-0958081-7 , SEÑOR  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.