Gráfico sin triángulos

Grafo sin triples de vértices adyacentes

En el área matemática de la teoría de grafos , un grafo sin triángulos es un grafo no dirigido en el que no hay tres vértices que formen un triángulo de aristas. Los grafos sin triángulos pueden definirse de manera equivalente como grafos con un número de clique  ≤ 2, grafos con circunferencia  ≥ 4, grafos sin ciclos de 3 inducidos o grafos localmente independientes .

Los grafos sin triángulos con más aristas en sus vértices son grafos bipartitos completos balanceados . Muchos grafos sin triángulos no son bipartitos, por ejemplo, cualquier grafo cíclico C _n para  n impar  > 3.

Por el teorema de Turán , el grafo libre de triángulos de n vértices con el máximo número de aristas es un grafo bipartito completo en el que los números de vértices en cada lado de la bipartición son lo más iguales posibles.

Problema de búsqueda de triángulos

El problema de búsqueda o detección de triángulos consiste en determinar si un gráfico no tiene triángulos o no. Cuando el gráfico contiene un triángulo, a menudo se requieren algoritmos para generar tres vértices que formen un triángulo en el gráfico.

Es posible probar si un grafo con aristas está libre de triángulos en el tiempo donde el oculta factores subpolinómicos. Aquí está el exponente de la multiplicación rápida de matrices ; ^[1] de lo que se deduce que la detección de triángulos se puede resolver en el tiempo . Otro enfoque es encontrar la traza de A ³ , donde A es la matriz de adyacencia del grafo. La traza es cero si y solo si el grafo está libre de triángulos. Para grafos densos , es más eficiente usar este algoritmo simple que nuevamente se basa en la multiplicación de matrices, ya que reduce la complejidad temporal a , donde es el número de vértices. ${\displaystyle m}$ ${\displaystyle {\tilde {O}}{\bigl (}m^{2\omega /(\omega +1)}{\bigr )}}$ ${\displaystyle {\tilde {O}}}$ ${\displaystyle \omega }$ ${\displaystyle \omega <2.372}$ ${\displaystyle O(m^{1.407})}$ ${\displaystyle O(n^{\omega })}$ ${\displaystyle n}$

Incluso si se descubrieran algoritmos de multiplicación de matrices con tiempo , los mejores límites temporales que se podrían esperar de estos enfoques son o . En la complejidad de grano fino , la hipótesis del triángulo disperso es una suposición de dureza computacional no probada que afirma que no es posible ningún límite temporal de la forma , para cualquier , independientemente de las técnicas algorítmicas que se utilicen. Esta, y la hipótesis del triángulo denso correspondiente de que no es posible ningún límite temporal de la forma , implican límites inferiores para varios otros problemas computacionales en optimización combinatoria y geometría computacional . ^[2] ${\displaystyle O(n^{2})}$ ${\displaystyle O(m^{4/3})}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(m^{4/3-\delta })}$ ${\displaystyle \delta >0}$ ${\displaystyle O(n^{\omega -\delta })}$

Como demostraron Imrich, Klavžar y Mulder (1999), el reconocimiento de gráficos sin triángulos es equivalente en complejidad al reconocimiento de gráficos medianos ; sin embargo, los mejores algoritmos actuales para el reconocimiento de gráficos medianos utilizan la detección de triángulos como una subrutina en lugar de lo contrario.

La complejidad del árbol de decisión o la complejidad de la consulta del problema, donde las consultas son a un oráculo que almacena la matriz de adyacencia de un grafo, es Θ( n ² ) . Sin embargo, para los algoritmos cuánticos , el límite inferior más conocido es Ω( n ) , pero el algoritmo más conocido es O ( n ^5/4 ) . ^[3]

Número de independencia y teoría de Ramsey

Un conjunto independiente de vértices (donde es la función de suelo ) en un grafo libre de triángulos con n vértices es fácil de encontrar: o bien hay un vértice con al menos vecinos (en cuyo caso esos vecinos son un conjunto independiente) o todos los vértices tienen estrictamente menos de vecinos (en cuyo caso cualquier conjunto independiente maximal debe tener al menos vértices). ^[4] Este límite se puede ajustar ligeramente: en cada grafo libre de triángulos existe un conjunto independiente de vértices, y en algunos grafos libres de triángulos cada conjunto independiente tiene vértices. ^[5] Una forma de generar grafos libres de triángulos en los que todos los conjuntos independientes son pequeños es el proceso libre de triángulos ^[6] en el que se genera un grafo libre de triángulos maximal añadiendo repetidamente aristas elegidas al azar que no completan un triángulo. Con alta probabilidad, este proceso produce un grafo con número de independencia . También es posible encontrar grafos regulares con las mismas propiedades. ^[7] ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ ${\displaystyle \lfloor \cdot \rfloor }$ ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ ${\displaystyle \Omega ({\sqrt {n\log n}})}$ ${\displaystyle O({\sqrt {n\log n}})}$ ${\displaystyle O({\sqrt {n\log n}})}$

Estos resultados también pueden interpretarse como que dan límites asintóticos a los números de Ramsey R(3, t ) de la forma : si los bordes de un gráfico completo en los vértices están coloreados de rojo y azul, entonces el gráfico rojo contiene un triángulo o, si no tiene triángulos, entonces debe tener un conjunto independiente de tamaño t correspondiente a una camarilla del mismo tamaño en el gráfico azul. ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$ ${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$

Colorear gráficos sin triángulos

El gráfico de Grötzsch es un gráfico sin triángulos que no se puede colorear con menos de cuatro colores.

Gran parte de la investigación sobre grafos sin triángulos se ha centrado en la coloración de los grafos . Todo grafo bipartito (es decir, todo grafo que se pueda colorear con dos colores) no tiene triángulos, y el teorema de Grötzsch establece que todo grafo plano sin triángulos puede tener tres colores. ^[8] Sin embargo, los grafos no planos sin triángulos pueden requerir muchos más de tres colores.

La primera construcción de grafos libres de triángulos con un número cromático arbitrariamente alto se debe a Tutte (escribiendo como Blanche Descartes ^[9] ). Esta construcción comenzó a partir del grafo con un solo vértice, digamos , y se construyó inductivamente a partir de lo siguiente: sea que tenga vértices, luego tome un conjunto de vértices y para cada subconjunto de de tamaño agregue una copia disjunta de y únala a con un correspondiente. Del principio del palomar se sigue inductivamente que no es coloreable, ya que al menos uno de los conjuntos debe estar coloreado monocromáticamente si solo se nos permite usar k colores. Mycielski (1955) definió una construcción, ahora llamada Mycielskian , para formar un nuevo grafo libre de triángulos a partir de otro grafo libre de triángulos. Si un grafo tiene número cromático k , su Mycielskian tiene número cromático k  + 1, por lo que esta construcción puede usarse para mostrar que pueden necesitarse cantidades arbitrariamente grandes de colores para colorear grafos libres de triángulos no planos. En particular, el grafo de Grötzsch , un grafo de 11 vértices formado por la aplicación repetida de la construcción de Mycielski, es un grafo sin triángulos que no se puede colorear con menos de cuatro colores, y es el grafo más pequeño con esta propiedad. ^[10] Gimbel & Thomassen (2000) y Nilli (2000) demostraron que la cantidad de colores necesarios para colorear cualquier grafo sin triángulos de m aristas es ${\displaystyle G_{1}}$ ${\displaystyle G_{k+1}}$ ${\displaystyle G_{k}}$ ${\displaystyle G_{k}}$ ${\displaystyle n}$ ${\displaystyle Y}$ ${\displaystyle k(n-1)+1}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle n}$ ${\displaystyle G_{k}}$ ${\displaystyle X}$ ${\displaystyle G_{k+1}}$ ${\displaystyle k}$ ${\displaystyle X}$

${\displaystyle O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)}$

y que existen grafos libres de triángulos que tienen números cromáticos proporcionales a este límite.

También se han obtenido varios resultados que relacionan la coloración con el grado mínimo en grafos sin triángulos. Andrásfai, Erdős y Sós (1974) demostraron que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga más de 2 n /5 vecinos debe ser bipartito. Este es el mejor resultado posible de este tipo, ya que el ciclo de 5 requiere tres colores pero tiene exactamente 2 n /5 vecinos por vértice. Motivados por este resultado, Erdős y Simonovits (1973) conjeturaron que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga al menos n /3 vecinos puede colorearse con solo tres colores; sin embargo, Häggkvist (1981) refutó esta conjetura al encontrar un contraejemplo en el que cada vértice del grafo de Grötzsch se reemplaza por un conjunto independiente de un tamaño cuidadosamente elegido. Jin (1995) demostró que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga más de 10 n /29 vecinos debe ser 3-coloreable; este es el mejor resultado posible de este tipo, porque el grafo de Häggkvist requiere cuatro colores y tiene exactamente 10 n /29 vecinos por vértice. Finalmente, Brandt y Thomassé (2006) demostraron que cualquier grafo sin triángulos de n vértices en el que cada vértice tenga más de n /3 vecinos debe ser 4-coloreable. No son posibles resultados adicionales de este tipo, ya que Hajnal ^[11] encontró ejemplos de grafos sin triángulos con un número cromático arbitrariamente grande y un grado mínimo (1/3 − ε) n para cualquier ε > 0.

Véase también

• Gráfico de Andrásfai , una familia de gráficos circulantes sin triángulos con diámetro dos
• Gráfico de Henson , un gráfico infinito sin triángulos que contiene todos los gráficos finitos sin triángulos como subgrafos inducidos
• Gráfico de desplazamiento , una familia de gráficos sin triángulos con un número cromático arbitrariamente alto
• El gráfico de Kneser no tiene triángulos y tiene número cromático. ${\displaystyle KG_{3k-1,k}}$ ${\displaystyle k+1}$
• Problema del triángulo monocromático , el problema de dividir los bordes de un gráfico dado en dos gráficos sin triángulos.
• Problema de Ruzsa-Szemerédi , sobre grafos en los que cada arista pertenece exactamente a un triángulo

Referencias

Notas

1. Alon, Yuster y Zwick (1994).
2. Abboud y otros. (2022); Chan (2023); Jin y Xu (2023)
3. Le Gall (2014), mejorando algoritmos anteriores de Lee, Magniez & Santha (2013) y Belovs (2012).
4. Boppana & Halldórsson (1992) p. 184, basado en una idea de un algoritmo de aproximación de coloración anterior de Avi Wigderson .
5. Kim (1995).
6. Erdős, Suen y Winkler (1995); Bohman (2009).
7. Alon, Ben-Shimon y Krivelevich (2010).
8. Grötzsch (1959); Thomassen (1994)).
9. Descartes (1947); Descartes (1954)
10. Chvátal (1974).
11. ver Erdős y Simonovits (1973).

Fuentes

• Abboud, Amir; Bringmann, Karl; Khoury, Seri; Zamir, Or (2022), "Dureza de aproximación en P mediante la eliminación de ciclos cortos: detección de ciclos, oráculos de distancia y más allá", en Leonardi, Stefano; Gupta, Anupam (eds.), STOC '22: 54.º Simposio anual ACM SIGACT sobre teoría de la computación, Roma, Italia, 20-24 de junio de 2022 , {ACM}, págs. 1487-1500, arXiv : 2204.10465 , doi : 10.1145/3519935.3520066, S2CID  248366492
• Alon, Noga ; Ben-Shimon, Sonny; Krivelevich, Michael (2010), "Una nota sobre los gráficos de Ramsey regulares", Journal of Graph Theory , 64 (3): 244–249, arXiv : 0812.2386 , doi :10.1002/jgt.20453, MR  2674496, S2CID  1784886.
• Alon, N .; Yuster, R.; Zwick, U. (1994), "Encontrar y contar ciclos de longitud determinados", Actas del 2º Simposio Europeo sobre Algoritmos, Utrecht, Países Bajos , págs. 354–364.
• Andrásfai, B.; Erdős, P.; Sós , VT (1974), "Sobre la conexión entre el número cromático, la camarilla máxima y el grado mínimo de un grafo" (PDF) , Discrete Mathematics , 8 (3): 205–218, doi :10.1016/0012-365X(74)90133-2.
• Belovs, Aleksandrs (2012), "Programas de extensión para funciones con certificados 1 de tamaño constante", Actas del cuadragésimo cuarto simposio anual de la ACM sobre teoría de la computación (STOC '12) , Nueva York, NY, EE. UU.: ACM, págs. 77–84, arXiv : 1105.4024 , doi : 10.1145/2213977.2213985, ISBN 978-1-4503-1245-5, Número de identificación del sujeto  18771464.
• Bohman, Tom (2009), "El proceso sin triángulos", Advances in Mathematics , 221 (5): 1653–1677, arXiv : 0806.4375 , doi : 10.1016/j.aim.2009.02.018 , MR  2522430, S2CID  17701040.
• Boppana, Ravi; Halldórsson, Magnús M. (1992), "Aproximación de conjuntos independientes máximos mediante la exclusión de subgrafos", BIT , 32 (2): 180–196, doi :10.1007/BF01994876, MR  1172185, S2CID  123335474.
• Brandt, S.; Thomassé, S. (2006), Los grafos densos sin triángulos son coloreables en cuatro colores: una solución al problema de Erdős–Simonovits (PDF).
• Chan, Timothy M. (2023), "Encontrar triángulos y otros subgrafos pequeños en grafos de intersección geométrica", en Bansal, Nikhil; Nagarajan, Viswanath (eds.), Actas del Simposio ACM-SIAM 2023 sobre algoritmos discretos, SODA 2023, Florencia, Italia, 22-25 de enero de 2023 , {SIAM}, págs. 1777–1805, arXiv : 2211.05345 , doi :10.1137/1.9781611977554.ch68
• Chiba, N.; Nishizeki, T. (1985), "Algoritmos de arboricidad y listado de subgrafos", SIAM Journal on Computing , 14 (1): 210–223, doi :10.1137/0214017, S2CID  207051803.
• Descartes, Blanche (abril de 1947), "Un problema de tres colores", Eureka , 21.
• Descartes, Blanche (1954), "Solución al problema avanzado n.° 4526", Amer. Math. Monthly , 61 : 352.
• Chvátal, Vašek (1974), "La minimalidad del grafo de Mycielski", Grafos y combinatoria (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973) , Lecture Notes in Mathematics, vol. 406, Springer-Verlag, págs. 243–246.
• Erdős, P. ; Simonovits, M. (1973), "Sobre un problema de valencia en la teoría de grafos extremales", Discrete Mathematics , 5 (4): 323–334, doi : 10.1016/0012-365X(73)90126-X.
• Erdős, P.; Suen, S.; Winkler, P. (1995), "Sobre el tamaño de un gráfico aleatorio maximal", Random Structures and Algorithms , 6 (2–3): 309–318, doi :10.1002/rsa.3240060217.
• Gimbel, John; Thomassen, Carsten (2000), "Coloración de gráficos sin triángulos con tamaño fijo", Discrete Mathematics , 219 (1–3): 275–277, doi : 10.1016/S0012-365X(00)00087-X.
• Grötzsch, H. (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 : 109-120.
• Häggkvist, R. (1981), "Ciclos impares de longitud especificada en grafos no bipartitos", Graph Theory (Cambridge, 1981), vol. 62, págs. 89–99, doi :10.1016/S0304-0208(08)73552-7.
• Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Gráficos medianos y gráficos sin triángulos", SIAM Journal on Discrete Mathematics , 12 (1): 111–118, doi :10.1137/S0895480197323494, MR  1666073, S2CID  14364050.
• Itai, A.; Rodeh, M. (1978), "Encontrar un circuito mínimo en un grafo", SIAM Journal on Computing , 7 (4): 413–423, doi :10.1137/0207033.
• Jin, Ce; Xu, Yinzhan (2023), "Eliminación de la estructura aditiva en reducciones basadas en 3SUM", en Saha, Barna; Servedio, Rocco A. (eds.), Actas del 55.º Simposio anual de la ACM sobre teoría de la computación, STOC 2023, Orlando, FL, EE. UU., 20-23 de junio de 2023 , {ACM}, págs. 405–418, arXiv : 2211.07048 , doi :10.1145/3564246.3585157, S2CID  253510334
• Jin, G. (1995), "Gráficos de cuatro cromáticos sin triángulos", Discrete Mathematics , 145 (1–3): 151–170, doi :10.1016/0012-365X(94)00063-O.
• Kim, JH (1995), "El número de Ramsey tiene un orden de magnitud ", Random Structures and Algorithms , 7 (3): 173–207, doi :10.1002/rsa.3240070302, S2CID  16658980 ${\displaystyle R(3,t)}$ ${\displaystyle {\tfrac {t^{2}}{\log t}}}$.
• Le Gall, François (octubre de 2014), "Algoritmo cuántico mejorado para la búsqueda de triángulos mediante argumentos combinatorios", Actas del 55.º Simposio anual sobre fundamentos de la informática (FOCS 2014) , IEEE, págs. 216-225, arXiv : 1407.0085 , doi : 10.1109/focs.2014.31, ISBN 978-1-4799-6517-5, Número de identificación del sujeto  5760574.
• Lee, Troy; Magniez, Frédéric; Santha, Miklos (2013), "Algoritmos de consulta cuántica mejorados para la búsqueda de triángulos y pruebas de asociatividad" , Actas del vigésimo cuarto simposio anual ACM-SIAM sobre algoritmos discretos (SODA 2013): Nueva Orleans, Luisiana, EE. UU., 6 al 8 de enero de 2013 , Association for Computing Machinery (ACM); Society for Industrial and Applied Mathematics (SIAM), págs. 1486–1502, ISBN 978-1-611972-51-1.
• Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Matemáticas. , 3 (2): 161–162, doi : 10,4064/cm-3-2-161-162.
• Nilli, A. (2000), "Gráficos sin triángulos con números cromáticos grandes", Discrete Mathematics , 211 (1–3): 261–262, doi : 10.1016/S0012-365X(99)00109-0.
• Shearer, JB (1983), "Nota sobre el número de independencia de grafos sin triángulos", Discrete Mathematics , 46 (1): 83–87, doi : 10.1016/0012-365X(83)90273-X.
• Thomassen, C. (1994), "Teorema de los tres colores de Grötzsch", Journal of Combinatorial Theory, Serie B , 62 (2): 268–279, doi : 10.1006/jctb.1994.1069.

Enlaces externos

• "Graphclass: triangle-free", Sistema de información sobre clases de grafos y sus inclusiones