La esencia de esta respuesta está contenida en la respuesta de reuns, pero esa respuesta, por desgracia, también contiene algunas afirmaciones incorrectas sobre la naturaleza y la finitud de los primos en los grafos.
Las respuestas en el enlace en tu pregunta original también son relevantes: una función de Möbius puede definirse siempre que tengas un conjunto parcialmente ordenado. En particular, la función de Möbius de la teoría de los números está estrechamente relacionada con la función de Möbius del ordenación parcial de los subconjuntos finitos de un subconjunto, ordenados por inclusión y también lo es la función de Möbius para la función zeta de Ihara.
En el contexto de la teoría de números, como consecuencia de la factorización única, cualquier entero positivo $n$ puede identificarse con el subconjunto de sus factores primos. Así que $1$ se identifica con $\{\}$ , $2$ con $\{2\}$ , $4$ con $\{2,2\}$ , $12$ con $\{2,2,3\}$ y así sucesivamente. La función de Möbius de la teoría de números, considerada como una función de un conjunto múltiple $M$ de los primos, es entonces $$ \mu(M)=\begin{cases}0 & \text{if $M$ contains any element more than once,}\\ 1 & \text{if $M$ contains an even number of elements, all distinct,}\\ -1 & \text{if $M$ contains an odd number of elements, all distinct.} \end{cases} $$
Se puede hacer exactamente lo mismo en el contexto de los gráficos. Los análogos de la teoría de grafos de los enteros $n$ son los conjuntos múltiples, $M$ cuyos elementos son clases de equivalencia de circuitos primos. De esto se deduce que $$ \sum_M u^{L(M)}\mu(M)=\prod_p \left(1-u^{L(p)}\right)=\frac{1}{\zeta_G(u)}, $$ donde $L(M)$ es la suma de las longitudes de los elementos de $M$ . Nótese que si el gráfico tiene al menos dos circuitos, entonces tiene infinitos circuitos primos. Los elementos de $M$ no tienen por qué cruzarse, por lo que no se puede suponer que puedan concatenarse para formar un único circuito. Además, los elementos de $M$ son clases de equivalencia de circuitos primos, por lo que no habría ningún punto de concatenación especificado de forma única, incluso cuando se cruzan. Esto significa que los conjuntos múltiples $M$ no puede identificarse directamente con algo tan simple como los circuitos en el gráfico.
Para responder a tu pregunta sobre qué ocurre cuando un vértice aparece más de una vez, es perfectamente posible tener $\mu(M)\ne0$ en esta situación: diferentes primos pueden contener el mismo vértice. Incluso, diferentes primos pueden contener todos los mismos vértices. Como ejemplo sencillo, si $p$ es un circuito primo, entonces atravesando las aristas de $p$ en el orden inverso da un circuito primo diferente.
Añadido en respuesta al comentario sobre la finitud del número de términos en $1/\zeta_G(u)$ :
De las fórmulas determinantes de Ihara, Sunada, Hashimoto y Bass se desprende que $1/\zeta_G(u)$ es efectivamente un polinomio en $u$ , pero eso no significa que la suma $\sum_Mu^{L(M)}\mu(M)$ sólo tiene un número finito de términos no nulos. Sólo significa que hay cancelaciones. Por supuesto, se da el caso de que hay muchos $M$ para lo cual $\mu(M)=0$ , es decir, aquellos $M$ que contienen algún primo más de una vez. Pero también hay infinitas $M$ para lo cual $\mu(M)=\pm1$ . Del mismo modo, en la forma de producto $$ \frac{1}{\zeta_G(u)}=\prod_p \left(1-u^{L(p)}\right) $$ el producto no contiene sólo un número finito de factores.
Revisando un ejemplo de un anterior hilo de comentarios , considere el $4$ -grafo regular con un vértice y dos bucles. Este grafo tiene una matriz de adyacencia $A_G=\begin{bmatrix}4\end{bmatrix}$ . A partir de la fórmula del determinante Ihara-Sunada-Bass, $$ \frac{1}{\zeta_G(u)}=(1-u^2)^{r_G-1}\det(I-uA_G+u^2Q_G),\tag{1} $$ donde $r_G$ es el rango del circuito del gráfico y $Q_G$ es la matriz diagonal cuyo $(i,i)$ elemento es $\deg(\text{vertex $ i $})-1$ se obtiene $$ \frac{1}{\zeta_G(u)}=(1-u^2)(1-4u+3u^2)=1-4u+2u^2+4u^3-3u^4 $$ para este gráfico. Ya sea por enumeración de fuerza bruta, o por el método de la matriz de aristas que se describe a continuación, se calcula el número de clases de equivalencia de los paseos cerrados primitivos, sin retroceso, de una longitud determinada. $$ \begin{array}{l|ccccccccccc} \text{length} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline \text{classes} & 4 & 4 & 8 & 18 & 48 & 116 & 312 & 810 & 2184 & 5880 & 16104 \end{array} $$ Evaluar el producto $$ \begin{aligned}&(1-u)^4(1-u^2)^4(1-u^3)^8(1-u^4)^{18}(1-u^5)^{48}(1-u^6)^{116}(1-u^7)^{312}\\ &\quad\times(1-u^8)^{810}(1-u^9)^{2184}(1-u^{10})^{5880}(1-u^{11})^{16104}\ ,\end{aligned} $$ se encuentra que es igual a $(1-u^2)(1-4u+3u^2)+O(u^{12})$ . A medida que se aumenta el número de factores en el producto, se puede hacer que éste difiera del polinomio por una expresión proporcional a una potencia arbitrariamente alta de $u$ . Como el polinomio tiene raíces en $-1$ , $1$ et $\frac{1}{3}$ también debería ser posible demostrar que el producto converge para todo $\lvert u\rvert<\frac{1}{3}$ .
Pasando a la forma de suma que da la inversión de Möbius, veremos que la desaparición de los coeficientes de las potencias de $u$ mayor que $4$ se produce por la cancelación, y no por la desaparición de todos los $\mu(M)$ . Utilizando el coeficiente de $u^5$ como ejemplo, necesitamos encontrar todas las formas de formar un conjunto múltiple de clases de equivalencia de paseos primos tal que la suma de las longitudes sea $5$ . Una forma es que $M$ para contener una única clase de equivalencia de longitud- $5$ camina, en cuyo caso hay una contribución de $\mu(M)=-1$ a la suma. El cuadro anterior muestra que hay $48$ tales clases de equivalencia. Otra forma es que $M$ para consistir en una clase de longitud- $4$ y una clase de longitud- $1$ paseos, o de clase de longitud- $3$ y una clase de longitud- $2$ camina. Una tercera forma es que $M$ para consistir en una clase de longitud- $3$ y dos clases de longitud- $1$ paseos, o de dos clases de longitud- $2$ y una clase de longitud- $1$ paseos. Una última forma es que $M$ para consistir en una clase de longitud- $2$ paseos y tres clases de longitud- $1$ camina. (Si $M$ consta de cinco clases de longitud- $1$ camina entonces $\mu(M)$ siempre es igual a $0$ ya que sólo hay cuatro clases diferentes de longitud- $1$ camina y por lo tanto $M$ debe contener al menos una clase dos veces).
Utilizando los números de clases de equivalencia de la tabla anterior, y omitiendo las contribuciones con $\mu(M)=0$ encontramos que el coeficiente de $u^5$ es $$ -48+18\cdot4+8\cdot4-8\cdot\binom{4}{2}-\binom{4}{2}\cdot4+4\cdot\binom{4}{3}=-48+72+32-48-24+16=0. $$
La siguiente tabla resume todas las contribuciones no nulas a los términos hasta $u^5$ . La notación de los paseos que figuran en el $M$ se explica a continuación. $$ \begin{array}{c|l|c|c|c} L(M) & M & \mu(M) & \text{subtotal} & \text{total}\\ \hline 0 & \{\} & 1 & 1 & 1\\ \hline 1 & \{1\},\{\bar{1}\},\{2\},\{\bar{2}\} & -1 & -4 & -4\\ \hline 2 & \{12\},\{1\bar{2}\},\{\bar{1}2\},\{\bar{1}\bar{2}\} & -1 & -4 & \\ & \{1,\bar{1}\},\{1,2\},\{1,\bar{2}\},\{\bar{1},2\},\{\bar{1},\bar{2}\},\{2,\bar{2}\} & 1 & \binom{4}{2} & 2\\ \hline 3 & \{112\},\{11\bar{2}\},\{122\},\{1\bar{2}\bar{2}\},\{\bar{1}\bar{1}2\},\{\bar{1}\bar{1}\bar{2}\},\{\bar{1}22\},\{\bar{1}\bar{2}\bar{2}\} & -1 & -8 & \\ & \{1,12\},\{1,1\bar{2}\},\ldots\{\bar{2},\bar{1}\bar{2}\} & 1 & 4\cdot4 & \\ & \{\bar{1},2,\bar{2}\},\{1,2,\bar{2}\},\{1,\bar{1},\bar{2}\},\{1,\bar{1},2\} & -1 & -\binom{4}{3} & 4\\ \hline 4 & \{1112\},\{111\bar{2}\},\ldots, & -1 & -18 & \\ & \{1,112\},\{1,11\bar{2}\},\ldots & 1 & 4\cdot8 & \\ & \{12,1\bar{2}\},\{12,\bar{1}2\},\ldots & 1 & \binom{4}{2} & \\ & \{1,\bar{1},12\},\{1,\bar{1},1\bar{2}\},\ldots & -1 & -\binom{4}{2}\cdot4 & \\ & \{1,\bar{1},2,\bar{2}\} & 1 & \binom{4}{4} & -3\\ \hline 5 & \{11112\},\{1111\bar{2}\},\ldots & -1 & -48 & \\ & \{1,1112\},\{1,111\bar{2}\},\ldots & 1 & 4\cdot18 & \\ & \{12,112\},\{12,11\bar{2}\},\ldots & 1 & 4\cdot8 & \\ & \{1,12,1\bar{2}\},\{1,12,\bar{1}2\},\ldots & -1 & -4\cdot\binom{4}{2} & \\ & \{1,\bar{1},112\},\{1,\bar{1},11\bar{2}\},\ldots & -1 & -\binom{4}{2}\cdot8 & \\ & \{1,\bar{1},2,12\},\{1,\bar{1},2,1\bar{2}\},\ldots & 1 & \binom{4}{3}\cdot4 & 0\\ \end{array} $$
Enumeración de clases de equivalencia de paseos primos. A continuación, se explica cómo se han calculado los números de las clases de equivalencia de los paseos cerrados primitivos y sin retroceso. Etiquete uno de los bucles en el gráfico $1$ y el otro $2$ . Los bucles pueden ser atravesados en cualquier dirección, por lo que elegimos arbitrariamente una de las direcciones de cada bucle para que sea la dirección de avance, y denotamos las direcciones inversas $\bar{1}$ y $\bar{2}$ . Dos paseos cerrados, escritos como palabras en el alfabeto $\{1,\bar{1},2,\bar{2}\}$ son equivalentes si son desplazamientos cíclicos entre sí. Una palabra es no primitiva si es igual a un desplazamiento cíclico no nulo de sí misma. Para que no haya retroceso, las letras $1$ y $\bar{1}$ no pueden ser adyacentes, con una restricción similar en las letras $2$ y $\bar{2}$ . Así que los paseos de longitud $1$ son $1$ , $\bar{1}$ , $2$ , $\bar{2}$ y los paseos de longitud $2$ son $12$ , $1\bar{2}$ , $\bar{1}2$ , $\bar{1}\bar{2}$ .
Para la longitud tres, los paseos son de la forma $aab$ o $abb$ , donde $a\in\{1,\bar{1}\}$ y $b\in\{2,\bar{2}\}$ , lo que implica ocho paseos. Para la longitud cuatro, tenemos las formas $aaab$ , $aabb$ , $abbb$ , dando $12$ paseos y, además, paseos de la forma $aba'b'$ , donde $a,a'\in\{1,\bar{1}\}$ , $b,b'\in\{2,\bar{2}\}$ , $a'$ es posiblemente igual a $a$ et $b'$ es posiblemente igual a $b$ . Esto último parece producir $16$ paseos, pero algunos están prohibidos y otros son equivalentes a otros. Los paseos no permitidos son los de la forma $abab$ ya que no son primitivos. Esto elimina $2\cdot2=4$ paseos. Los ocho paseos restantes satisfacen las equivalencias $$ \begin{aligned} 121\bar{2}&\sim1\bar{2}12,\\ 12\bar{1}2&\sim\bar{1}212,\\ 12\bar{1}\bar{2}&\sim\bar{1}\bar{2}12,\\ 1\bar{2}\bar{1}2&\sim\bar{1}21\bar{2},\\ 1\bar{2}\bar{1}\bar{2}&\sim\bar{1}\bar{2}1\bar{2},\\ \bar{1}2\bar{1}\bar{2}&\sim\bar{1}\bar{2}\bar{1}2. \end{aligned} $$ Por lo tanto, hay $(16-4)/2=6$ clases de equivalencia. En total hay $12+6=18$ clases. Para longitudes superiores a cuatro, los números de las clases de equivalencia se obtuvieron inicialmente por enumeración exhaustiva en un ordenador.
Sin embargo, un método mejor es utilizar la matriz de adyacencia de aristas de Hashimoto, que se denomina $0,1$ matriz de bordes $W_1$ en la definición 2.2 de ¿Qué son las funciones zeta de los gráficos y para qué sirven? por Matthew D. Horton, H. M. Stark y Audrey A. Terras. En primer lugar, enumeramos el número de paseos cerrados sin seguimiento. Sea $$ W_1=\begin{bmatrix}1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0\\ 1 & 1 & 0 & 1\end{bmatrix}, $$ donde las filas y las columnas están indexadas por las letras $1$ , $\bar{1}$ , $2$ , $\bar{2}$ . (Esta matriz se llamó $B$ en el anterior hilo de comentarios .) El número de paseos cerrados sin retroceso (palabras cíclicas con $\bar{1}$ nunca adyacente a $1$ y $\bar{2}$ nunca adyacente a $2$ ) de longitud $\ell$ es entonces $\mathrm{Tr}\,W_1^\ell=\sum \lambda_j^\ell$ , donde $\lambda_j$ son los valores propios de $W_1$ , a saber $3$ , $1$ , $1$ , $-1$ . El resultado es $3^\ell+2+(-1)^\ell$ .
El requisito de que nuestros paseos cerrados sin retroceso sean primitivos puede imponerse utilizando la inversión de Möbius. Sea $\phi(\ell)$ sea el número de paseos cerrados primitivos, sin retroceso. Entonces $\sum_{d\mid \ell}\phi(d)=3^\ell+2+(-1)^\ell$ . La fórmula de inversión de Möbius implica entonces que $\phi(\ell)=\sum_{d\mid\ell}\mu(\ell/d)(3^d+2+(-1)^d)$ . Dado que las clases de equivalencia de las primitivas, sin retroceso de longitud- $\ell$ los paseos contienen $\ell$ elementos, el número de clases de equivalencia de longitudes cerradas primitivas y sin retroceso $\ell$ paseos es $\phi(\ell)/\ell$ . Se puede comprobar que esto reproduce la secuencia $4$ , $4$ , $8$ , $18$ , $48$ , $116$ , $312$ , $\ldots$ en la primera tabla anterior.
Cabe destacar que $W_1$ parece desempeñar un papel importante en la teoría de la función zeta de Ihara. K. Hashimoto dio la fórmula $$ \frac{1}{\zeta_G(u)}=\det(I-uW_1),\tag{2} $$ que ya muestra que $1/\zeta_G(u)$ es un polinomio en $u$ . El artículo de Horton, Stark y Terras ofrece una breve demostración de esta fórmula, que surge como un paso intermedio en su presentación de una demostración de la generalización de H. Bass de la fórmula del determinante de Ihara y Sunada (ecuación (1) anterior).
Su prueba de (2) implica la generalización de $W_1$ sustituyendo los elementos $1$ con variables complejas para obtener una matriz $W$ . La suma sobre paseos primos se reorganiza entonces para eliminar
-
la restricción a los paseos primitivos, y
-
la restricción a un único representante de cada clase de equivalencia.
Así que ahora tenemos una suma sobre paseos cerrados sin retroceso en lugar de sobre primos. La contribución a la suma de paseos de longitud $\ell$ es $\mathrm{Tr}\,W^\ell$ que es similar a la expresión a la que llegamos anteriormente. Se utiliza algo de cálculo matricial para relacionar esta suma con un determinante. Finalmente, las variables complejas se sustituyen por $1$ s para que $W$ se reduce a $W_1$ .
