Hacer gráficos con un número impar de paseos de longitud $\ell$ entre dos vértices cualesquiera?

Question

Dado $\ell\ge 1$ decimos que un gráfico $G$ es $\ell$ -bueno si para cada $u,v\in G$ (no necesariamente distintos), el número de paseos de longitud $\ell$ de $u$ a $v$ es impar. Decimos que un gráfico $G$ es bueno si es $\ell$ -bueno para algunos $\ell\ge 1$ .

¿Existen los buenos gráficos? Para que quede claro, sólo hablo de grafos simples (que carecen de bucles y aristas múltiples).

Contexto: En el libro de Stanley sobre combinatoria algebraica, el ejercicio 1.13 trata de demostrar una interesante propiedad que se cumple para todos los grafos buenos. Un amigo mío me dijo que después de resolver el ejercicio, se dio cuenta de que no conocía ningún ejemplo de tales grafos. Yo también estoy perplejo sobre si pueden existir tales grafos.

Una búsqueda informática reveló que no existe ninguna con $7$ o menos vértices. No tengo claro los detalles de la búsqueda, los hizo mi amigo.

Answer 1

Un gráfico sin bucles no puede ser bueno.

Supongamos lo contrario, que $G$ tienen $n$ vértices y ser bueno.

Dejemos que $A$ sea la matriz de adyacencia de $G$ , dejemos que $\lambda_1,\ldots,\lambda_n$ sean sus valores propios sobre alguna extensión de $\mathbb{F}_2$ . Tenemos $\sum_{i=1}^n \lambda_i=\mathrm{tr} A=0$ .

Que $A$ es bueno significa que $A^\ell$ es una matriz todo-1 sobre $\mathbb{F}_2$ . Tiene rango 1, por lo que al menos $n-1$ valores propios de $A^\ell$ son 0. Por otro lado, los valores propios de $A^\ell$ son $\lambda_1^\ell,\ldots,\lambda_n^\ell$ . Por lo tanto, al menos $n-1$ $\lambda_i$ son cero, y como $\sum \lambda_i =0$ , todos $\lambda_i$ son 0. Por lo tanto $A$ es nilpotente. Como $A^\ell$ tiene rango 1, obtenemos $A^{\ell+1}=0$ (de hecho, denota $\mathrm{im} A^{\ell}:=X$ entonces $\dim X=1$ . Tenemos $\mathrm{im} A^{\ell+1}\subset \mathrm{im} A^{\ell}=X$ y también $\mathrm{im} A^{\ell+1}=AX$ . Desde $\dim X=1$ , ya sea $\mathrm{im} A^{\ell+1}=\{0\}$ o $AX=\mathrm{im} A^{\ell+1}=X$ En este último caso $A$ no es nilpotente ya que $A^kX=X\ne \{0\}$ para todos $k=0,1,2,\ldots$ ). Así que, $A\cdot A^\ell=0$ , lo que significa que la suma de las entradas en cada fila de $A$ es par, es decir, cada vértice de $G$ debe tener un grado parejo.

Ahora elige un vértice $v$ y que $W$ sea el conjunto de todos los paseos de longitud $\ell$ de $v$ a $v$ . La cardinalidad de $W$ es impar por hipótesis. La operación $\rho$ de invertir un paseo es una involución en $W$ por lo que el número de puntos fijos de $\rho$ es impar; estos puntos fijos consisten en paseos de la forma "tomar cualquier paseo de longitud $\ell/2$ a partir de $v$ y luego volver sobre sus pasos hasta $v$ " (así en particular, $\ell$ debe ser par). Pero como cada vértice tiene grado par, en particular hay un número par de opciones para el último paso del paseo de longitud $\ell/2$ por lo que el número total de paseos de longitud $\ell/2$ debe ser uniforme. Esto es una contradicción.