En matemáticas , un gráfico topológico es una representación de un gráfico en el plano , donde los vértices del gráfico están representados por puntos distintos y los bordes por arcos de Jordan (piezas conectadas de curvas de Jordan ) que unen los pares de puntos correspondientes. Los puntos que representan los vértices de un gráfico y los arcos que representan sus aristas se denominan vértices y aristas.del gráfico topológico. Por lo general, se asume que dos bordes cualesquiera de un gráfico topológico se cruzan un número finito de veces, ningún borde pasa a través de un vértice diferente de sus puntos finales y no hay dos bordes que se toquen entre sí (sin cruzarse). Un gráfico topológico también se denomina dibujo de un gráfico.
Una clase especial importante de gráficos topológicos es la clase de gráficos geométricos , donde los bordes están representados por segmentos de línea . (El término gráfico geométrico a veces se usa en un sentido más amplio y algo vago).
La teoría de grafos topológicos es un área de la teoría de grafos , que se ocupa principalmente de las propiedades combinatorias de los grafos topológicos, en particular, con los patrones de cruce de sus bordes. Está estrechamente relacionado con el dibujo de gráficos , un campo que está más orientado a las aplicaciones, y la teoría de gráficos topológicos , que se centra en incrustaciones de gráficos en superficies (es decir, dibujos sin cruces).
Problemas extremos para gráficos topológicos
Un problema fundamental en la teoría de grafos extremos es el siguiente: ¿cuál es el número máximo de aristas que puede tener un gráfico de n vértices si no contiene ningún subgrafo que pertenezca a una clase determinada de subgrafos prohibidos ? El prototipo de tales resultados es el teorema de Turán , donde hay un subgrafo prohibido: un gráfico completo con k vértices ( k es fijo). Pueden plantearse cuestiones análogas para los gráficos topológicos y geométricos, con la diferencia de que ahora están prohibidas determinadas subconfiguraciones geométricas .
Históricamente, la primera instancia de tal teorema se debe a Paul Erdős , quien extendió un resultado de Heinz Hopf y Erika Pannwitz . [2] Demostró que el número máximo de aristas que puede tener una gráfica geométrica con n > 2 vértices sin contener dos aristas disjuntas (que ni siquiera pueden compartir un punto final) es n . John Conway conjeturó que esta afirmación se puede generalizar a gráficos topológicos simples. Un gráfico topológico se denomina "simple" si cualquier par de sus bordes comparte como máximo un punto, que es un punto final o un punto interior común en el que los dos bordes se cruzan correctamente. La conjetura del thrackle de Conway ahora se puede reformular de la siguiente manera: Un gráfico topológico simple con n > 2 vértices y no hay dos bordes disjuntos tiene como máximo n bordes.
El primer límite superior lineal en el número de bordes de dicho gráfico fue establecido por Lovász et al. [3] El límite superior más conocido, 1.428 n , fue probado por Fulek y Pach . [4] Aparte de las gráficas geométricas, se sabe que la conjetura de la esclavitud de Conway es cierta para las gráficas topológicas x- monótonas. [5] Se dice que un gráfico topológico es x-monótono si cada línea vertical interseca cada borde en como máximo un punto.
Alon y Erdős [6] iniciaron la investigación de la generalización de la pregunta anterior al caso donde la configuración prohibida consiste en k bordes disjuntos ( k > 2). Demostraron que el número de aristas de una gráfica geométrica de n vértices, que no contiene 3 aristas disjuntas es O ( n ). El límite óptimo de aproximadamente 2,5 n fue determinado por Černý. [7] Para valores mayores de k , el primer límite superior lineal,, fue fundada por Pach y Töröcsik. [8] Esto fue mejorado por Tóth para. [9] Para el número de aristas de un gráfico topológico simple sin k aristas disjuntas, sólo unse conoce el límite superior. [10] Esto implica que cada grafo topológico simple completo con n vértices tiene al menos bordes cruzados por pares, que se mejoró para de Ruiz-Vargas. [11] Es posible que este límite inferior se pueda mejorar aún más a cn , donde c > 0 es una constante.
Gráficos cuasiplanar
Un punto interior común de dos bordes, en el que el primer borde pasa de un lado del segundo borde al otro, se denomina cruce . Dos bordes de un gráfico topológico se cruzan si determinan un cruce. Para cualquier número entero k > 1, una gráfica topológica o geométrica se llama k-cuasi-planar si no tiene k bordes cruzados por pares. Usando esta terminología, si un gráfico topológico es 2-cuasi-plano, entonces es un gráfico plano . De la fórmula poliédrica de Euler se deduce que cada grafo plano con n > 2 vértices tiene como máximo 3 n - 6 aristas. Por lo tanto, cada grafo de 2 cuasiplanar con n > 2 vértices tiene como máximo 3 n - 6 aristas.
Ha sido conjeturado por Pach et al. [12] que cada k -grafo topológico cuasiplanar con n vértices tiene como máximo c ( k ) n aristas, donde c ( k ) es una constante que depende solo de k . Se sabe que esta conjetura es cierta para k = 3 [13] [14] y k = 4. [15] También se sabe que es cierta para las gráficas geométricas convexas (es decir, para las gráficas geométricas cuyos vértices forman el conjunto de vértices de un convexo n -gon), [16] y para k -grafos topológicos cuasi-planar cuyas aristas se dibujan como x -curvas monotónicas, todas las cuales cruzan una línea vertical. [17] [18] El último resultado implica que cada k -grafo topológico cuasi-planar con n vértices, cuyas aristas se dibujan como x -curvas monotónicas tiene como máximo c ( k ) n log n aristas para una constante adecuada c ( k ). Para los gráficos geométricos, Valtr demostró esto anteriormente. [19] El límite superior general más conocido para el número de aristas de un grafo topológico k -cuasi-planar es. [20]
Números de cruce
Desde que Pál Turán acuñó su problema de fábrica de ladrillos [21] durante la Segunda Guerra Mundial , la determinación o estimación de números cruzados de gráficos ha sido un tema popular en la teoría de grafos y en la teoría de algoritmos. [22] Sin embargo, las publicaciones en el tema (explícita o implícitamente) utilizaron varias definiciones en competencia de números cruzados. Esto fue señalado por Pach y Tóth, [23] quienes introdujeron la siguiente terminología.
Número de cruce (de un gráfico G ): el número mínimo de puntos de cruce sobre todos los dibujos de G en el plano (es decir, todas sus representaciones como un gráfico topológico) con la propiedad de que no hay tres bordes que pasen por el mismo punto. Se denota por cr ( G ).
Número de pares de cruce : El número mínimo de cruzar pares de bordes sobre todos los dibujos de G . Se denota por par-cr ( G ).
Número impar de cruce : El número mínimo de dichos pares de bordes que se cruzan un número impar de veces, sobre todos los dibujos de G . Se denota con impar-cr ( G ).
Estos parámetros no son ajenos. Uno tiene impar-cr ( G ) ≤ par-cr ( G ) ≤ cr ( G ) para cada gráfica G . Se sabe que cr ( G ) ≤ 2 (impar-cr ( G )) 2 [23] y[24] y que existen infinitos gráficos para los cuales pair-cr ( G ) ≠ impar-cr ( G ). [1] No se conocen ejemplos en los que el número de cruce y el número de cruce de pares no sean el mismo. Se deduce del teorema de Hanani-Tutte [25] [26] que impar-cr ( G ) = 0 implica cr ( G ) = 0. También se sabe que impar-cr ( G ) = k implica cr (G) = k para k = 1, 2, 3. [27] Otro parámetro gráfico bien investigado es el siguiente.
Número de cruce rectilíneo : el número mínimo de puntos de cruce sobre todos los dibujos en línea recta de G en el plano (es decir, todas sus representaciones como un gráfico geométrico) con la propiedad de que no hay tres aristas que pasen por el mismo punto. Se denota por lin-cr ( G ).
Por definición, uno tiene cr ( G ) ≤ lin-cr ( G ) para cada gráfica G . Bienstock y Dean demostraron que hay gráficos con el número de cruce 4 y con un número de cruce rectilíneo arbitrariamente grande. [28]
Problemas tipo Ramsey para gráficas geométricas
En la teoría de grafos tradicional , un resultado típico de tipo Ramsey establece que si coloreamos los bordes de un gráfico completo suficientemente grande con un número fijo de colores, entonces necesariamente encontramos un subgrafo monocromático de cierto tipo. [29] Se pueden plantear preguntas similares para gráficos geométricos (o topológicos), excepto que ahora buscamos subestructuras monocromáticas (de un color) que satisfagan ciertas condiciones geométricas. [30] Uno de los primeros resultados de este tipo establece que cada gráfico geométrico completo cuyos bordes están coloreados con dos colores contiene un árbol de expansión monocromático que no se cruza . [31] También es cierto que cada gráfico geométrico contienebordes disjuntos del mismo color. [31] La existencia de una trayectoria monocromática que no se cruza de tamaño al menos cn , donde c > 0 es una constante, es un problema abierto desde hace mucho tiempo. Solo se sabe que cada grafo geométrico completo en n vértices contiene una trayectoria monocromática que no se cruza de longitud al menos. [32]
Hipergrafos topologicos
Si vemos un gráfico topológico como una realización topológica de un complejo simplicial unidimensional , es natural preguntarse cómo los problemas extremos y de tipo Ramsey anteriores se generalizan a realizaciones topológicas de complejos simpliciales d- dimensionales. Hay algunos resultados iniciales en esta dirección, pero se requiere más investigación para identificar las nociones y los problemas clave. [33] [34] [35]
Se dice que dos vértices simples disjuntos se cruzan si sus interiores relativos tienen un punto en común. Un conjunto de k > 3 simplices se cruza fuertemente si ninguno de ellos comparte un vértice, pero sus interiores relativos tienen un punto común.
Se sabe que un conjunto de simples d- dimensionales divididos por n puntos en sin un par de simplices cruzados puede tener como máximo simplices y este límite es asintóticamente estrecho. [36] Este resultado se generalizó a conjuntos de simples bidimensionales ensin tres simplices fuertemente cruzados. [37] Si prohibimos k cruces fuertes de simplices, el límite superior correspondiente más conocido es, [36] para algunos. Este resultado se deriva del teorema de Tverberg coloreado . [38] Está lejos del límite conjeturado de. [36]
Para cualquier k > 1 fijo , podemos seleccionar como máximo d -simplices dimensionales divididos por un conjunto de n puntos encon la propiedad de que hay k de ellos comparten un punto interior común. [36] [39] Esto es asintóticamente ajustado.
Dos triángulos en se dice que son casi inconexos si son inconexos o si comparten un solo vértice. Es un viejo problema de Gil Kalai y otros decidir si el mayor número de triángulos casi disjuntos que se pueden elegir en algún conjunto de vértices de n puntos en es . Se sabe que existen conjuntos de n puntos para los cuales este número es al menospara una constante adecuada c > 0. [40]
Referencias
- ↑ a b Pelsmajer, Michael J .; Schaefer, Marcus; Štefankovič, Daniel (2008), "El número de cruce impar y el número de cruce no son lo mismo", Geometría discreta y computacional , 39 (1–3): 442–454, doi : 10.1007 / s00454-008-9058-x Una versión preliminar de estos resultados fue revisada en Proc. of 13th International Symposium on Graph Drawing , 2005, págs. 386–396, doi : 10.1007 / 11618058_35.
- ^ Hopf, Heinz ; Pannwitz, Erika (1934), "Aufgabe nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung , 43 : 114
- ^ Lovász, László ; Pach, János ; Szegedy, Mario (1997), "Sobre la conjetura de la esclavitud de Conway", Geometría discreta y computacional , Springer, 18 (4): 369-376, doi : 10.1007 / PL00009322
- ^ Fulek, Radoslav; Pach, János (2011), "A computational approach to Conway's thrackle conjecture", Computational Geometry , 44 (6-7): 345-355, arXiv : 1002.3904 , doi : 10.1007 / 978-3-642-18469-7_21 , MR 2785903
- ^ Pach, János ; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly , 118 (6): 544–548, doi : 10.4169 / amer.math.monthly.118.06.544 , MR 2812285 , S2CID 17558559
- ^ Alon, Noga ; Erdős, Paul (1989), "Aristas disjuntas en gráficas geométricas" , Geometría discreta y computacional , 4 (4): 287-290, doi : 10.1007 / bf02187731
- ^ Černý, Jakub (2005), "Gráficos geométricos sin tres bordes separados ", Geometría discreta y computacional , 34 (4): 679–695, doi : 10.1007 / s00454-005-1191-1
- ^ Pach, János ; Töröcsik, Jenö (1994), "Algunas aplicaciones geométricas del teorema de Dilworth", Geometría discreta y computacional , 12 : 1–7, doi : 10.1007 / BF02574361
- ^ Tóth, Géza (2000), "Nota sobre gráficos geométricos", Journal of Combinatorial Theory , Serie A, 89 (1): 126-132, doi : 10.1006 / jcta.1999.3001
- ^ Pach, János ; Tóth, Géza (2003), "Bordes disjuntos en gráficos topológicos", Geometría combinatoria y teoría de grafos: Conferencia conjunta Indonesia-Japón, IJCCGGT 2003, Bandung, Indonesia, 13-16 de septiembre de 2003, Revised Selected Papers (PDF) , Lecture Notes en Ciencias de la Computación, 3330 , Springer-Verlag, págs. 133–140, doi : 10.1007 / 978-3-540-30540-8_15
- ^ J. Ruiz-Vargas, Andres (2015), Many disjoint edge in topological graphs , 50 , pp. 29-34, arXiv : 1412.3833 , doi : 10.1016 / j.endm.2015.07.006 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ Pach, János ; Shahrokhi, Farhad; Szegedy, Mario (1996), "Applications of the crossing number", Algorithmica , Springer, 16 (1): 111-117, doi : 10.1007 / BF02086610 , S2CID 20375896
- ^ Agarwal K., Pankaj ; Aronov, Boris ; Pach, János ; Pollack, Richard ; Sharir, Micha (1997), "Las gráficas cuasi-planas tienen un número lineal de aristas", Combinatorica , 17 : 1–9, doi : 10.1007 / bf01196127 , S2CID 8092013
- ^ Ackerman, Eyal; Tardos, Gábor (2007), "Sobre el número máximo de aristas en grafos cuasi-planar", Journal of Combinatorial Theory , Serie A, 114 (3): 563–571, doi : 10.1016 / j.jcta.2006.08.002
- ^ Ackerman, Eyal (2009), "Sobre el número máximo de aristas en gráficos topológicos sin cuatro aristas cruzadas por pares", Geometría discreta y computacional , 41 (3): 365–375, doi : 10.1007 / s00454-009-9143-9
- ^ Capoyleas, Vasilis; Pach, János (1992), "Un teorema tipo Turán sobre las cuerdas de un polígono convexo", Journal of Combinatorial Theory , Serie B, 56 (1): 9-15, doi : 10.1016 / 0095-8956 (92) 90003- GRAMO
- ^ Suk, Andrew (2011), " k -quasi-planar graphs", Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, Países Bajos, 21-23 de septiembre de 2011, Revised Selected Papers , Lecture Notes in Computer Science, 7034 , Springer-Verlag, págs. 266–277, arXiv : 1106.0958 , doi : 10.1007 / 978-3-642-25878-7_26 , S2CID 18681576
- ^ Fox, Jacob ; Pach, János ; Suk, Andrew (2013), "El número de aristas en k -gráficas cuasi-planas", SIAM Journal on Discrete Mathematics , 27 (1): 550–561, arXiv : 1112.2361 , doi : 10.1137 / 110858586 , S2CID 52317.
- ^ Valtr, Pavel (1997), "Dibujo de gráfico sin k bordes cruzados por pares", Dibujo de gráfico: 5to Simposio Internacional, GD '97 Roma, Italia, 18 al 20 de septiembre de 1997, Actas , Lecture Notes in Computer Science, 1353 , Springer -Verlag, págs. 205–218
- ^ Fox, Jacob; Pach, János (2012), "Colorear-Gráficos de intersección libres de objetos geométricos en el plano ", European Journal of Combinatorics , 33 (5): 853–866, doi : 10.1016 / j.ejc.2011.09.021 Una versión preliminar de estos resultados se anunció en Proc. del Simposio sobre geometría computacional (PDF) , 2008, págs. 346–354, doi : 10.1145 / 1377676.1377735 , S2CID 15138458
- ^ Turán, Paul (1977), "Una nota de bienvenida", Journal of Graph Theory , 1 : 7-9, doi : 10.1002 / jgt.3190010105
- ^ Garey, MR ; Johnson, DS (1983), "Crossing number is NP-complete", SIAM Journal on Algebraic and Discrete Methods , 4 (3): 312–316, doi : 10.1137 / 0604033 , MR 0711340CS1 maint: varios nombres: lista de autores ( enlace )
- ^ a b Pach, János; Tóth, Géza (2000), "¿Qué número de cruce es de todos modos?", Journal of Combinatorial Theory , Serie B, 80 (2): 225–246, doi : 10.1006 / jctb.2000.1978
- ^ Matoušek, Jiří (2014), "Separadores casi óptimos en gráficos de cadenas", Combin. Probab. Computación. , 23 , págs. 135-139, arXiv : 1302.6482 , doi : 10.1017 / S0963548313000400 , S2CID 2351522
- ^ Chojnacki (Hanani), Chaim (Haim) (1934), "Uber wesentlich unplattbar Kurven im dreidimensionale Raume", Fundamenta Mathematicae , 23 : 135-142, doi : 10.4064 / fm-23-1-135-142
- ^ Tutte, William T. (1970), "Hacia una teoría del cruce de números", Journal of Combinatorial Theory , 8 : 45–53, doi : 10.1016 / s0021-9800 (70) 80007-2
- ^ Pelsmajer, Michael J .; Schaefer, Marcus; Štefankovič, Daniel (2007), "Eliminación de cruces pares", Journal of Combinatorial Theory , Serie B, 97 (4): 489–500, doi : 10.1016 / j.jctb.2006.08.001
- ^ Bienstock, Daniel; Dean, Nathaniel (1993), "Límites para números de cruces rectilíneos", Journal of Graph Theory , 17 (3): 333–348, doi : 10.1002 / jgt.3190170308
- ^ Graham, Ronald L .; Rothschild, Bruce L .; Spencer, Joel H. (1990), Teoría de Ramsey , Wiley
- ^ Károlyi, Gyula (2013), "Problemas tipo Ramsey para gráficos geométricos", en Pach, J. (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer
- ^ a b Károlyi, Gyula J .; Pach, János; Tóth, Géza (1997), "Resultados tipo Ramsey para gráficas geométricas, I", Geometría discreta y computacional , 18 (3): 247-255, doi : 10.1007 / PL00009317
- ^ Károlyi, Gyula J .; Pach, János; Tóth, Géza; Valtr, Pavel (1998), "Resultados tipo Ramsey para gráficas geométricas, II", Geometría discreta y computacional , 20 (3): 375–388, doi : 10.1007 / PL00009391
- ^ Pach, János (2004), "Teoría de grafos geométricos", en Goodman, Jacob E .; O'Rourke, Joseph (eds.), Manual de geometría discreta y computacional , Matemáticas discretas y sus aplicaciones (2a ed.), Chapman y Hall / CRC
- ^ Matoušek, Jiří ; Tancer, Martin; Wagner, Uli (2009), Dureza de incrustar complejos simpliciales en, págs. 855–864 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ Brass, Peter (2004), "Problemas tipo Turán para hipergráficos geométricos convexos", en Pach, J. (ed.), Towards a Theory of Geometric Graphs , Contemporary Mathematics, American Mathematical Society, pp. 25–33
- ^ a b c d Dey, Tamal K .; Pach, János (1998), "Problemas extremos para hipergráficos geométricos", Geometría discreta y computacional , 19 (4): 473–484, doi : 10.1007 / PL00009365
- ^ Suk, Andrew (2013), "Una nota sobre los 3-hipergráficos geométricos", en Pach, J. (ed.), Treinta ensayos sobre teoría de gráficos geométricos , Springer arXiv: 1010.5716v3
- ^ Živaljević, Rade T .; Vrećica, Siniša T. (1992), "El problema de Tverberg coloreado y los complejos de funciones inyectivas", Journal of Combinatorial Theory , Serie A, 61 (2): 309–318, doi : 10.1016 / 0097-3165 (92) 90028- S
- ^ Bárány, Imre; Fürédi, Zoltán (1987), "Simplices vacíos en el espacio euclidiano", Canadian Mathematical Bulletin , 30 (4): 436–445, doi : 10.4153 / cmb-1987-064-1 , hdl : 1813/8573
- ^ Károlyi, Gyula; Solymosi, József (2002), "Triángulos casi disjuntos en 3 espacios", Geometría discreta y computacional , 28 (4): 577–583, doi : 10.1007 / s00454-002-2888-z