Tag Archives: graph theory

Laplacian and Energy in Graphs

If E is a digraph (say, irreflexive binary relation on a set V), we then defined the incidence matrix [E] as the |V|\times |V| matrix whose ij entry was 1 iff (i,j)\in E for vertices i,j.  NOTE:  This definition is not the traditional one;  I accidentally wrote it incorrectly in a previous post and have made the correction to that definition.  The correct definition of [E] is the |V|\times |E| matrix where the i,(j,k) entry is 1 iff 1=i or 1=j.  That is, the entry i,(j,k) is 1 iff i is a vertex on the edge (j,k).  We can then define the Laplacian of E as

L(E)=[E][E]^\top.

We will simply write L as the Laplacian when it is clear what digraph we are discussing.

Now consider a map f:V\to\mathbb{R}^m and the corresponding |V|\times m matrix whose ith row is f(i).  We will denote this matrix f(V).  The authors ([1]) call the map f a representation of the graph (or digraph in our case) in \mathbb{R}^m.  As the m-vectors f(i) aren’t operators on \mathbb{R}^m, it seems counterintuitive to call the map a representation, but I will discuss an m\times m matrix they mention in a bit.

Definition 1.  Let \|\cdot\|=\|\cdot\|_2.  We define the energy with respect to f of the graph E by

\displaystyle\mathcal{E}_f(E)=\sum_{(i,j)\in E}\|f(i)-f(j)\|^2.

Furthermore we can define each edge to have a weight w((i,j))=w_{ij}\in\mathbb{R}^+ and define the weighted energy of E with respect to f and w by

\displaystyle\mathcal{E}_{f,w}(E)=\sum_{(i,j)\in E}w_{ij}\|f(i)-f(j)\|^2.

Now let W be the diagonal |E|\times |E| matrix whose diagonal (i,j),(i,j) entry is w_{ij} for a chosen weight function w.

Proposition 2.  Let E be an antisymmetric ((i,j)\in E\Rightarrow (j,i)\notin E) digraph on V, f:V\to\mathbb{R}^m, and w be a weight function on E.  Then

\displaystyle\mathcal{E}_{f,w}(E)=\mbox{tr~}f(V)^\top[E]W[E]^\top f(V).

One may call the matrix [E]W[E]^\top the weighted Laplacian of E.  Now the matrix f(V)^\top [E]W[E]^\top f(V) is an m\times m matrix which depends upon a triple (E,f,w) with E an antisymmetric digraph on V, f:V\to\mathbb{R}^m, and w:E\to\mathbb{R}^+.  So we could define a map \rho_E:F\times W\to L(\mathbb{R}^m) where

\displaystyle\rho_E((f,w))=f(V)^\top [E]W[E]^\top f(V).

Unfortunately this map isn’t a homomorphism, and hence not technically a representation;  I couldn’t find a simple structure on F\times W compatible with addition of m\times m matrices.

[1]  Godsil, Chris and Gordon Royle.  Algebraic Graph Theory.  Graduate Texts in Mathematics.  Vol. 207.  Springer Science and Business Media.  2004.

Advertisements

Matrices and Graphs

Recall in the post “Canonical Representation of Finitely Presented Coxeter Groups” we defined the Coxeter matrix of a Coxeter group G by a_{ij}=m_{ij} where (r_ir_j)^{m_{ij}}=1 with r_i,r_j as the generators of the group.  We can also define the Coxeter graph of a Coxeter group G whose vertices are the generators of the group.  Then since m_{ij}\geq 2 for i\neq j, we will define edges between two generators iff m_{i,j}\geq 3, and label the edge with m_{ij} when m_{ij}\geq 4.

In a generic graph (recall our presentation with V a set and E a symmetric relation on V^2), we can define a |V|\times |E| matrix, called the incidence matrix of E, denoted [E], where

a_{i,(j,k)}=\left\{\begin{array}{lcl}1&\mbox{if}&i=j \mbox{~or~} i=k\\ 0&\mbox{otherwise}&\end{array}\right .

So a_{i,(j,k)} is 1 iff the vertex i is a vertex on the edge (j,k).  This assumes some ordering of V.  So if we assume irreflexivity of E, then every column, indexed by (i,j), will have precisely two entries that are 1, specifically in the ith and jth row.

In the case of the incidence matrix of a Coxeter graph, the nonzero rows thus coincide with generators r_i such that m_{ij}\geq 3 for some j.

We can remove the symmetric requirement of E; so E is just a subset of V^2.  We can then use “binary relation” synonymously with “digraph“.  From here on we will assume a digraph on V is an irreflexive binary relation on V, and that a graph on V is an irreflexive symmetric binary relation on V.

Definition 1.  Let E_1 and E_2 be digraphs on V_1 and V_2 respectively.  A map \varphi:V_1\to V_2 is an (E_1,E_2)-digraph homomorphism if (x,y)\in E_1\Rightarrow(\varphi(x),\varphi(y))\in E_2.  An (E_1,E_2)isomorphism of digraphs is a bijective (E_1,E_2)-homomorphism of digraphs.

Definition 2.  Let E be a digraph on V.  We define the adjacency matrix of E, denoted (E), as the |V|\times |V| matrix where a_{x,y} is the number of paths from x to y.

So an entry a_{i,(j,k)}\in [E] being 1 means one of the entries a_{i,j} or a_{j,i} is 1 in (E) since being a vertex on an edge means there is a path to some other vertex (namely the other vertex on that edge).

Proposition 3.  Let E_1 and E_2 be digraphs on V.  There is an (E_1,E_2)-automorphism of V iff there is a permutation matrix P such that

\displaystyle P^\top(E_1)P=(E_2).

[1]  Godsil, Chris and Gordon Royle.  Algebraic Graph Theory.  Graduate Texts in Mathematics.  Vol. 207.  Springer Science and Business Media.  2004.

A Bit on Graphs

I was never a big fan of the presentation of graphs as sets of vertices and edges (say V and E) such that elements of E had the form e_{x,y} with x,y\in V and e_{x,y}=e_{y,x}.  I prefer to use the language of relations.

Definition 1.  A graph on X is a symmetric binary relation E on X.  We then call X the set of vertices and E the set of edges.

Recall a binary relation on X is a subset of X^2.  They are equivalent notions, but in the latter, one simply has a set with a relation on it–rather than these two separate sets such that the second set backtracks to the first as a relation.

Example 2.  A complete graph (one in which any two vertices are adjoined by an edge) is thus simply a graph where every x\in X is almost surjective with respect to E, by which I mean if we let

\displaystyle (x,X-\{x\})=\{(x,y):x\neq y\in X\},

then (x,X-\{x\})\subseteq E for all x\in X.  In particular we hence have

\displaystyle E=\bigcup_{x\in X}(x,X-\{x\}).

When I say a vertex is surjective with respect to E, I mean it has an edge with all other vertices (where almost-surjective excludes an edge with itself).  Note the relation E is always a surjective relation if we assume every vertex has some edge connected to it (i.e. is left-total and hence surjective since domain=codomain).  But a surjective relation E of course does not imply every element is surjective with respect to E.

Example 3.  A connected graph is a graph such that for any distinct two x,y\in X, there is a sequence (or path) x=x_1,...,x_n=y such that (x_i,x_{i+1})\in E for all 1\leq i\leq n.

A tree is thus a connected graph such that paths between points are unique (note this definition of a tree is different from that of posets: where elements have a well-ordered set of predecessors).  And so on and so on….

In fact,  recall Abramenko and Brown used this algebraic approach in the construction of Coxeter complexes, although it was slightly more complicated since they were dealing with graphs whose vertices were cosets of the maximal standard subgroups of a Coxeter group G.  Lengths of paths between vertices in the sense I have described coincide with lengths of minimal galleries between chambers containing those vertices.  Also, be not confused that in that construction of Coxeter complexes, there was another implicit notion of a (di)graph where any simplex was a vertex, and a directed edge connected two simplices if one was the face of another.