La matriz de adyacencia de diferencias simétricas de cualquier subconjunto de caras tiene un valor propio de$2$ ...?

Question

Asumir una cúbicos (la recompensa) plano gráfico de $G$ y vamos a llamar a sus caras $f_k\in F$. La matriz de adyacencia de cualquier cara $f_k$ tiene un autovalor de a $2$, ya que es un $2$-gráfico regular, es decir, un ciclo.

Quiero mostrar que la simétrica de las diferencias de cualquier subconjunto de a $F$, también tiene un autovalor de a $2$, lo cual es evidente desde $f_k \ominus f_n$ es de nuevo un ciclo.

Así que empecé a configurar un cálculo simbólico: $$ Un(\vec x)={\enorme{\ominus}}_{k} \; x_k f_k = \left( \sum_k x_k f_k \right) \bmod 2 , $$ donde $\vec x$ denota un vector con los valores de $\mathbb Z_2$, es decir,$0$$1$. Una vez $\vec x$ es elegido la matriz resultante contiene sólo valores de $0$$1$.

Ahora quiero mostrar que la $\displaystyle \det\left(A(\vec x) -2I \right)=0 \; \; \forall \vec x$, con la excepción de $\vec 0$ $\vec 1$ (donde todos los $x_k=1$). Y aquí es donde estoy atascado...

Para dar una explicite ejemplo, aquí la matriz resultante por el prisma triangular gráfico de $Y_3$

$\hskip1.7in$

$$ Un(\vec x)= \pmatrix{ 0& x_1+x_3& x_1+x_5& x_3+x_5& 0& 0\\ x_1+x_3& 0& x_1+x_4& 0& x_3+x_4& 0\\ x_1+x_5& x_1+x_4& 0& 0& 0& x_4+x_5\\ x_3+x_5& 0& 0& 0& x_2+x_3& x_2+x_5\\ 0& x_3+x_4& 0& x_2+x_3& 0& x_2+x_4\\ 0& 0& x_4+x_5& x_2+x_5& x_2+x_4& 0 } $$ cuando los triángulos son fácilmente reconocido como superior izquierda/inferior derecha de los bloques de variables $x_1/x_2$.

Ahora, cuando el cálculo de $\det\left(A(\vec x) -2I \right)=0$ todos los $32-2=30$ posibilidades, puedo comprobar que es correcto!

Answer 1

La mejor manera de probar para cúbicos gráficos, es notar que cualquier diferencia simétrica de las caras es $2$-regular. El argumento aquí es básicamente que cualquiera de las dos caras que compartan $0$ o $1$ común edge, por lo que la diferencia simétrica es cualquiera de los dos ciclos disjuntos o un gran ciclo. Entonces usted sabe que una de dos gráfico regular tiene un autovalor de a $2$.

Usted puede hacerlo de la manera que usted está tratando; es difícil. El hecho de que usted está considerando la adición de matrices $\bmod{2}$, a continuación, convertir de nuevo a las matrices de más de $\mathbb{Q}$ hace las cosas difíciles. Pero puede ayudar si usted usa el $\circ$ operación, básicamente $A \circ B$ es la de las componentes de la multiplicación. Para $0$-$1$ matrices esto significa que usted tiene un $1$ en posiciones donde la $A$ $B$ ambos $1$ $0$ en todas las demás. Esto significa que la diferencia simétrica de a $A$ y $B$, $A+B \bmod{2}$, puede ser escrito $A+B - 2(A \circ B)$. Así que usted puede probar para mostrar dos caras: tome $F_{i}$$F_{j}$, considerado como matrices de adyacencia de dos caras (como $n \times n$ matrices, $|V|=n$). Usted sabe que cada cara tiene un vector propio para $2$, $f_{i}$ y $f_{k}$, respectivamente, donde estos vectores tienen un $1$ corresponden a puntos en la cara y un $0$ en todas partes. Entonces usted necesita para convencerse de que $$(F_{i}+F_{j} - 2(F_{i} \circ F_{j})) (f_{i} + f_{j} - 2(f_{i} \circ f_{j}))= 2(f_{i} + f_{j} - 2(f_{i} \circ f_{j})).$$ Esto es muy fácil si $F_{i}$ $F_{j}$ no comparten aristas comunes (porque entonces $F_{i} \circ F_{j} = 0$, $f_{i} \circ f_{j} = 0$, y $F_{i}f_{j} = F_{j}f_{i} = 0$). Algunos más (complicado, pero no se puede deshacer) argumentos deben de ser las dos caras que comparten un borde...

[RESPUESTA anterior para no cúbico gráficos]

En realidad, hay dos cosas que decir: si la diferencia simétrica de una colección de caras es de nuevo un ciclo, o incluso en una unión de ciclos disjuntos, entonces no hay nada que mostrar; es dos regulares, por lo que claramente tiene un autovalor igual a $2$.

Pero ¿es esto cierto? ¿Qué sucede si dos caras comparten un vértice, pero no un borde? Tomemos, por ejemplo, este gráfico; es planar. La diferencia simétrica de las caras superior e inferior y es el gráfico completo. Pero no tiene un autovalor de a dos.