Gráfico topológico

Un gráfico con un número de cruces impares de 13 y un número de cruces de pares de 15 ^[1]

En matemáticas , un grafo topológico es una representación de un grafo en el plano , donde los vértices del grafo están representados por puntos distintos y las aristas por arcos de Jordan (fragmentos conectados de curvas de Jordan ) que unen los pares de puntos correspondientes. Los puntos que representan los vértices de un grafo y los arcos que representan sus aristas se denominan vértices y aristas del grafo topológico. Por lo general, se supone que dos aristas cualesquiera de un grafo topológico se cruzan un número finito de veces, ninguna arista pasa por un vértice diferente de sus puntos finales y ninguna de las dos aristas se toca entre sí (sin cruzarse). Un grafo topológico también se denomina dibujo de un grafo.

Una clase especial importante de grafos topológicos es la clase de grafos geométricos , donde los bordes están representados por segmentos de línea . (El término grafo geométrico a veces se utiliza 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, de los patrones de cruce de sus aristas. Está estrechamente relacionada con el dibujo de grafos , un campo más orientado a la aplicación, y con la teoría de grafos topológicos , que se centra en las incrustaciones de grafos en superficies (es decir, dibujos sin cruces).

Problemas extremos para grafos topológicos

Un problema fundamental en la teoría de grafos extremales es el siguiente: ¿cuál es el número máximo de aristas que puede tener un grafo de n vértices si no contiene ningún subgrafo perteneciente a una clase dada de subgrafos prohibidos ? El prototipo de tales resultados es el teorema de Turán , donde hay un subgrafo prohibido: un grafo completo con k vértices ( k es fijo). Pueden plantearse cuestiones análogas para los grafos topológicos y geométricos, con la diferencia de que ahora ciertas subconfiguraciones geométricas están prohibidas.

Históricamente, la primera instancia de un teorema de este tipo 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 un grafo geométrico con n  > 2 vértices puede tener 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 grafos topológicos simples. Un grafo topológico se llama "simple" si cualquier par de sus aristas comparte como máximo un punto, que es un punto final o un punto interior común en el que las dos aristas se cruzan correctamente. La conjetura de thrackle de Conway ahora se puede reformular de la siguiente manera: Un grafo topológico simple con n  > 2 vértices y sin dos aristas disjuntas tiene como máximo n aristas.

El primer límite superior lineal del número de aristas de un grafo de este tipo fue establecido por Lovász et al. ^[3] El límite superior más conocido, 1,3984 n , fue demostrado por Fulek y Pach . ^[4] Aparte de los grafos geométricos, se sabe que la conjetura de Thrackle de Conway es verdadera para grafos topológicos x -monótonos. ^[5] Se dice que un grafo topológico es x-monótono si cada línea vertical interseca cada arista 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 aristas disjuntas ( k  > 2). Probaron que el número de aristas de un grafo geométrico 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 establecido por Pach y Töröcsik. ^[8] Esto fue mejorado por Tóth a . ^[9] Para el número de aristas en un grafo topológico simple sin k aristas disjuntas, solo se conoce un límite superior. ^[10] Esto implica que cada grafo topológico simple completo con n vértices tiene al menos aristas disjuntas por pares, lo que fue mejorado por Ruiz-Vargas. ^{[11] [12]} Es posible que este límite inferior pueda mejorarse aún más a cn , donde c  > 0 es una constante. ${\displaystyle O(k^{4}n)}$ ${\displaystyle O(k^{2}n)}$ ${\displaystyle O(n\log ^{4k-8}n)}$ ${\displaystyle c{\frac {\log n}{\log \log n}}}$ ${\displaystyle cn^{{\frac {1}{2}}-\epsilon }}$

Grafos cuasi-planares

Un punto interior común de dos aristas, en el que la primera arista pasa de un lado de la segunda arista al otro, se llama cruce . Dos aristas de un grafo topológico se cruzan entre sí si determinan un cruce. Para cualquier entero k  > 1, un grafo topológico o geométrico se llama k-cuasiplanar si no tiene k aristas que se crucen por pares. Usando esta terminología, si un grafo topológico es 2-cuasiplanar, entonces es un grafo planar . De la fórmula poliédrica de Euler se deduce que todo grafo planar con n  > 2 vértices tiene como máximo 3 n  − 6 aristas. Por lo tanto, todo grafo 2-cuasiplanar con n  > 2 vértices tiene como máximo 3 n  − 6 aristas.

^{Pach et al. [13]} han conjeturado que cada k -grafo topológico cuasi-planar con n vértices tiene como máximo c ( k ) n aristas, donde c ( k ) es una constante que depende sólo de k . Se sabe que esta conjetura es verdadera para k  = 3 ^{[14] [15]} y k  = 4. ^[16] También se sabe que es verdadera para grafos geométricos convexos (es decir, para grafos geométricos cuyos vértices forman el conjunto de vértices de un n -gono convexo), ^[17] y para k -grafos topológicos cuasi-planares cuyas aristas se dibujan como curvas x -monótonas, todas las cuales cruzan una línea vertical. ^{[18] [19]} El último resultado implica que cada k -grafo topológico cuasi-planar con n vértices, cuyas aristas se dibujan como curvas x -monótonas tiene como máximo c ( k ) n  log  n aristas para una constante adecuada c ( k ). Para los gráficos geométricos, esto fue demostrado anteriormente por Valtr. ^{[20] El} límite superior general más conocido para el número de aristas de un gráfico topológico k -cuasiplanar es . ^[21] Esto implica que cada gráfico topológico completo con n vértices tiene al menos aristas que se cruzan por pares, lo que se mejoró a un límite cuasi lineal en el caso del gráfico geométrico. ^[22] ${\displaystyle n\log ^{O(\log k)}n}$ ${\displaystyle n^{\frac {1}{O(\log \log n)}}}$

Cruce de números

Desde que Pál Turán acuñó su problema de la fábrica de ladrillos ^[23] durante la Segunda Guerra Mundial , la determinación o estimación de números cruzados de grafos ha sido un tema popular en la teoría de grafos y en la teoría de algoritmos ^[24] que está llena de famosos problemas abiertos de larga data como la conjetura de Albertson , la conjetura de Harary-Hill ^[25] o el todavía sin resolver problema de la fábrica de ladrillos de Turán . ^[26] Sin embargo, las publicaciones en el tema (explícita o implícitamente) utilizaron varias definiciones competitivas de números cruzados. Esto fue señalado por Pach y Tóth, ^[27] quienes introdujeron la siguiente terminología.

Número de cruces (de un grafo G ): Número mínimo de puntos de cruce en todos los dibujos de G en el plano (es decir, todas sus representaciones como grafo topológico) con la propiedad de que no hay tres aristas que pasen por el mismo punto. Se denota por cr( G ).

Número de cruces de pares : el número mínimo de pares de aristas que se cruzan en todos los dibujos de G. Se denota por pair-cr( G ).

Número de cruces impares : el número mínimo de esos pares de aristas que se cruzan un número impar de veces, en todos los dibujos de G. Se denota por odd-cr( G ).

Estos parámetros no son independientes. Uno tiene odd-cr( G ) ≤ pair-cr( G ) ≤ cr( G ) para cada grafo G . Se sabe que cr( G ) ≤ 2(odd-cr( G )) ^{2 [27]} y ^[28] y que existen infinitos grafos para los cuales pair-cr( G ) ≠ odd-cr( G ). ^{[1] [29]} No se conocen ejemplos para los cuales el número de cruces y el número de cruces de pares no sean los mismos. Se deduce del teorema de Hanani-Tutte ^{[30] [31]} que odd-cr( G ) = 0 implica cr( G ) = 0. También se sabe que odd-cr( G ) =  k implica cr(G)=k para k  = 1, 2, 3. ^[32] Otro parámetro de grafo bien investigado es el siguiente. ${\displaystyle O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))}$

Número de cruces rectilíneos : Número mínimo de puntos de cruce en todos los dibujos de líneas rectas de G en el plano (es decir, todas sus representaciones como 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, se tiene cr( G ) ≤ lin-cr( G ) para cada grafo G . Bienstock y Dean demostraron que hay grafos con número de cruces 4 y con número de cruces rectilíneos arbitrariamente grande. ^[33]

El cálculo del número de cruce es NP-completo ^[34] en general. Por lo tanto, una gran cantidad de investigación se centra en sus estimaciones. El Lema de cruce es un resultado fundamental que proporciona límites inferiores ampliamente aplicables en el número de cruce. Se conocen varias variantes y generalizaciones interesantes del Lema de cruce para las curvas de Jordan ^{[35] [36]} y el número de cruce degenerado ^{[37] [38]} , donde este último relaciona la noción de número de cruce con el género de grafos .

Problemas tipo Ramsey para gráficos geométricos

En la teoría de grafos tradicional , un resultado típico de tipo Ramsey establece que si coloreamos los bordes de un grafo completo suficientemente grande con un número fijo de colores, entonces necesariamente encontramos un subgrafo monocromático de un cierto tipo. ^[39] Se pueden plantear preguntas similares para grafos geométricos (o topológicos), excepto que ahora buscamos subestructuras monocromáticas (de un solo color) que satisfagan ciertas condiciones geométricas. ^[40] Uno de los primeros resultados de este tipo establece que cada grafo geométrico completo cuyos bordes están coloreados con dos colores contiene un árbol de expansión monocromático que no se cruza . ^[41] También es cierto que cada grafo geométrico de este tipo contiene bordes disjuntos del mismo color. ^[41] La existencia de un camino monocromático que no se cruza de tamaño al menos cn , donde c  > 0 es una constante, es un problema abierto de larga data. Solo se sabe que cada grafo geométrico completo en n vértices contiene un camino monocromático que no se cruza de longitud al menos . ^[42] ${\displaystyle \left\lceil {\frac {n+1}{3}}\right\rceil }$ ${\displaystyle n^{\frac {2}{3}}}$

Hipergrafos topológicos

Si consideramos un grafo topológico como una realización topológica de un complejo simplicial unidimensional , es natural preguntar 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. ^{[43] [44] [45]}

Se dice que dos símplices disjuntos en sus vértices se cruzan si sus interiores relativos tienen un punto en común. Un conjunto de k  > 3 símplices se cruza fuertemente si no hay 2 de ellos que compartan un vértice, pero sus interiores relativos tienen un punto en común.

Se sabe que un conjunto de símplices d -dimensionales abarcados por n puntos en sin un par de símplices que se cruzan puede tener como máximo símplices y este límite es asintóticamente ajustado. ^[46] Este resultado se generalizó a conjuntos de símplices bidimensionales en sin tres símplices que se cruzan fuertemente. ^[47] Si prohibimos k símplices que se cruzan fuertemente, el límite superior correspondiente mejor conocido es , ^[46] para algunos . Este resultado se desprende del teorema de Tverberg coloreado . ^[48] Está lejos del límite conjeturado de . ^[46] ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle O(n^{d})}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle O(n^{d+1-\delta })}$ ${\displaystyle \delta =\delta (k,d)<1}$ ${\displaystyle O(n^{d})}$

Para cualquier k fijo  > 1, podemos seleccionar como máximo símplices d -dimensionales abarcados por un conjunto de n puntos con la propiedad de que ningún k de ellos comparte un punto interior común. ^{[46] [49]} Esto es asintóticamente ajustado. ${\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}$ ${\displaystyle \mathbb {R} ^{d}}$

Se dice que dos triángulos en son casi disjuntos si son disjuntos o si comparten un solo vértice. Un viejo problema de Gil Kalai y otros es 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 menos para una constante adecuada c  > 0. ^[50] ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle o(n^{2})}$ ${\displaystyle cn^{\frac {3}{2}}}$

Referencias

1. 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-xUna versión preliminar de estos resultados fue revisada en Proc. of 13th International Symposium on Graph Drawing , 2005, pp. 386–396, doi : 10.1007/11618058_35
2. Hopf, Heinz ; Pannwitz, Erika (1934), "Aufgabe nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung , 43 : 114
3. Lovász, László ; Pach, János ; Szegedy, Mario (1997), "Sobre la conjetura del estrangulamiento de Conway", Geometría discreta y computacional , 18 (4), Springer: 369–376, doi : 10.1007/PL00009322
4. Fulek, Radoslav ; Pach, János (2019), "Thrackles: Un límite superior mejorado", Discrete Applied Mathematics , 259 : 226–231, arXiv : 1708.08037 , doi :10.1016/j.dam.2018.12.025.
5. Pach, János ; Sterling, Ethan (2011), "Conjetura de Conway para thrackles monótonos", American Mathematical Monthly , 118 (6): 544–548, doi :10.4169/amer.math.monthly.118.06.544, MR  2812285, S2CID  17558559
6. Alon, Noga ; Erdős, Paul (1989), "Aristas disjuntas en gráficos geométricos", Geometría discreta y computacional , 4 (4): 287–290, doi : 10.1007/bf02187731
7. Černý, Jakub (2005), "Gráficos geométricos sin tres aristas disjuntas", Geometría discreta y computacional , 34 (4): 679–695, doi : 10.1007/s00454-005-1191-1
8. 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
9. Tóth, Géza (2000), "Nota sobre grafos geométricos", Journal of Combinatorial Theory , Serie A, 89 (1): 126–132, doi : 10.1006/jcta.1999.3001
10. Pach, János ; Tóth, Géza (2003), "Aristas disjuntas en grafos topológicos", Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, 13-16 de septiembre de 2003, Documentos seleccionados revisados ​​(PDF) , Lecture Notes in Computer Science, vol. 3330, Springer-Verlag, pp. 133–140, doi :10.1007/978-3-540-30540-8_15
11. Ruiz-Vargas, Andres J. (2015), "Muchas aristas disjuntas en grafos topológicos", en Campêlo, Manoel; Corrêa, Ricardo; Linhares-Sales, Cláudia; Sampaio, Rudini (eds.), LAGOS'15 – VIII Simposio Latinoamericano de Algoritmos, Grafos y Optimización , Electronic Notes in Discrete Mathematics, vol. 50, Elsevier, pp. 29–34, arXiv : 1412.3833 , doi :10.1016/j.endm.2015.07.006, S2CID  14865350
12. Ruiz-Vargas, Andres J. (2017), "Muchas aristas disjuntas en grafos topológicos", Comput. Geom. , 62 : 1–13, arXiv : 1412.3833 , doi :10.1016/j.comgeo.2016.11.003
13. Pach, János ; Shahrokhi, Farhad; Szegedy, Mario (1996), "Aplicaciones del número de cruce", Algorithmica , 16 (1), Springer: 111–117, doi :10.1007/BF02086610, S2CID  20375896
14. Agarwal K., Pankaj ; Arónov, Boris ; Pach, János ; Pollack, Richard ; Sharir, Micha (1997), "Los gráficos cuasiplanares tienen un número lineal de aristas", Combinatorica , 17 : 1–9, doi :10.1007/bf01196127, S2CID  8092013
15. Ackerman, Eyal; Tardos, Gábor (2007), "Sobre el número máximo de aristas en grafos cuasiplanares", Journal of Combinatorial Theory , Serie A, 114 (3): 563–571, ​​doi :10.1016/j.jcta.2006.08.002
16. Ackerman, Eyal (2009), "Sobre el número máximo de aristas en grafos topológicos sin cuatro aristas cruzadas por pares", Geometría discreta y computacional , 41 (3): 365–375, doi : 10.1007/s00454-009-9143-9
17. Capoyleas, Vasilis; Pach, János (1992), "Un teorema de tipo Turán sobre cuerdas de un polígono convexo", Journal of Combinatorial Theory , Serie B, 56 (1): 9–15, doi :10.1016/0095-8956(92)90003-G
18. Suk, Andrew (2011), " k -quasi-planar graphs", Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, Países Bajos, 21-23 de septiembre de 2011, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 7034, Springer-Verlag, págs. 266-277, arXiv : 1106.0958 , doi :10.1007/978-3-642-25878-7_26, S2CID  18681576
19. Fox, Jacob ; Pach, János ; Suk, Andrew (2013), "El número de aristas en grafos k -cuasiplanares", SIAM Journal on Discrete Mathematics , 27 (1): 550–561, arXiv : 1112.2361 , doi :10.1137/110858586, S2CID  52317.
20. Valtr, Pavel (1997), "Dibujo de grafos sin k pares de aristas cruzadas", Graph Drawing: 5th International Symposium, GD '97 Roma, Italia, 18-20 de septiembre de 1997, Actas , Lecture Notes in Computer Science, vol. 1353, Springer-Verlag, págs. 205-218
21. Fox, Jacob; Pach, János (2012), "Coloración de gráficos de intersección libres de objetos geométricos en el plano con K k {\displaystyle K_{\mbox{k}}}" (PDF) , European Journal of Combinatorics , 33 (5): 853–866, doi : 10.1016/j.ejc.2011.09.021Una versión preliminar de estos resultados fue anunciada en Proc. of Symposium on Computational Geometry (PDF) , 2008, págs. 346–354, doi :10.1145/1377676.1377735, S2CID  15138458
22. Pach, János ; Rubin, Natan; Tardos, Gábor (2021), "Los conjuntos de puntos planos determinan muchos segmentos cruzados por pares", Advances in Mathematics , 386 : 107779, arXiv : 1904.08845 , doi : 10.1016/j.aim.2021.107779.
23. Turán, Paul (1977), "Una nota de bienvenida", Journal of Graph Theory , 1 : 7–9, doi :10.1002/jgt.3190010105
24. Garey, MR ; Johnson, DS (1983), "El número de cruce es NP-completo", Revista SIAM sobre métodos algebraicos y discretos , 4 (3): 312–316, doi :10.1137/0604033, MR  0711340{{citation}}: CS1 maint: varios nombres: lista de autores ( enlace )
25. Balogh, József; Lidický, Bernard; Salazar, Gelasio (2019), "Acercándonos a la conjetura de Hill", SIAM Journal on Discrete Mathematics , 33 (3): 1261–1276, arXiv : 1711.08958 , doi :10.1137/17M1158859, S2CID  119672893
26. Schaefer, Marcus (2012), "El número de cruce de grafos y sus variantes: una encuesta", Electronic Journal of Combinatorics , 1000 : DS21–May, doi : 10.37236/2713
27. Pach, János; Tóth, Géza (2000), "¿Cuál es el número de cruce?", Journal of Combinatorial Theory , Serie B, 80 (2): 225–246, doi : 10.1006/jctb.2000.1978
28. Matoušek, Jiří (2014), "Separadores casi óptimos en grafos de cadenas", Combin. Probab. Comput. , vol. 23, págs. 135–139, arXiv : 1302.6482 , doi : 10.1017/S0963548313000400, S2CID  2351522
29. Tóth, Géza (2008), "Nota sobre el número de cruces de pares y el número de cruces impares", Geometría discreta y computacional , 39 (4): 791–799, doi : 10.1007/s00454-007-9024-z.
30. 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
31. Tutte, William T. (1970), "Hacia una teoría de los números cruzados", Journal of Combinatorial Theory , 8 : 45–53, doi :10.1016/s0021-9800(70)80007-2
32. 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
33. Bienstock, Daniel; Dean, Nathaniel (1993), "Límites para números de cruce rectilíneos", Journal of Graph Theory , 17 (3): 333–348, doi :10.1002/jgt.3190170308
34. Garey, MR ; Johnson, DS (1983). "El número de cruce es NP-completo". Revista SIAM sobre métodos algebraicos y discretos . 4 (3): 312–316. doi :10.1137/0604033. MR  0711340.
35. Pach, János ; Rubin, Natán; Tardos, Gábor (2018), "Un lema de cruce para las curvas de Jordan", Avances en Matemáticas , 331 : 908–940, arXiv : 1708.02077 , doi : 10.1016/j.aim.2018.03.015, S2CID  22278629
36. Pach, János ; Tóth, Géza (2019), "Muchos toques fuerzan muchos cruces", Journal of Combinatorial Theory , Serie B, 137 : 104–111, arXiv : 1706.06829 , doi :10.1016/j.jctb.2018.12.002
37. Ackerman, Eyal; Pinchasi, Rom (2013), "Sobre el número de cruce degenerado", Geometría discreta y computacional , 49 (3): 695–702, doi :10.1007/s00454-013-9493-1, S2CID  254030772
38. Schaefer, Marcus; Štefankovič, Daniel (2015), "El número de cruce degenerado y las incrustaciones de géneros superiores", Graph Drawing: 23rd International Symposium, GD 2015, Los Ángeles, CA, EE. UU., 24-26 de septiembre de 2015, Documentos seleccionados revisados , págs. 63–74, doi : 10.1007/978-3-319-27261-0_6
39. Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1990), Teoría de Ramsey , Wiley
40. Károlyi, Gyula (2013), "Problemas de tipo Ramsey para grafos geométricos", en Pach, J. (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer
41. Károlyi, Gyula J.; Pach, János; Tóth, Géza (1997), "Resultados de tipo Ramsey para gráficos geométricos, I", Geometría discreta y computacional , 18 (3): 247–255, doi : 10.1007/PL00009317
42. Károlyi, Gyula J.; Pach, János; Tóth, Géza; Valtr, Pavel (1998), "Resultados de tipo Ramsey para gráficos geométricos, II", Geometría discreta y computacional , 20 (3): 375–388, doi : 10.1007/PL00009391
43. Pach, János (2004), "Teoría geométrica de grafos", en Goodman, Jacob E. ; O'Rourke, Joseph (eds.), Manual de geometría discreta y computacional , Matemáticas discretas y sus aplicaciones (2.ª ed.), Chapman y Hall/CRC
44. Matoušek, Jiří ; Tancer, Martin; Wagner, Uli (2009), "Dureza de la incrustación de complejos simpliciales en ", Actas del vigésimo simposio anual ACM-SIAM sobre algoritmos discretos , págs. 855–864 ${\displaystyle \mathbb {R} ^{d}}$
45. Brass, Peter (2004), "Problemas de tipo Turán para hipergrafos geométricos convexos", en Pach, J. (ed.), Towards a Theory of Geometric Graphs , Contemporary Mathematics, American Mathematical Society, pp. 25–33
46. Dey, Tamal K. ; Pach, János (1998), "Problemas extremos para hipergrafos geométricos", Geometría discreta y computacional , 19 (4): 473–484, doi : 10.1007/PL00009365
47. Suk, Andrew (2013), "Una nota sobre los 3-hipergrafos geométricos", en Pach, J. (ed.), Treinta ensayos sobre teoría de grafos geométricos , SpringerarXiv:1010.5716v3
48. Ž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
49. Bárány, Imre; Fürédi, Zoltán (1987), "Simples vacíos en el espacio euclidiano", Canadian Mathematical Bulletin , 30 (4): 436–445, doi :10.4153/cmb-1987-064-1, hdl : 1813/8573 , S2CID  122255929
50. 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