Problema de Zarankevich

El problema de Zarankevich  es un problema de teoría de grafos relacionado con encontrar el número mínimo de intersecciones al representar un gráfico bipartito completo en un plano . [una]

También conocido como el problema de la fábrica de ladrillos de Turan , en honor al matemático húngaro Pal Turan , quien formuló este problema mientras trabajaba en una fábrica de ladrillos durante la Segunda Guerra Mundial .  

El matemático polaco Kazimierz Zarankiewicz ( Polaco Kazimierz Zarankiewicz ) conjeturó que alguna imagen gráfica simple tiene un número mínimo de intersecciones, sin embargo, salvo casos especiales, su optimalidad sigue sin demostrarse [2] .

Origen y redacció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, donde transportaba carretas de ladrillos desde los hornos hasta los almacenes. En la fábrica, las vías del tren se colocaban entre cualquier horno y cualquier almacén , y era más difícil empujar el carro donde se cruzaban estas vías. Esto inspiró a Turan a preguntar cómo se podrían reorganizar los caminos para minimizar el número de intersecciones. [una]

Desde el punto de vista de las matemáticas, esta es la tarea de representar un gráfico en un plano : hornos y almacenes definen los vértices del gráfico, y las vías del tren definen sus bordes. Dado que hay exactamente un camino entre cada horno y cada almacén, dicho gráfico es un bipartito completo . Si hay p hornos y s almacenes, ese gráfico se denota por . El problema de Turan consiste en disponer los vértices y las aristas de un grafo en el plano de tal manera que ningún vértice se encuentre en una arista de la que no sea el final, y al mismo tiempo las aristas del grafo tengan un número mínimo de intersecciones. aparte de los vértices. En este caso, las aristas no tienen por qué ser rectilíneas , aunque en la solución, que se supone mínima, sí lo es. [2]

El problema de Turan se considera uno de los primeros problemas sobre el número mínimo de intersecciones de grafos . [3] Un caso especial es el problema matemático clásico " Casas y pozos ", en el que el papel de hornos y almacenes lo desempeñan casas y pozos, cada uno - tres piezas.

Intentos de solución

Zarankiewicz y Kazimierz Urbanik ( polaco: Kazimierz Urbanik ) asistieron a las conferencias de Turan en Polonia en 1952 [4] y publicaron de forma independiente intentos de resolver el problema. [5]

En ambos casos, propusieron dibujar un gráfico bipartito completo de la siguiente manera (ver la imagen al principio del artículo): dibujar vértices de un color (“hornos”) a lo largo del eje vertical, vértices de otro color (“almacenes”) a lo largo del eje horizontal, y el punto de intersección de los ejes elegir de manera que en cada lado haya vértices iguales (si hay vértices pares de un color dado ) o casi iguales (si son impares). Como resultado, ambos recibieron el siguiente número de intersecciones para los bordes del gráfico:

Este ejemplo da un límite superior al número de intersecciones, pero ambas pruebas de su minimalidad, dando un límite inferior, resultaron ser incorrectas: fueron refutadas por Gerhard Ringel y Paul Kainen casi simultáneamente, en 1965 [6] 

Aunque en el caso general la cuestión de la minimalidad sigue siendo una conjetura, se han demostrado con éxito casos especiales: el caso del propio Zarankevich, y más tarde con . [7] Dado que para dos p, s cualesquiera, la prueba de minimalidad requiere un número finito de comprobaciones, se llevó a cabo para p, s suficientemente pequeños. [8] También se demostró que el número mínimo de intersecciones es al menos el 83% de la estimación de Zarankiewicz. [9]

Notas

  1. ↑ 1 2 Turan, P. (1977), Una nota de bienvenida , Journal of Graph Theory vol.1 : 7–9 , doi 10.1002/jgt.3190010105  .
  2. ↑ 1 2 Pach, Janos & Sharir, Micha (2009), 5.1 Cruces: el problema de la fábrica de ladrillos, la geometría combinatoria y sus aplicaciones algorítmicas: The Alcala Lectures , vol. 152, Mathematical Surveys and Monographs, American Mathematical Society , p. 126–127  .
  3. ↑ Foulds, LR (1992), Aplicaciones de la teoría de grafos , Universitex, Springer, p. 71, ISBN 9781461209331 , < https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA71 > Archivado el 12 de julio de 2022 en Wayback Machine . 
  4. ↑ Beineke, Lowell & Wilson, Robin (2010), La historia temprana del problema de la fábrica de ladrillos , The Mathematical Intelligencer Vol. 32 (2): 41–48 , DOI 10.1007/s00283-009-9120-4  .
  5. ↑ Urbanik, K. (1955), Solution du probleme pose par P. Turan, Colloq. Matemáticas. T. 3: 200–201  . Citado por Szekely, Laszlo A. (2001), Zarankiewicz cruce la conjetura del número , en Hazewinkel, Michiel, Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4 
  6. ↑ Guy, Richard K. (1969), The declive and fall of Zarankiewicz's theorem, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) , Academic Press, Nueva York, pág. . . 63–69  .
  7. ↑ Kleitman, Daniel J. (1970), El número de cruce de K 5, n , Journal of Combinatorial Theory vol.9: 315–323 , DOI 10.1016/s0021-9800(70)80087-4  .
  8. ↑ Cristiano, Robin; Richter, R. Bruce & Salazar, Gelasio (2013), la conjetura de Zarankiewicz es finita para cada m fijo , Journal of Combinatorial Theory , Serie B Vol. 103 (2): 237–247 , DOI 10.1016/j.jctb.2012.11.001  .
  9. ↑ de Klerk, E.; Maharry, J.; Pasechnik, DV y Richter, RB (2006), Límites mejorados para los números cruzados de K m,n y Kn , SIAM Journal on Discrete Mathematics Vol. 20 (1): 189–202 , DOI 10.1137/S0895480104442741  .

Enlaces