Gráfico sin triángulos

Grafica sin tripletas de vértices adyacentes

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

Los gráficos sin triángulos con más aristas para sus vértices son gráficos bipartitos completos equilibrados . Muchos gráficos sin triángulos no son bipartitos, por ejemplo, cualquier gráfico de ciclo C _n para  n impar  > 3.

Según el teorema de Turán , el gráfico libre de triángulos de n -vértices con el máximo número de aristas es un gráfico bipartito completo en el que el número de vértices a cada lado de la bipartición es lo más igual posible.

Problema de búsqueda de triángulos

El problema de encontrar o detectar triángulos es el problema de determinar si una gráfica está libre de 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 gráfico con aristas está libre de triángulos en el tiempo donde oculta factores subpolinomiales y es el exponente de la multiplicación rápida de matrices . ^[1] A partir de 2023 se sabe de lo que se deduce que la detección de triángulos se puede solucionar a tiempo . Otro enfoque es encontrar la traza de A ³ , donde A es la matriz de adyacencia del gráfico. La traza es cero si y sólo si la gráfica no tiene triángulos. Para gráficos densos , es más eficiente usar este algoritmo simple que nuevamente se basa en la multiplicación de matrices, ya que reduce la complejidad del tiempo 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 }$^[update] ${\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 el tiempo, los mejores límites de tiempo que podrían esperarse de estos enfoques son o . En complejidad detallada , 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 ninguna , independientemente de las técnicas algorítmicas que se utilicen. Esto, y la correspondiente hipótesis del triángulo denso de que no es posible ningún límite temporal de la forma , implica 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^{2-\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 y no al revés.

La complejidad del árbol de decisión o complejidad de la consulta del problema, donde las consultas son a un oráculo que almacena la matriz de adyacencia de un gráfico, 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

Es fácil encontrar un conjunto independiente de vértices (donde está la función suelo ) en un gráfico sin triángulos de n vértices: o hay un vértice con al menos vecinos (en cuyo caso esos vecinos son un conjunto independiente) o todos los vértices tienen estrictamente menor que los vecinos (en cuyo caso cualquier conjunto máximo independiente debe tener al menos vértices). ^[4] Este límite se puede ajustar ligeramente: en cada gráfico sin triángulos existe un conjunto independiente de vértices, y en algunos gráficos sin triángulos cada conjunto independiente tiene vértices. ^[5] Una forma de generar gráficos sin triángulos en los que todos los conjuntos independientes son pequeños es el proceso sin triángulos ^[6] en el que se genera un gráfico sin triángulos máximo agregando repetidamente aristas elegidas al azar que no completan un triángulo. Con alta probabilidad, este proceso produce un gráfico con un número de independencia . También es posible encontrar gráficas 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 límites asintóticos de los números de Ramsey R(3, t ) de la forma : si las aristas de un gráfico completo en los vértices están coloreadas 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 gráficos sin triángulos se ha centrado en la coloración de gráficos . Todo gráfico bipartito (es decir, todo gráfico de 2 colores) no tiene triángulos, y el teorema de Grötzsch establece que todo gráfico plano sin triángulos puede tener 3 colores. ^[8] Sin embargo, los gráficos no planos sin triángulos pueden requerir muchos más de tres colores.

La primera construcción de gráficos libres de triángulos con un número cromático arbitrariamente alto se debe a Tutte (escrito como Blanche Descartes ^[9] ). Esta construcción comenzó a partir del gráfico con un solo vértice, digamos , y se construyó inductivamente de la siguiente manera: tengamos vértices, luego tomemos un conjunto de vértices y para cada subconjunto de tamaño agregue una copia disjunta y únala con una coincidencia. Del principio del casillero se deduce inductivamente que no es coloreable, ya que al menos uno de los conjuntos debe colorearse monocromáticamente si sólo se nos permite usar k colores. Mycielski (1955) definió una construcción, ahora llamada mycielskiana , para formar un nuevo gráfico sin triángulos a partir de otro gráfico sin triángulos. Si una gráfica tiene un número cromático k , su mycielskiano tiene un número cromático k  + 1, por lo que esta construcción puede usarse para mostrar que se pueden necesitar cantidades arbitrariamente grandes de colores para colorear gráficas no planas sin triángulos. En particular, el gráfico de Grötzsch , un gráfico de 11 vértices formado mediante la aplicación repetida de la construcción de Mycielski, es un gráfico sin triángulos que no se puede colorear con menos de cuatro colores y es el gráfico más pequeño con esta propiedad. ^[10] Gimbel y Thomassen (2000) y Nilli (2000) demostraron que el número de colores necesarios para colorear cualquier gráfico 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 gráficos sin triángulos que tienen números cromáticos proporcionales a este límite.

También ha habido varios resultados que relacionan la coloración al grado mínimo en gráficos sin triángulos. Andrásfai, Erdős & Sós (1974) demostraron que cualquier gráfico 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 gráfico sin triángulos de n -vértices en el que cada vértice tenga al menos n /3 vecinos puede colorearse con sólo tres colores; sin embargo, Häggkvist (1981) refutó esta conjetura al encontrar un contraejemplo en el que cada vértice del gráfico de Grötzsch es reemplazado por un conjunto independiente de un tamaño cuidadosamente elegido. Jin (1995) demostró que cualquier gráfico sin triángulos de n vértices en el que cada vértice tenga más de 10 n /29 vecinos debe tener 3 colores; este es el mejor resultado posible de este tipo, porque el gráfico de Häggkvist requiere cuatro colores y tiene exactamente 10 n /29 vecinos por vértice. Finalmente, Brandt y Thomassé (2006) demostraron que cualquier gráfico sin triángulos de n vértices en el que cada vértice tenga más de n /3 vecinos debe tener 4 colores. No es posible obtener resultados adicionales de este tipo, ya que Hajnal ^[11] encontró ejemplos de gráficos sin triángulos con un número cromático arbitrariamente grande y un grado mínimo (1/3 − ε) n para cualquier ε > 0.

Ver también

• Gráfico de Andrásfai , una familia de gráficos circulantes libres de 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úmeros cromáticos. ${\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 , en gráficas en las 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 y 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 eliminación de ciclo corto: detección de ciclo, oráculos de distancia y más", en Leonardi, Stefano; Gupta, Anupam (eds.), STOC '22: 54.º Simposio anual ACM SIGACT sobre teoría de la informática, Roma, Italia, 20 al 24 de junio de 2022, {ACM}, págs. 1487-1500, arXiv : 2204.10465 , doi : 10.1145 /3519935.3520066, S2CID  248366492
• Alón, Noga ; Ben-Shimon, Sonny; Krivelevich, Michael (2010), "Una nota sobre los gráficos regulares de Ramsey", Journal of Graph Theory , 64 (3): 244–249, arXiv : 0812.2386 , doi :10.1002/jgt.20453, MR  2674496, S2CID  1784886.
• Alón, N .; Yuster, R.; Zwick, U. (1994), "Encontrar y contar ciclos de longitud dados", Actas del segundo Simposio europeo sobre algoritmos, Utrecht, Países Bajos , págs..
• 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 gráfico" (PDF) , Matemáticas discretas , 8 (3): 205–218, doi :10.1016/0012-365X(74) 90133-2.
• Belovs, Aleksandrs (2012), "Programas de amplitud para funciones con certificados 1 de tamaño constante", Actas del cuadragésimo cuarto simposio anual de ACM sobre teoría de la informática (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, S2CID  18771464.
• Bohman, Tom (2009), "El proceso sin triángulos", Avances en Matemáticas , 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 excluyendo subgrafos", BIT , 32 (2): 180–196, doi :10.1007/BF01994876, MR  1172185, S2CID  123335474.
• Brandt, S.; Thomassé, S. (2006), Los gráficos densos sin triángulos se pueden colorear 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 gráficos de intersección geométrica", en Bansal, Nikhil; Nagarajan, Viswanath (eds.), Actas del Simposio ACM-SIAM de 2023 sobre algoritmos discretos, SODA 2023, Florencia, Italia, 22 al 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 listado de subgrafos y arboricidad", 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. Matemáticas. Mensual , 61 : 352.
• Chvátal, Vašek (1974), "La minimalidad del gráfico de Mycielski", Gráficos 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 extremos", Matemáticas discretas , 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 máximo aleatorio", Algoritmos y estructuras aleatorias , 6 (2–3): 309–318, doi :10.1002/rsa.3240060217.
• Gimbel, Juan; Thomassen, Carsten (2000), "Colorear gráficos sin triángulos con tamaño fijo", Matemáticas discretas , 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 gráficos no bipartitos", Teoría de grafos (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 de mediana y gráficos sin triángulos", Revista SIAM de Matemáticas Discretas , 12 (1): 111–118, doi :10.1137/S0895480197323494, MR  1666073, S2CID  14364050.
• Itaí, A.; Rodeh, M. (1978), "Encontrar un circuito mínimo en un gráfico", 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 ACM sobre teoría de la computación, STOC 2023, Orlando, FL, EE. UU., 20 al 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 cuatrocromáticos sin triángulos", Matemáticas discretas , 145 (1–3): 151–170, doi :10.1016/0012-365X(94)00063-O.
• Kim, JH (1995), "El número de Ramsey tiene orden de magnitud ", Algoritmos y estructuras aleatorias , 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, S2CID  5760574.
• Lee, Troya; Magniez, Federico; 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, págs. ISBN 978-1-611972-51-1{{citation}}: CS1 maint: location missing publisher (link).
• 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 grandes números cromáticos", Matemáticas discretas , 211 (1–3): 261–262, doi : 10.1016/S0012-365X(99)00109-0.
• Shearer, JB (1983), "Nota sobre el número de independencia de gráficas sin triángulos", Matemáticas discretas , 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