Conjetura de Hadwiger (geometría combinatoria)

Problema sin resolver en matemáticas

¿Puede todo cuerpo convexo de -dimensiones ser 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 afirma que cualquier cuerpo convexo en el espacio euclidiano n -dimensional puede ser cubierto por 2n ^o menos cuerpos más pequeños homotéticos con el cuerpo original, y que, además, el límite superior de 2n ^es necesario si y solo si el cuerpo es un paralelepípedo . También existe una formulación equivalente en términos del número de reflectores necesarios para iluminar el cuerpo.

La conjetura de Hadwiger recibe su nombre de Hugo Hadwiger , quien la incluyó en una lista de problemas sin resolver en 1957; sin embargo, ya había sido estudiada previamente por Levi (1955) e independientemente por Gohberg y Markus (1960) . Además, existe otra conjetura de Hadwiger relacionada con la coloración de grafos , y en algunas fuentes la conjetura geométrica de Hadwiger también se denomina conjetura de Levi-Hadwiger o problema de recubrimiento de Hadwiger-Levi .

La conjetura sigue sin resolverse incluso en tres dimensiones, aunque el caso bidimensional fue resuelto por Levi (1955) .

Formalmente, la conjetura de Hadwiger es: Si K es cualquier conjunto convexo acotado en el espacio euclidiano n -dimensional R ⁿ , entonces existe un conjunto de 2 ⁿ escalares s _i y un conjunto de 2 ⁿ vectores de traslación v _i tales que todos los 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 todos los 2 ⁿ de los escalares pueden elegirse iguales a 1/2.

Como demostró Boltyansky , el problema es equivalente a uno de iluminación : ¿cuántos reflectores deben colocarse fuera de un cuerpo convexo opaco para iluminar completamente su exterior? Para los fines de este problema, un cuerpo se considera iluminado solo si, para cada punto de su contorno, hay al menos un reflector separado del cuerpo por todos los planos tangentes que lo intersecan en ese punto; por lo tanto, aunque las caras de un cubo pueden estar iluminadas por solo dos reflectores, 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 reflectores necesarios para iluminarlo completamente resulta ser igual al número de copias más pequeñas del cuerpo que se necesitan para cubrirlo. ^{[ 1 ]}

Como se muestra en la ilustración, un triángulo puede cubrirse con tres copias más pequeñas de sí mismo, y, de forma más general, en cualquier dimensión, un simplex puede cubrirse con 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 solo puede cubrir una de las cuatro esquinas del cuadrado más grande. En dimensiones superiores, cubrir un hipercubo o, de forma más general, 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; dado que estas figuras tienen 2 ⁿ vértices, se necesitan 2 ⁿ copias más pequeñas. Este número también es suficiente: un cubo o paralelepípedo puede cubrirse con 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 cubrirse con menos de 2 ⁿ copias más pequeñas de sí mismo. ^{[ 1 ]}

El caso bidimensional fue resuelto por Levi (1955) : todo conjunto convexo acotado bidimensional puede cubrirse con cuatro copias más pequeñas de sí mismo, siendo necesaria la cuarta copia solo en el caso de paralelogramos. Sin embargo, la conjetura permanece abierta en dimensiones superiores, salvo en algunos casos especiales. La cota superior asintótica más conocida sobre el número de copias más pequeñas necesarias para cubrir un cuerpo dado es ^{[ 2 ]} donde es una constante positiva. Para valores pequeños de , la cota superior de establecida por Lassak (1988) es mejor que la asintótica. En tres dimensiones , Papadoperakis (1999) demostró que 16 copias siempre son suficientes, y posteriormente Prymak (2023) demostró que 14 copias también lo son, pero esto aún está lejos de la cota conjeturada de 8 copias. ^{[ 1 ]}$${\displaystyle \displaystyle 4^{n}\exp {\frac {-cn}{\log ^{8}n}},}$$${\displaystyle c}$${\displaystyle n}$${\displaystyle (n+1)n^{n-1}-(n-1)(n-2)^{n-1}}$

Se sabe que la conjetura se cumple para ciertas clases especiales de cuerpos convexos, incluyendo, en dimensión tres, poliedros con simetría central 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 único plano tangente por punto de contorno), se necesitan como máximo copias más pequeñas para cubrir el cuerpo, como ya demostró Levi . ^{[ 1 ]}${\displaystyle (3/4)2^{n}}$${\displaystyle n+1}$

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

• Boltjansky, Vladimir G.; Gohberg , Israel (1985). «11. La conjetura de Hadwiger». Resultados y problemas en geometría combinatoria . Cambridge: Cambridge University Press . págs.  44-46 . ISBN 978-0-521-26923-0..
• Brass, Peter; Moser, William; Pach, János (2005). «3.3 Problema de recubrimiento de Levi-Hadwiger e iluminación». Problemas de investigación en geometría discreta . Springer-Verlag. pp.  136–142 . ISBN 978-0-387-23815-9..
• Campos, Marcelo; van Hintum, Peter; Morris, Robert ; Tiba, Marius (2023), "Hacia la conjetura de Hadwiger mediante el seccionamiento de Bourgain", International Mathematics Research Notices , 2024 (10): 8282–8295 , arXiv : 2206.11227 , doi : 10.1093/imrn/rnad198.
• Gohberg, Israel Ts. ; Markus, Alexander S. (1960), "Un cierto problema sobre el recubrimiento de conjuntos convexos con conjuntos 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 recubrimiento de Hadwiger mediante estimaciones de capa delgada", Journal of the European Mathematical Society , 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 con teselas", Actas de la Sociedad Matemática Americana , 104 (1): 269– 272, doi : 10.1090/s0002-9939-1988-0958081-7 , MR  0958081.
• Papadoperakis, Ioannis (1999), "Una estimación para el problema de iluminación del límite de un cuerpo convexo en ", Geometriae Dedicata , 75 (3): 275– 285, doi : 10.1023/A:1005056207406${\displaystyle E^{3}}$.
• Prymak, Andriy (2023), "Una nueva cota para el problema de recubrimiento de Hadwiger en ", SIAM Journal on Discrete Mathematics , 37 (1): 17– 24, doi : 10.1137/22M1490314${\displaystyle \mathbb {E} ^{3}}$.
• 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.