stringtranslate.com

El problema de la fábrica de ladrillos de Turán

Problema sin resolver en matemáticas :
¿Es posible dibujar un grafo bipartito completo con menos cruces que el número dado por Zarankiewicz?
Un dibujo óptimo de K 4,7 , con 18 cruces (puntos rojos)

En las matemáticas del dibujo de grafos , el problema de la fábrica de ladrillos de Turán pide el número mínimo de cruces en un dibujo de un grafo bipartito completo . El problema recibe su nombre de Pál Turán , quien lo formuló mientras se veía obligado a trabajar en una fábrica de ladrillos durante la Segunda Guerra Mundial. [1]

Se ha conjeturado que un método de dibujo descubierto por Kazimierz Zarankiewicz da la respuesta correcta para cada grafo bipartito completo, y la afirmación de que esto es cierto se conoce como la conjetura del número de cruce de Zarankiewicz . La conjetura permanece abierta, con solo algunos casos especiales resueltos. [2]

Origen y formulación

Durante la Segunda Guerra Mundial , el matemático húngaro Pál Turán se vio obligado a trabajar en una fábrica de ladrillos, empujando vagones llenos de ladrillos desde los hornos hasta los lugares de almacenamiento. La fábrica tenía vías que unían cada horno con cada lugar de almacenamiento, y era más difícil empujar los vagones en los puntos donde las vías se cruzaban. Turán se inspiró en esta situación para preguntarse cómo se podría rediseñar la fábrica para minimizar el número de cruces entre estas vías. [1]

Matemáticamente, este problema se puede formalizar como pedir un dibujo gráfico de un grafo bipartito completo , cuyos vértices representan hornos y lugares de almacenamiento, y cuyos bordes representan las vías desde cada horno hasta cada lugar de almacenamiento. El grafo debe dibujarse en el plano con cada vértice como un punto, cada borde como una curva que conecta sus dos puntos finales y ningún vértice colocado sobre un borde al que no sea incidente. Se cuenta un cruce siempre que dos bordes que están disjuntos en el grafo tienen una intersección no vacía en el plano. La pregunta es entonces, ¿cuál es el número mínimo de cruces en un dibujo de este tipo? [2] [3]

La formulación de Turán de este problema es a menudo reconocida como uno de los primeros estudios de los números cruzados de grafos . [4] (Otra formulación independiente del mismo concepto ocurrió en sociología, en métodos para dibujar sociogramas , [5] y un rompecabezas mucho más antiguo, el problema de las tres utilidades , puede verse como un caso especial del problema de la fábrica de ladrillos con tres hornos y tres instalaciones de almacenamiento. [6] ) Los números cruzados han ganado desde entonces mayor importancia, como un objeto central de estudio en el dibujo de grafos [7] y como una herramienta importante en el diseño VLSI [8] y la geometría discreta . [9]

Límite superior

Tanto Zarankiewicz como Kazimierz Urbanik vieron a Turán hablar sobre el problema de la fábrica de ladrillos en diferentes charlas en Polonia en 1952, [3] y publicaron de forma independiente intentos de solución del problema, con fórmulas equivalentes para el número de cruces. [10] [11] Como ambos demostraron, siempre es posible dibujar el grafo bipartito completo K m,n (un grafo con m vértices en un lado, n vértices en el otro lado y mn aristas que conectan los dos lados) con un número de cruces igual a

La construcción es sencilla: se colocan m vértices en el eje x del plano, evitando el origen , con un número igual o casi igual de puntos a la izquierda y a la derecha del eje y . De manera similar, se colocan n vértices en el eje y del plano, evitando el origen, con un número igual o casi igual de puntos por encima y por debajo del eje x . Luego, se conecta cada punto del eje x mediante un segmento de línea recta a cada punto del eje y . [3]

Sin embargo, sus pruebas de que esta fórmula es óptima, es decir, que no puede haber dibujos con menos cruces, eran erróneas. La brecha no fue descubierta hasta once años después de su publicación, casi simultáneamente por Gerhard Ringel y Paul Kainen . [12] Sin embargo, se conjetura que la fórmula de Zarankiewicz y Urbanik es óptima. Esto ha llegado a conocerse como la conjetura del número de cruces de Zarankiewicz. Aunque se sabe que algunos casos especiales de ella son ciertos, el caso general permanece abierto. [2]

Límites inferiores

Como K m,n y K n,m son isomorfos, basta considerar el caso en que m ≤ n . Además, para m ≤ 2 la construcción de Zarankiewicz no da cruces, lo que por supuesto no se puede superar. Por lo tanto, los únicos casos no triviales son aquellos para los que m y n son ambos ≥ 3 .

El intento de Zarankiewicz de demostrar la conjetura, aunque no es válida para el caso general de K m , n , funciona para el caso m = 3 . Desde entonces se ha extendido a otros valores pequeños de m , y se sabe que la conjetura de Zarankiewicz es verdadera para los grafos bipartitos completos K m,n con m ≤ 6 . [13] También se sabe que la conjetura es verdadera para K 7,7 , K 7,8 y K 7,9 . [14] Si existe un contraejemplo, es decir, un grafo K m,n que requiere menos cruces que el límite de Zarankiewicz, entonces en el contraejemplo más pequeño tanto m como n deben ser impares. [13]

Para cada elección fija de m , la verdad de la conjetura para todo K m,n puede verificarse probando solo un número finito de elecciones de n . [15] De manera más general, se ha demostrado que cada grafo bipartito completo requiere un número de cruces que es (para grafos suficientemente grandes) al menos el 83% del número dado por el límite de Zarankiewicz. Cerrar la brecha entre este límite inferior y el límite superior sigue siendo un problema abierto. [16]

Números de cruces rectilíneos

Si se requiere que los bordes se dibujen como segmentos de línea recta, en lugar de curvas arbitrarias, entonces algunos grafos necesitan más cruces de los que necesitarían si se dibujaran con bordes curvos. Sin embargo, el límite superior establecido por Zarankiewicz para el número de cruces de grafos bipartitos completos se puede lograr utilizando solo bordes rectos. Por lo tanto, si la conjetura de Zarankiewicz es correcta, entonces los grafos bipartitos completos tienen un número de cruces rectilíneos igual a su número de cruces. [17]

Referencias

  1. ^ ab Turán, P. (1977), "Una nota de bienvenida", Journal of Graph Theory , 1 : 7–9, doi :10.1002/jgt.3190010105.
  2. ^ abc Pach, János ; Sharir, Micha (2009), "5.1 Cruces: el problema de la fábrica de ladrillos", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures , Mathematical Surveys and Monographs, vol. 152, American Mathematical Society , págs. 126–127.
  3. ^ abc Beineke, Lowell ; Wilson, Robin (2010), "La historia temprana del problema de la fábrica de ladrillos", The Mathematical Intelligencer , 32 (2): 41–48, doi :10.1007/s00283-009-9120-4, MR  2657999, S2CID  122588849.
  4. ^ Foulds, LR (1992), Aplicaciones de la teoría de grafos, Universitext, Springer, pág. 71, ISBN 9781461209331.
  5. ^ Bronfenbrenner, Urie (1944), "La presentación gráfica de datos sociométricos", Sociometry , 7 (3): 283–289, doi :10.2307/2785096, JSTOR  2785096, La disposición de los sujetos en el diagrama, aunque en parte aleatoria, está determinada en gran medida por ensayo y error con el objetivo de minimizar el número de líneas que se cruzan.
  6. ^ Bóna, Miklós (2011), Un recorrido por la combinatoria: una introducción a la enumeración y la teoría de grafos , World Scientific, págs. 275-277, ISBN 9789814335232Bóna presenta el rompecabezas (en forma de tres casas que se conectan a tres pozos) en la pág. 275, y escribe en la pág. 277 que "es equivalente al problema de dibujar K 3,3 en una superficie plana sin cruces".
  7. ^ Schaefer, Marcus (2014), "El número de cruce de grafos y sus variantes: una encuesta", The Electronic Journal of Combinatorics : #DS21
  8. ^ Leighton, T. (1983), Problemas de complejidad en VLSI , Foundations of Computing Series, Cambridge, MA: MIT Press
  9. ^ Székely, LA (1997), "Números cruzados y problemas de Erdős difíciles en geometría discreta", Combinatorics, Probability and Computing , 6 (3): 353–358, CiteSeerX 10.1.1.134.9842 , doi :10.1017/S0963548397002976, MR  1464571, S2CID  36602807 
  10. ^ Zarankiewicz, K. (1954), "Sobre un problema de P. Turan sobre gráficos", Fundamenta Mathematicae , 41 : 137–145, doi : 10.4064/fm-41-1-137-145 , MR  0063641.
  11. ^ Urbaník, K. (1955), "Solution du problème posé par P. Turán", Colloq. Matemáticas. , 3 : 200–201. Citado por Székely, László A. (2001) [1994], "Conjetura del número de cruce de Zarankiewicz", Enciclopedia de Matemáticas , EMS Press
  12. ^ Guy, Richard K. (1969), "La decadencia y caída del teorema de Zarankiewicz", Técnicas de prueba en teoría de grafos (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) , Academic Press, Nueva York, págs. 63-69, MR  0253931.
  13. ^ ab Kleitman, Daniel J. (1970), "El número de cruce de K 5, n ", Journal of Combinatorial Theory , 9 (4): 315–323, doi : 10.1016/s0021-9800(70)80087-4 , MR  0280403.
  14. ^ Woodall, DR (1993), "Gráficos de orden cíclico y conjetura de números cruzados de Zarankiewicz", Journal of Graph Theory , 17 (6): 657–671, doi :10.1002/jgt.3190170602, MR  1244681.
  15. ^ Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), "La conjetura de Zarankiewicz es finita para cada m fijo ", Journal of Combinatorial Theory , Serie B, 103 (2): 237–247, doi : 10.1016/j.jctb.2012.11.001 , MR  3018068.
  16. ^ de Klerk, E.; Maharry, J.; Pasechnik, DV; Richter, RB; Salazar, G. (2006), "Límites mejorados para los números de cruce de K m, n y K n ", SIAM Journal on Discrete Mathematics , 20 (1): 189–202, arXiv : math/0404142 , doi :10.1137/S0895480104442741, MR  2257255, S2CID  1509054.
  17. ^ Kainen, Paul C. (1968), "Sobre un problema de P. Erdős", Journal of Combinatorial Theory , 5 (4): 374–377, doi : 10.1016/s0021-9800(68)80013-4 , MR  0231744

Enlaces externos