En el campo matemático de la teoría de grafos , un gráfico representable por palabras es un gráfico que puede caracterizarse por una palabra (o secuencia) cuyas entradas se alternan de una manera prescrita. En particular, si el conjunto de vértices del gráfico es V , uno debería poder elegir una palabra w en lugar del alfabeto V tal que las letras a y b se alternen en w si y solo si el par ab es una arista en el gráfico. (Las letras a y b se alternan en w si, después de eliminar de w todas las letras excepto las copias de a y b , se obtiene una palabra abab ... o una palabra baba ...) Por ejemplo, el gráfico de ciclo etiquetado por a , b , cyd en el sentido de las agujas del reloj es representable con palabras porque puede representarse mediante abdacdbc : los pares ab , bc , cd y ad se alternan, pero los pares ac y bd no .
La palabra w es la palabra representativa de G , y se dice que w representa G. El gráfico más pequeño (por el número de vértices) que no se puede representar con palabras es el gráfico de rueda W 5 , que es el único gráfico que no se puede representar con palabras en 6 vértices.
La definición de un gráfico representable por palabras funciona tanto en casos etiquetados como sin etiquetar, ya que cualquier etiquetado de un gráfico es equivalente a cualquier otro etiquetado. Además, la clase de gráficos representables por palabras es hereditaria . Los gráficos representables en palabras generalizan varias clases importantes de gráficos, como los gráficos circulares , los gráficos de 3 colores y los gráficos de comparabilidad . Varias generalizaciones de la teoría de gráficos representables con palabras se adaptan a la representación de cualquier gráfico.
Sergey Kitaev [1] introdujo los gráficos representables por palabras en 2004 basándose en una investigación conjunta con Steven Seif [2] sobre el semigrupo de Perkins , que ha desempeñado un papel importante en la teoría de semigrupos desde 1960. [3] El primer estudio sistemático de palabras -Los gráficos representables se llevaron a cabo en un artículo de 2008 de Kitaev y Artem Pyatkin, [4] iniciando el desarrollo de la teoría. Uno de los contribuyentes clave al área es Magnús M. Halldórsson. [5] [6] [7] Hasta la fecha, se han escrito más de 35 artículos sobre el tema, y el núcleo del libro [3] de Sergey Kitaev y Vadim Lozin está dedicado a la teoría de gráficos representables con palabras. Una forma rápida de familiarizarse con el área es leer uno de los artículos de la encuesta. [8] [9] [10]
Según [3] , los gráficos representables con palabras son relevantes para varios campos, lo que motiva a estudiar los gráficos. Estos campos son álgebra , teoría de grafos , informática , combinatoria de palabras y programación . Los gráficos representables con palabras son especialmente importantes en la teoría de grafos, ya que generalizan varias clases importantes de gráficos, por ejemplo, gráficos circulares , gráficos de 3 colores y gráficos de comparabilidad .
En [4] se demostró que un gráfico G es representable en palabras si es k-representable para alguna k , es decir, G puede representarse mediante una palabra que tenga k copias de cada letra. Además, si un gráfico es k -representable, entonces también es ( k + 1) -representable. Por tanto, la noción de número de representación de un gráfico , como el mínimo k tal que un gráfico sea representable con palabras, está bien definida. Los gráficos que no se pueden representar con palabras tienen el número de representación ∞. Las gráficas con número de representación 1 son precisamente el conjunto de gráficas completas , mientras que las gráficas con número de representación 2 son precisamente la clase de gráficas circulares no completas. En particular, los bosques (excepto los árboles individuales en como máximo 2 vértices), los gráficos de escalera y los gráficos de ciclo tienen el número de representación 2. No se conoce ninguna clasificación para los gráficos con el número de representación 3. Sin embargo, existen ejemplos de este tipo de gráficos, por ejemplo, el gráfico de Petersen y los prismas. Además, la subdivisión en 3 de cualquier gráfico es representable en 3. En particular, para cada gráfico G existe un gráfico H de 3 representables que contiene a G como menor . [4]
Un gráfico G es representable permutacionalmente si puede representarse mediante una palabra de la forma p 1 p 2 ... p k , donde p i es una permutación . On también puede decir que G es permutacionalmente k -representable . Un gráfico es representable permutacionalmente si es un gráfico de comparabilidad . [2] Un gráfico representable mediante palabras implica que la vecindad de cada vértice es representable permutacionalmente (es decir, es un gráfico de comparabilidad ). [2] Lo contrario de la última afirmación no es cierta. [5] Sin embargo, el hecho de que la vecindad de cada vértice sea un gráfico de comparabilidad implica que el problema de la camarilla máxima se puede resolver polinomialmente en gráficos representables con palabras. [6] [7]
Las orientaciones semitransitivas proporcionan una herramienta poderosa para estudiar gráficos representables con palabras. Un gráfico dirigido está orientado semitransitivamente si y solo es acíclico y para cualquier camino dirigido u 1 → u 2 → ...→ u t , t ≥ 2, o no hay aristas de u 1 a u t o todas las aristas u i → u j existe para 1 ≤ i < j ≤ t . Un teorema clave en la teoría de los gráficos representables con palabras establece que un gráfico es representable con palabras si admite una orientación semitransitiva. [7] Como corolario de la prueba del teorema clave, se obtiene un límite superior para los representativos de palabras: cada gráfico G incompleto representable con palabras es 2( n − κ ( G )) -representable, donde κ ( G ) es el tamaño de una camarilla máxima en G . [7] Como corolario inmediato de la última afirmación, uno tiene que el problema de reconocimiento de la representabilidad de las palabras está en NP . En 2014, Vincent Limouzy observó que reconocer si un gráfico determinado es representable con palabras es un problema NP-completo . [3] [8] Otro corolario importante del teorema clave es que cualquier gráfico de 3 colores es representable con palabras. El último hecho implica que muchos problemas de gráficos clásicos son NP-difíciles en gráficos representables con palabras.
Los gráficos de rueda W 2 n +1 , para n ≥ 2, no son representables con palabras y W 5 es el gráfico mínimo (por el número de vértices) no representable con palabras. Tomando cualquier gráfico de no comparabilidad y agregando un vértice (un vértice conectado a cualquier otro vértice), obtenemos un gráfico no representable con palabras, que luego puede producir infinitos gráficos no representables con palabras. [3] Cualquier gráfico producido de esta manera tendrá necesariamente un triángulo (un ciclo de longitud 3) y un vértice de grado al menos 5. Existen gráficos no representables con palabras de grado máximo 4 [11] y gráficos sin palabras. Existen gráficos representables sin triángulos. [6] También existen gráficos regulares representables sin palabras. [3] Heman ZQ Chen enumeró por primera vez los gráficos conectados no isomorfos y no representables con palabras en un máximo de ocho vértices. Sus cálculos se ampliaron en [12] , donde se demostró que los números de gráficos conectados no isomorfos y no representables con palabras en 5-11 vértices están dados, respectivamente, por 0, 1, 25, 929, 54957, 4880093, 650856040. Esta es la secuencia A290814 en la Enciclopedia en línea de secuencias enteras (OEIS).
Las operaciones que preservan la representabilidad de las palabras son eliminar un vértice, reemplazar un vértice con un módulo, producto cartesiano, producto raíz, subdivisión de un gráfico, conectar dos gráficos por un borde y pegar dos gráficos en un vértice. [3] Las operaciones que no necesariamente preservan la representabilidad de la palabra son tomar el complemento, tomar el gráfico lineal, contracción de bordes, [3] pegar dos gráficos en una camarilla de tamaño 2 o más, [13] producto tensorial, producto lexicográfico y producto fuerte. . [14] La eliminación de bordes, la adición de bordes y el levantamiento de bordes con respecto a la representabilidad de palabras (equivalentemente, orientabilidad semitransitiva) se estudian en. [14]
Si bien cada gráfico G representable con palabras no completo es representable 2( n − κ ( G )), donde κ ( G ) es el tamaño de una camarilla máxima en G , [7] el número de representación más alto conocido es piso ( n /2) dado por gráficos de corona con un vértice totalmente adyacente. [7] Curiosamente, estos gráficos no son los únicos que requieren representaciones largas. [15] Se ha demostrado que los propios gráficos de corona requieren representaciones largas (posiblemente más largas) entre los gráficos bipartitos. [dieciséis]
Las complejidades computacionales conocidas para problemas en gráficos representables con palabras se pueden resumir de la siguiente manera: [3] [8]
Los gráficos planos sin triángulos se pueden representar con palabras. [7] Una casi triangulación libre de K4 es de 3 colores si y sólo si es representable por palabras; [17] este resultado generaliza los estudios en. [18] [19] La representabilidad de palabras de las subdivisiones de caras de gráficos de cuadrícula triangular se estudia en [20] y la representabilidad de palabras de triangulaciones de gráficos de cilindros cubiertos de cuadrícula se estudia en. [21]
La representación de palabras de gráficos divididos se estudia en. [22] [13] En particular, [22] ofrece una caracterización en términos de subgrafos inducidos prohibidos de gráficos divididos representables por palabras en los que los vértices en el conjunto independiente son de grado como máximo 2 , o el tamaño de la camarilla es 4, mientras que en [13] se proporciona una caracterización computacional de gráficos divididos representables por palabras con la camarilla de tamaño 5. Además, las condiciones necesarias y suficientes para que la orientación de un gráfico dividido sea semi- transitivos se dan en [22] , mientras que en [13] se muestra que los gráficos de umbral son representables por palabras y los gráficos divididos se usan para mostrar que pegar dos gráficos representables por palabras en cualquier camarilla de tamaño al menos 2 puede o no dio como resultado un gráfico representable con palabras, que resolvió un problema abierto de larga data.
Un gráfico es p -representable si puede representarse mediante una palabra que evite un patrón p . Por ejemplo, los gráficos de 132 representables son aquellos que se pueden representar con palabras w 1 w 2 ... w n donde no hay 1 ≤ a < b < c ≤ n tales que w a < w c < w b . En [23] se muestra que cualquier gráfico representable en 132 es necesariamente un gráfico circular , y cualquier gráfico de árbol y de ciclo , así como cualquier gráfico en como máximo 5 vértices, son representables en 132. En [24] se demostró que no todos los gráficos circulares son representables en 132 y que los gráficos representables en 123 también son una subclase adecuada de la clase de gráficos circulares.
Varias generalizaciones [25] [26] [27] de la noción de gráfico representable con palabras se basan en la observación de Jeff Remmel de que los no bordes se definen por apariciones del patrón 11 (dos letras iguales consecutivas) en un palabra que representa un gráfico, mientras que los bordes se definen evitando este patrón. Por ejemplo, en lugar del patrón 11, se puede usar el patrón 112, o el patrón 1212, o cualquier otro patrón binario en el que se pueda asumir que el alfabeto está ordenado de modo que una letra en una palabra correspondiente a 1 en la patrón es menor que el correspondiente a 2 en el patrón. Dejando que u sea un patrón binario ordenado, obtenemos la noción de un gráfico representable en u . Entonces, los gráficos representables con palabras son solo la clase de gráficos representables con 11 palabras. Curiosamente, cualquier gráfico puede representarse con u suponiendo que u tenga una longitud de al menos 3. [28]
Otra forma de generalizar la noción de un gráfico representable con palabras, nuevamente sugerida por Remmel, es introducir el "grado de tolerancia" k para las apariciones de un patrón p que define aristas/no aristas. Es decir, podemos decir que si hay hasta k ocurrencias de p formadas por las letras a y b , entonces hay una arista entre a y b . Esto da la noción de un gráfico representable k - p , y se estudian gráficos representables k -11. [29] Tenga en cuenta que los gráficos representables 0-11 son gráficos representables precisamente con palabras. Los resultados clave en [29] son que cualquier gráfico es representable 2-11 y que los gráficos representables con palabras son una subclase adecuada de los gráficos representables 1-11. Si un gráfico es o no representable 1-11 es un problema abierto desafiante.
Para otro tipo de generalización relevante, Hans Zantema sugirió la noción de k -orientación semitransitiva refinando la noción de orientación semitransitiva. [15] La idea aquí es limitarnos a considerar solo caminos dirigidos de longitud que no exceda k mientras permitimos violaciones de la semitransitividad en caminos más largos.
Los problemas abiertos sobre gráficos representables con palabras se pueden encontrar en [3] [8] [9] [10] e incluyen:
La lista de publicaciones para estudiar la representación de gráficos por palabras contiene, entre otras,
El software para estudiar gráficos representables con palabras se puede encontrar aquí: