¿Se puede dibujar un gráfico bipartito completo con menos cruces que el número dado por Zarankiewicz?
En las matemáticas del dibujo de gráficos , el problema de la fábrica de ladrillos de Turán pide el número mínimo de cruces en un dibujo de un gráfico bipartito completo . El problema lleva el 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 encontrado por Kazimierz Zarankiewicz da la respuesta correcta para cada gráfico 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 carretas llenas de ladrillos de los hornos a los lugares de almacenamiento. La fábrica tenía pistas de cada horno a cada sitio de almacenamiento, y los vagones eran más difíciles de empujar en los puntos donde las pistas 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 pidiendo un dibujo gráfico de un gráfico bipartito completo , cuyos vértices representan hornos y sitios de almacenamiento, y cuyos bordes representan las pistas de cada horno a cada sitio de almacenamiento. El gráfico 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 en un borde al que no incide. Se cuenta un cruce siempre que dos bordes que están separados en el gráfico 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 tal dibujo? [2] [3]
La formulación de Turán de este problema a menudo se reconoce como uno de los primeros estudios sobre el cruce de números de gráficos . [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] ) Desde entonces, los números de cruce han ganado mayor importancia, como objeto central de estudio en el dibujo de gráficos [7] y como una herramienta importante en el diseño VLSI [8] y 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 conversaciones 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 mostraron ambos, siempre es posible dibujar el gráfico bipartito completo K m, n (un gráfico con m vértices en un lado, n vértices en el otro lado y mn bordes que conectan los dos lados ) con un número de cruces igual a
La construcción es simple: coloque m vértices en el eje x del plano, evitando el origen , con números iguales o casi iguales de puntos a la izquierda y derecha del eje y . De manera similar, coloque 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, 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, fueron erróneas. La brecha no se descubrió hasta once años después de la 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 se conoce como la conjetura del número de cruce de Zarankiewicz. Aunque se sabe que algunos casos especiales son ciertos, el caso general permanece abierto. [2]
Límites inferiores
Dado que K m, n y K n, m son isomorfos, basta con considerar el caso en el que m ≤ n . Además, para m ≤ 2, la construcción de Zarankiewicz no ofrece cruces, lo que, por supuesto, no puede superarse. Así los casos solamente no triviales son aquellos para los que m y n son ambos ≥ 3 .
El intento de prueba de Zarankiewicz de la conjetura, aunque no es válido 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 cierta para los gráficos bipartitos completos K m, n con m ≤ 6 . [13] También se sabe que la conjetura es cierta para K 7,7 , K 7,8 y K 7,9 . [14] Si existe un contraejemplo, es decir, un gráfico K m, n que requiere menos pasos que la Zarankiewicz obligado, a continuación, en el más pequeño contraejemplo ambos m y n debe ser impar. [13]
Para cada elección fija de m , la verdad de la conjetura para todos los K m, n puede verificarse probando sólo un número finito de elecciones de n . [15] De manera más general, se ha demostrado que todo gráfico bipartito completo requiere un número de cruces que es (para gráficos 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. [dieciséis]
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 gráficos necesitan más cruces de los que necesitarían cuando se dibujan con bordes curvos. Sin embargo, el límite superior establecido por Zarankiewicz para los números de cruce de gráficos bipartitos completos se puede lograr utilizando solo bordes rectos. Por lo tanto, si la conjetura de Zarankiewicz es correcta, entonces los gráficos bipartitos completos tienen números de cruce rectilíneos iguales a sus números de cruce. [17]
Referencias
- ↑ a b Turán, P. (1977), "Una nota de bienvenida", Journal of Graph Theory , 1 : 7-9, doi : 10.1002 / jgt.3190010105.
- ^ a b c Pach, János ; Sharir, Micha (2009), "5.1 Cruces: el problema de la fábrica de ladrillos", Geometría combinatoria y sus aplicaciones algorítmicas: las conferencias de Alcalá , estudios y monografías de matemáticas, 152 , American Mathematical Society , págs. 126-127.
- ^ a b c Beineke, Lowell ; Wilson, Robin (2010), "The early history of the brick factory problem", The Mathematical Intelligencer , 32 (2): 41–48, doi : 10.1007 / s00283-009-9120-4 , MR 2657999 , S2CID 122588849.
- ^ Foulds, LR (1992), Aplicaciones de la teoría de grafos , Universitext, Springer, p. 71, ISBN 9781461209331.
- ^ 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 desordenada, es determinado en gran parte por prueba y error con el objetivo de minimizar el número de líneas que se cruzan.
- ^ Bóna, Miklós (2011), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory , World Scientific, págs. 275–277, ISBN 9789814335232. Bóna presenta el rompecabezas (en forma de tres casas que se conectarán a tres pozos) en la p. 275, y escribe en la p. 277 que "equivale al problema de dibujar K 3,3 en una superficie plana sin cruces".
- ^ Schaefer, Marcus (2014), "El número de cruce del gráfico y sus variantes: una encuesta", The Electronic Journal of Combinatorics : # DS21
- ^ Leighton, T. (1983), Problemas de complejidad en VLSI , Foundations of Computing Series, Cambridge, MA: MIT Press
- ^ Székely, LA (1997), "Números cruzados y problemas difíciles de Erd en geometría discreta", Combinatoria, Probabilidad y Computación , 6 (3): 353–358, doi : 10.1017 / S0963548397002976 , MR 1464571
- ^ Zarankiewicz, K. (1954), "Sobre un problema de P. Turan sobre gráficas", Fundamenta Mathematicae , 41 : 137-145, doi : 10.4064 / fm-41-1-137-145 , MR 0063641.
- ^ 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" , Encyclopedia of Mathematics , EMS Press
- ^ Guy, Richard K. (1969), "El declive y la caída del teorema de Zarankiewicz", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) , Academic Press, Nueva York, págs. 63–69, MR 0253931.
- ^ a b Kleitman, Daniel J. (1970), "El número de cruce de K 5, n ", Journal of Combinatorial Theory , 9 : 315–323, doi : 10.1016 / s0021-9800 (70) 80087-4 , MR 0280403.
- ^ Woodall, DR (1993), "Gráficos de orden cíclico y conjetura del número de cruce de Zarankiewicz", Journal of Graph Theory , 17 (6): 657–671, doi : 10.1002 / jgt.3190170602 , MR 1244681.
- ^ 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.
- ^ 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 2.257.255 , S2CID 1509054.
- ^ 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
- Weisstein, Eric W. , "Conjetura de Zarankiewicz" , MathWorld