Skip to main content
MathOverflow

Return to Question

added 20 characters in body
Source Link
user6818
user6818
  • 1.9k
  • 12
  • 20

We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on two elements or which is to be lifted with a flip.

We know that the adjacency spectrum of the 2-lifted graph is the union (with multiplicity) of the adjacency spectrum of the initial graph and the spectrum of the signing matrix.

  • Is there any generalization of the above for the spectrum of any of the Laplacians as given below? (I am particularly interested in $L4$)

$L1 = D - A$ where $D$ is the diagonal matrix of vertex degrees and $A$ is the adjacency matrix. (the ordinary "Laplacian")

$L2 = BB^T$, the ``Unsigned Laplacian" where $B$ is the vextex-edge incidence matrix. ($B(v,(a,b)) = 1,0,-1$ depending on whether $v=a$ or $v \neq a,b$ or $v=b$ respectively)

$L3$ s.t $L3_{ii} = deg(v_i)$ and $L3_{ij} = \frac{ -1}{ \sqrt{ deg(v_i) deg(v_j) } } $. This is the ``Normalized Laplacian"

$L4 = \sum _{edges} (v_{+} v_{+}^T \text{ or } v_{-} v_{-}^T)$ where for any edge $(s,t)$ $v_{+} = e_s + e_t$ and $v_{-} =e_s -e_t$ where $e_i$ is a $\vert V \vert$ size column vector with $1$ at the $i^{th}$ row and $0$ elsewhere. This is the ``Signed Laplacian"

We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on two elements or which is to be lifted with a flip.

We know that the adjacency spectrum of the 2-lifted graph is the union of the adjacency spectrum of the initial graph and the spectrum of the signing matrix.

  • Is there any generalization of the above for the spectrum of any of the Laplacians as given below? (I am particularly interested in $L4$)

$L1 = D - A$ where $D$ is the diagonal matrix of vertex degrees and $A$ is the adjacency matrix. (the ordinary "Laplacian")

$L2 = BB^T$, the ``Unsigned Laplacian" where $B$ is the vextex-edge incidence matrix. ($B(v,(a,b)) = 1,0,-1$ depending on whether $v=a$ or $v \neq a,b$ or $v=b$ respectively)

$L3$ s.t $L3_{ii} = deg(v_i)$ and $L3_{ij} = \frac{ -1}{ \sqrt{ deg(v_i) deg(v_j) } } $. This is the ``Normalized Laplacian"

$L4 = \sum _{edges} (v_{+} v_{+}^T \text{ or } v_{-} v_{-}^T)$ where for any edge $(s,t)$ $v_{+} = e_s + e_t$ and $v_{-} =e_s -e_t$ where $e_i$ is a $\vert V \vert$ size column vector with $1$ at the $i^{th}$ row and $0$ elsewhere. This is the ``Signed Laplacian"

We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on two elements or which is to be lifted with a flip.

We know that the adjacency spectrum of the 2-lifted graph is the union (with multiplicity) of the adjacency spectrum of the initial graph and the spectrum of the signing matrix.

  • Is there any generalization of the above for the spectrum of any of the Laplacians as given below? (I am particularly interested in $L4$)

$L1 = D - A$ where $D$ is the diagonal matrix of vertex degrees and $A$ is the adjacency matrix. (the ordinary "Laplacian")

$L2 = BB^T$, the ``Unsigned Laplacian" where $B$ is the vextex-edge incidence matrix. ($B(v,(a,b)) = 1,0,-1$ depending on whether $v=a$ or $v \neq a,b$ or $v=b$ respectively)

$L3$ s.t $L3_{ii} = deg(v_i)$ and $L3_{ij} = \frac{ -1}{ \sqrt{ deg(v_i) deg(v_j) } } $. This is the ``Normalized Laplacian"

$L4 = \sum _{edges} (v_{+} v_{+}^T \text{ or } v_{-} v_{-}^T)$ where for any edge $(s,t)$ $v_{+} = e_s + e_t$ and $v_{-} =e_s -e_t$ where $e_i$ is a $\vert V \vert$ size column vector with $1$ at the $i^{th}$ row and $0$ elsewhere. This is the ``Signed Laplacian"

Source Link
user6818
user6818
  • 1.9k
  • 12
  • 20

Laplacian spectrum of $2-$lifts of graphs

We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on two elements or which is to be lifted with a flip.

We know that the adjacency spectrum of the 2-lifted graph is the union of the adjacency spectrum of the initial graph and the spectrum of the signing matrix.

  • Is there any generalization of the above for the spectrum of any of the Laplacians as given below? (I am particularly interested in $L4$)

$L1 = D - A$ where $D$ is the diagonal matrix of vertex degrees and $A$ is the adjacency matrix. (the ordinary "Laplacian")

$L2 = BB^T$, the ``Unsigned Laplacian" where $B$ is the vextex-edge incidence matrix. ($B(v,(a,b)) = 1,0,-1$ depending on whether $v=a$ or $v \neq a,b$ or $v=b$ respectively)

$L3$ s.t $L3_{ii} = deg(v_i)$ and $L3_{ij} = \frac{ -1}{ \sqrt{ deg(v_i) deg(v_j) } } $. This is the ``Normalized Laplacian"

$L4 = \sum _{edges} (v_{+} v_{+}^T \text{ or } v_{-} v_{-}^T)$ where for any edge $(s,t)$ $v_{+} = e_s + e_t$ and $v_{-} =e_s -e_t$ where $e_i$ is a $\vert V \vert$ size column vector with $1$ at the $i^{th}$ row and $0$ elsewhere. This is the ``Signed Laplacian"