Yo soy un físico, así que disculpas de antemano por cualquier confuso notación o terminología; yo estaremos contentos de aclarar. Para proporcionar una cantidad mínima de contexto, el gráfico siguiente polinomio apareció en mi investigación en una clase de cuántico de espín de los modelos con ${\rm SU}(N)$ simetría. Parece probable que me este polinomio es conocido, tal vez incluyendo los resultados útil para mis propósitos, pero no he sido capaz de encontrar la información pertinente.
Considere la posibilidad de conexión de un simple gráfico de $G$ con $n$ vértices y $m$ bordes. La vista de cada borde de la $\ell$ como una transposición $t_{\ell}$ que actúa sobre el conjunto de vértices. [Para ser más explícitos, dada una arista $\ell$ uniendo los vértices $v_1$ y $v_2$, $t_{\ell}$ es una permutación intercambio de $v_1$ e $v_2$, dejando a todos los demás vértices fijos.] Deje ${\cal L}$ el conjunto de ordenadas $m$-tuplas de los bordes, de modo que los elementos de la ${\cal L}$ son de la forma $L = (\ell_1, \dots, \ell_m)$, con cada borde que aparece exactamente una vez.
Para cada una de las $L \in {\cal L}$ podemos asociar una permutación $\pi(L) \in S_n$ por tomar el producto de transposiciones, \begin{equation} \pi[(\ell_1, \dots, \ell_m)] = t_{\ell_1} t_{\ell_2} \cdots t_{\ell_m}. \end{equation}
Para $\pi \in S_n$, vamos a $c(\pi)$ el número de ciclos en los que el ciclo de descomposición, contando 1-ciclos. Así, por ejemplo,$c(1) = n$, e $c(\pi) = 1$ para $\pi$ una $n$-ciclo. Entonces podemos definir el polinomio de interés: \begin{equation} X(N) = \sum_{L \in {\cal L}} N^{c[\pi(L)]} \text{.} \end{equation}
Mi pregunta principal es si un eficiente (en términos prácticos), el procedimiento es conocido para calcular $X(N)$, ya sea para grafos arbitrarios, o para ciertas familias de grafos. En mi aplicación, necesito calcular $X(N)$ para todos los gráficos que se subdiagramas de una red regular, hasta algunos máximo número de aristas (que me gustaría hacer tan grande como sea posible). En particular, estoy enfocado en la plaza de celosía (por ahora), lo que restringe a bipartita de grafos planares. Quizás también relevante, en mi aplicación de bordes paralelos son permitidos, pero me he concentrado en gráficas sencillas aquí por motivos de simplicidad.
Ya sé $X(N) = m! N$ si $G$ es un árbol, y $X(N) = m! N^2$ si $G$ es un ciclo. Además, la eliminación de todos los puentes de $G$, hay una fórmula sencilla de dar a $X(N)$ como producto de la $X(N)$'s de las piezas resultantes, multiplicado por un factor general. Más allá de esto, hasta ahora lo mejor que puedo hacer es tomar una aproximación de fuerza bruta.
Más allá de mi pregunta principal, también estoy más en general interesados en aprender lo que, si nada se sabe acerca de este polinomio. Por ejemplo, hay referencias de donde $X(N)$ es objeto de estudio, es $X(N)$ relacionadas con otras (quizás mejor conocido) gráfica de polinomios, etc.?
