Polinomio de correspondencia

En los campos matemáticos de la teoría de grafos y la combinatoria , un polinomio de emparejamiento (a veces llamado polinomio acíclico ) es una función generadora del número de emparejamientos de distintos tamaños en un grafo. Es uno de los diversos polinomios de grafos que se estudian en la teoría algebraica de grafos .

Se han definido varios tipos diferentes de polinomios de emparejamiento. Sea G un grafo con n vértices y sea m _k el número de emparejamientos de k aristas.

Un polinomio correspondiente de G es $${\displaystyle m_{G}(x):=\sum _{k\geq 0}m_{k}x^{k}.}$$

Otra definición da como resultado el polinomio correspondiente $${\displaystyle M_{G}(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}.}$$

Una tercera definición es el polinomio $${\displaystyle \mu _{G}(x,y):=\sum _{k\geq 0}m_{k}x^{k}y^{n-2k}.}$$

Cada tipo tiene sus usos, y todos son equivalentes mediante transformaciones simples. Por ejemplo, $${\displaystyle M_{G}(x)=x^{n}m_{G}(-x^{-2})}$$ y $${\displaystyle \mu _{G}(x,y)=y^{n}m_{G}(x/y^{2}).}$$

El primer tipo de polinomio de emparejamiento es una generalización directa del polinomio de la torre .

El segundo tipo de polinomio de emparejamiento tiene conexiones notables con los polinomios ortogonales . Por ejemplo, si G  = K _{m , n} , el grafo bipartito completo , entonces el segundo tipo de polinomio de emparejamiento está relacionado con el polinomio de Laguerre generalizado L _n ^α ( x ) mediante la identidad: 

$${\displaystyle M_{K_{m,n}}(x)=n!L_{n}^{(mn)}(x^{2}).}$$

Si G es el grafo completo K _n , entonces M _G ( x ) es un polinomio de Hermite: $${\displaystyle M_{K_{n}}(x)=H_{n}(x),}$$ donde H _n ( x ) es el "polinomio de Hermite probabilístico" (1) en la definición de polinomios de Hermite . Estos hechos fueron observados por Godsil (1981) .

Si G es un bosque , entonces su polinomio de emparejamiento es igual al polinomio característico de su matriz de adyacencia .

Si G es un camino o un ciclo , entonces M _G ( x ) es un polinomio de Chebyshev . En este caso, μ _G (1, x ) es un polinomio de Fibonacci o un polinomio de Lucas , respectivamente.

El polinomio correspondiente de un grafo G con n vértices está relacionado con el de su complemento mediante un par de fórmulas (equivalentes). Una de ellas es una identidad combinatoria simple debida a Zaslavsky (1981) . La otra es una identidad integral debida a Godsil (1981) .

Existe una relación similar para un subgrafo G de K _{m , n} y su complemento en K _{m , n} . Esta relación, debida a Riordan (1958), era conocida en el contexto de colocaciones de torres no atacantes y polinomios de torres.

El índice de Hosoya de un grafo G , su número de coincidencias, se utiliza en quimioinformática como descriptor estructural de un grafo molecular. Puede evaluarse como m _G (1) ( Gutman 1991 ) .

El tercer tipo de polinomio de coincidencia fue introducido por Farrell (1980) como una versión del "polinomio acíclico" utilizado en química .

En grafos arbitrarios, o incluso en grafos planares , el cálculo del polinomio de emparejamiento es #P-completo ( Jerrum 1987 ) . Sin embargo, puede calcularse de manera más eficiente cuando se conoce la estructura adicional del grafo. En particular, el cálculo del polinomio de emparejamiento en grafos de n vértices con ancho de árbol k es tratable con parámetros fijos : existe un algoritmo cuyo tiempo de ejecución, para cualquier constante fija k , es un polinomio en n con un exponente que no depende de k ( Courcelle, Makowsky y Rotics 2001 ) . El polinomio de emparejamiento de un grafo con n vértices y ancho de clique k puede calcularse en tiempo n ^{O( k )} ( Makowsky et al. 2006 ) .

• Courcelle, B .; Makowsky, JA; Rotics, U. (2001), "Sobre la complejidad de parámetros fijos de los problemas de enumeración de grafos definibles en lógica monádica de segundo orden" (PDF) , Discrete Applied Mathematics , 108 ( 1–2 ): 23–52 , doi : 10.1016/S0166-218X(00)00221-3.
• Farrell, EJ ( 1980), "El polinomio de emparejamiento y su relación con el polinomio acíclico de un grafo", Ars Combinatoria , 9 : 221–228.
• Godsil, CD (1981), "Polinomios de Hermite y una relación de dualidad para polinomios de emparejamiento", Combinatorica , 1 (3): 257– 262, doi : 10.1007/BF02579331.
• Gutman, Ivan (1991), "Polinomios en la teoría de grafos", en Bonchev, D.; Rouvray, DH (eds.), Teoría química de grafos: Introducción y fundamentos , Química matemática, vol.  1, Taylor & Francis, pp. 133–176 , ISBN  978-0-85626-454-2.
• Jerrum, Mark (1987), "Los sistemas monoméricos-dímeros bidimensionales son computacionalmente intratables", Journal of Statistical Physics , 48 ​​(1): 121– 134, Bibcode : 1987JSP....48..121J , doi : 10.1007/BF01010403.
• Makowsky, JA; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Cálculo de polinomios de grafos en grafos de ancho de clique acotado", Actas del 32.º Taller Internacional sobre Conceptos de Teoría de Grafos en Ciencias de la Computación (WG '06) (PDF) , Lecture Notes in Computer Science, vol.  4271, Springer-Verlag, pp. 191–204 , doi : 10.1007/11917496_18 , ISBN  978-3-540-48381-6Archivado desde el original (PDF) el 24/06/2021 , consultado el 15/09/2019..
• Riordan, John (1958), Introducción al análisis combinatorio , Nueva York: Wiley.
• Zaslavsky, Thomas (1981), "Vectores de emparejamiento complementarios y la propiedad de extensión de emparejamiento uniforme", European Journal of Combinatorics , 2 : 91–103 , doi : 10.1016/s0195-6698(81)80025-x.