Recall in the post “Canonical Representation of Finitely Presented Coxeter Groups” we defined the Coxeter matrix of a Coxeter group by where with as the generators of the group. We can also define the Coxeter graph of a Coxeter group whose vertices are the generators of the group. Then since for we will define edges between two generators iff and label the edge with when
In a generic graph (recall our presentation with a set and a symmetric relation on ), we can define a matrix, called the incidence matrix of , denoted where
So is iff the vertex is a vertex on the edge This assumes some ordering of So if we assume irreflexivity of then every column, indexed by will have precisely two entries that are specifically in the th and th row.
In the case of the incidence matrix of a Coxeter graph, the nonzero rows thus coincide with generators such that for some
We can remove the symmetric requirement of ; so is just a subset of We can then use “binary relation” synonymously with “digraph“. From here on we will assume a digraph on is an irreflexive binary relation on and that a graph on is an irreflexive symmetric binary relation on
Definition 1. Let and be digraphs on and respectively. A map is an -digraph homomorphism if An –isomorphism of digraphs is a bijective -homomorphism of digraphs.
Definition 2. Let be a digraph on We define the adjacency matrix of , denoted as the matrix where is the number of paths from to
So an entry being means one of the entries or is in 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 and be digraphs on There is an -automorphism of iff there is a permutation matrix such that
 Godsil, Chris and Gordon Royle. Algebraic Graph Theory. Graduate Texts in Mathematics. Vol. 207. Springer Science and Business Media. 2004.
I was never a big fan of the presentation of graphs as sets of vertices and edges (say and ) such that elements of had the form with and I prefer to use the language of relations.
Definition 1. A graph on is a symmetric binary relation on We then call the set of vertices and the set of edges.
Recall a binary relation on is a subset of 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 is almost surjective with respect to , by which I mean if we let
then for all In particular we hence have
When I say a vertex is surjective with respect to , I mean it has an edge with all other vertices (where almost-surjective excludes an edge with itself). Note the relation 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 of course does not imply every element is surjective with respect to
Example 3. A connected graph is a graph such that for any distinct two there is a sequence (or path) such that for all
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 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.