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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: