En matemáticas, la conjetura de Gilbert-Pollak es una conjetura no demostrada sobre la relación de las longitudes de los árboles de Steiner y los árboles de expansión mínima euclidianos para los mismos conjuntos de puntos en el plano euclidiano . Fue propuesta por Edgar Gilbert y Henry O. Pollak en 1968. [1]
Para un conjunto de puntos en el plano, la red más corta de segmentos de línea que conecta los puntos, teniendo solo los puntos dados como puntos finales, es el árbol de expansión mínimo euclidiano del conjunto. Puede ser posible construir una red más corta utilizando puntos finales adicionales, no presentes en el conjunto de puntos dado. Estos puntos adicionales se denominan puntos de Steiner y la red más corta que se puede construir utilizándolos se denomina árbol mínimo de Steiner . El coeficiente de Steiner es el supremo , sobre todos los conjuntos de puntos, del cociente de las longitudes del árbol de expansión mínimo euclidiano con el árbol mínimo de Steiner. Debido a que el árbol mínimo de Steiner es más corto, este cociente siempre es mayor que uno. [2]
Un límite inferior del coeficiente de Steiner lo proporcionan tres puntos en los vértices de un triángulo equilátero de longitud de lado unidad. Para estos tres puntos, el árbol de expansión mínima euclidiana utiliza dos aristas del triángulo, con una longitud total de dos. El árbol mínimo de Steiner conecta los tres puntos con un punto de Steiner en el centroide del triángulo, con la longitud total más pequeña . Debido a este ejemplo, el coeficiente de Steiner debe ser al menos . [2]
La conjetura de Gilbert-Pollak establece que este ejemplo es el peor caso para el coeficiente de Steiner, y que este coeficiente es igual a . Es decir, para cada punto finito establecido en el plano euclidiano, el árbol de expansión mínimo euclidiano no puede ser más largo que 10 veces la longitud del árbol mínimo de Steiner. [2]
La conjetura es famosa por su prueba por Ding-Zhu Du y Frank Kwang-Ming Hwang, [3] [2] que más tarde resultó tener una grave laguna. [4] [5]
Basándose en el resultado erróneo de Du y Hwang, J. Hyam Rubinstein y Jia F. Weng concluyeron que el coeficiente de Steiner también es para una esfera bidimensional de curvatura constante , [6] pero debido a la brecha en el resultado base de Du y Hwang, el resultado de Rubinstein y Weng ahora también se considera como no probado todavía. [7]
