Espectro Laplaciano de $2-$elevaciones de gráficos

Question

Sabemos que un levantamiento de $2$ de un grafo está especificado por una asignación de $\pm 1$ en las aristas del grafo (dada como una matriz de signos) denotando cuál arista debe ser duplicada por la permutación de identidad en dos elementos o cuál debe ser levantada con un cambio de signo.

Sabemos que el espectro de adyacencia del grafo elevado a $2$ es la unión (con multiplicidad) del espectro de adyacencia del grafo inicial y el espectro de la matriz de signos.

• ¿Hay alguna generalización de lo anterior para el espectro de cualquiera de los Laplacianos como se muestra a continuación? (Me interesa particularmente $L4$)

---

$L1 = D - A$ donde $D$ es la matriz diagonal de los grados de los vértices y $A$ es la matriz de adyacencia. (el "Laplaciano" ordinario)

$L2 = BB^T$, el "Laplaciano No Firmado" donde $B$ es la matriz de incidencia vértice-aresta. ($B(v,(a,b)) = 1,0,-1$ dependiendo si $v=a$ o $v \neq a,b$ o $v=b$ respectivamente)

$L3$ tal que $L3_{ii} = deg(v_i)$ y $L3_{ij} = \frac{ -1}{ \sqrt{ deg(v_i) deg(v_j) } } $. Este es el "Laplaciano Normalizado"

$L4 = \sum _{aristas} (v_{+} v_{+}^T \text{ o } v_{-} v_{-}^T)$ donde para cualquier arista $(s,t)$ $v_{+} = e_s + e_t$ y $v_{-} =e_s -e_t$ donde $e_i$ es un vector columna de tamaño $\vert V \vert$ con $1$ en la fila $i$ y $0$ en otro lugar. Este es el "Laplaciano Firmado"

Answer 1

Si $Y$ es una elevación de 2 de $X$, existe una partición $\pi$ de $V(Y)$ en pares, de tal forma que los vértices en un par no son adyacentes y dos pares distintos están unidos por un emparejamiento de 2, o por ningún borde en absoluto. Supongamos que $n=|V(X)|$ y sea $P$ la matriz $2n\times n$ cuyas columnas son los vectores característicos de los pares. Sea $Q$ la matriz $2n\times n$ que obtenemos reemplazando un 1 en cada columna de $P$ por un -1. Nótese que $P^TQ=0$ y tanto $P$ como $Q$ tienen rango $n$. Sea $M$ la matriz $[P Q]$. Nótese que $M^TM=2I.

Sea $A$ la matriz de adyacencia de $Y$ y sea $D$ su matriz diagonal de grados, y consideremos la matriz $B=\frac12 M^TAM$. El espacio columna de $P$ es $A$-invariante (porque $\pi$ es una partición equitativa para $Y$); ya que el espacio columna de $Q$ es el complemento ortogonal del espacio columna de $P, también es $A$-invariante. Por lo tanto, $B$ es diagonal por bloques. El bloque $(1,1)$ es $A(X)$ y el bloque $(2,2)$ es la matriz de adyacencia firmada de $X$, que denotaré por $S$.

Ahora, sea $D$ la matriz diagonal de los grados de $Y$, sea $D_X$ la matriz diagonal de los grados de $X$ y sea $A_X$ la matriz de adyacencia de $X$. Dado que dos vértices en la misma celda de $\pi$ tienen el mismo grado, $DP=PD_X$ y $DQ=QD_X$. Por lo tanto, $M^TDM$ es diagonal por bloques, con ambos bloques diagonales iguales a $D_X$.

De esto se deduce que $\frac12 M^T(A+D)M$ es diagonal por bloques con bloques $A_X+D_X$ y $S+D_X$, y $\frac12 M^T(D-A)M$ es diagonal por bloques con bloques $D_X-A_X$ y $D_X-S$.

Dejo los otros dos casos como ejercicios.