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 se esconden factores subpolinomiales. 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 a tiempo . Otro enfoque es encontrar la traza de A 3 , 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.
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]
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.
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]
Estos resultados también pueden interpretarse como límites asintóticos de 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.
Colorear gráficos sin triángulos
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 por 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
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.
^ Abboud y otros. (2022); Chan (2023); Jin y Xu (2023)
^ Le Gall (2014), mejorando algoritmos anteriores de Lee, Magniez & Santha (2013) y Belovs (2012).
^ Boppana y Halldórsson (1992) p. 184, basado en una idea de un algoritmo de aproximación de coloración anterior de Avi Wigderson .
^ Kim (1995).
^ Erdős, Suen y Winkler (1995); Bohman (2009).
^ Alon, Ben-Shimon y Krivelevich (2010).
^ Grötzsch (1959); Thomassen (1994)).
^ Descartes (1947); Descartes (1954)
^ Chvátal (1974).
^ 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.
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 abarcados 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
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.
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, EE. UU., 6 al 8 de enero , 2013 , Asociación de Maquinaria de Computación (ACM); Sociedad de Matemáticas Industriales y Aplicadas (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 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.