- 1. Introduction
- 2. Digraph Algebras
- 2.1 Digraph algebras of type C(
*S*) - 2.2 Abstract algebras of type C(
*S*) - 3. Representation of Posets

In the early 1970s, while teaching mathematics at St Stephen's College, Delhi, I had the idea of representing a directed graph as an algebraic expression in its vertices. When the university closed for some weeks because of a student agitation, I developed some (much too complicated) algebras along the lines I had been thinking about. I failed to get the idea published, partly (perhaps) because mathematical journals thought my aim was to advance the theory of algebras.

My aim was really very simple. Instead of referring to the digraph,
*ao--->---ob*, for instance, by some artificial name, it can be
referred to as *ab*, which also tells us all there is to know about it.
This is analogous to the situation in analytical geometry, where a
particular circle is represented by the equation *x*^2 + *y*^2 =
*r*^2, which also contains all there is to know about that circle.

The algebras developed here clearly enable a finite digraph to be held in a computer as a string.

A labelled digraph is completely defined by an ordered pair of sets
[*V,E*], where *V* is the set of vertices of the digraph and
*E* is the set of its edges. If we have some ordered pair
[*V,E*], the necessary and sufficient conditions for it to be
interpretable as a digraph will be taken to be, intuitively,

(1) *V* x *V* incls *E*,

(2) *V*, *E* have null intersection,

(3) The elements of *V* are irreducible (in the sense that even if
these elements have some internal structure, this never interacts with any
digraph operations).

Edges have the form (*a,b*), where *a,b* are vertices. An edge
(*a,a*) is a *loop* and a sequence of two or more edges of the
form (*a,b*), (*b,c*), ... , (*k,a*) is a *circuit*.

The digraph [*V,E*] may be interpreted as a set *V* on which there
is a binary relation R, given by

(D) *a*R*b* iff (*a,b*) blng *E*.

Conversely, a set *V* with a binary relation R is equivalent to the
digraph [*V,E*], where

*E* = {(*a,b*)| *a,b* blng *V*, and *a*R*b*}.

In a digraph algebra of type C (so named because *abc*, for instance,
represents a chain), we define

(4) [*V,E*] = [*W,F*] iff *V=W, E=F,*

(5) [*V,E*] + [*W,F*] = [*V* union *W*,
*E* union *F*],

(6) [*V,E*][*W,F*] = [*V* union *W*,
*E* union *F* union (*V* x *W*)].

It is easier to work with a simplified notation for digraphs. An isolated vertex will simply be called by its name:

(7) [{*a*},0] <--> *a*.

The *empty digraph* [0,0] will be denoted by 1 (this makes some
formulae counterintuitive, but the alternative symbol, 0, is equally
counterintuitive in other formulae):

(8) [0,0] <--> 1.

An arbitrary digraph will be denoted by a capital letter, as in

(9) [*V*(*A*),*E*(*A*)] <--> *A*.

It is now not difficult to derive the following axioms for an algebra of
type C called C(*S*), say (the significance of the *S* is
explained later):

C1. If *A, B* blng C(*S*) then *A + B*,
*AB* blng C(*S*),

C2. *A + B = B + A*,

C3. (*A + B*) + *C = A* + (*B + C*),

C4. (*AB*)*C = A*(*BC*),

C5. *A*(*B + C*) = *AB + AC*,
(*A + C*)*B = AB + CB*,

C6. *A* + 1 = 1 + *A*,

C7. *A*1 = 1*A* = *A*,

C8. *ABC = AB + BC + AC*.

(Axioms C1-C5 make C(*S*) a *semiring*.) Putting *C*=1 in C5, and later *B*=1 gives the important *absorption* rules:

*AB* + *A* = *AB* = *AB + B*,
*A + A = A*.

We also have *A*^3 = *A*^2, 1^2 =1.

Any particular digraph algebra C(*S*) is generated by 1 and certain
vertices which are the elements of the set *S*. By repeated use of
the axioms we obtain a *canonical form* for any element of C(*S*):

(10) *A* = Sum *ab* + Sum *c*, (*a,b,c* blng *S*,
and *c* =/= *a,b*),

the summations being over the terms relevant to *a*, assuming that
maximum absorption of terms has taken place. Eq.(10) has an intuitive
meaning: any digraph is the sum of its edges between pairs of vertices,
together with any isolated vertices. Canonical forms are unique up to
the order of terms.

Putting (10) into the ordered pair notation using (5)-(7), (9) gives two
important definitions in C(*S*):

C9. *V*(*A*) = {*a* | *a* blng *S*, and
*a* occurs in a canonical form of *A*},

C10. *E*(*A*) = {(*a,b*) | *a,b* blng *S*, and
*ab* is a term in a canonical form of *A*}.

Inclusion of digraphs will be defined by

(11) [*V,E*] incls [*W,F*] iff
*V* incls *W, E* incls *F*.

Now suppose *A, B* are digraphs of C(*S*) and *A* incls
*B*. Absorption when *A, B* are expressed in canonical form gives
*A + B* = *A*. Conversely, this equation can only hold by
absorption. Hence

C11. *A* incls *B* iff *A + B* = *A*.

An important element of C(*S*) is the digraph G(*S*) defined by

(12) G(*S*) = Sum Sum *ab* = (Sum *a*)^2,

the summation being over all the elements of *S*. G(*S*) is the
complete looped digraph with vertices *S*, so

[*S*, *S* x *S*] <--> G(*S*).

Hence any digraph *A* belongs to C(*S*) iff G(*S*) incls
*A*.

The following useful result is easily derived using canonical forms:

*AB = A* + *B* + (Sum *a*)(Sum *b*), (*a* blng
*V*(*A*), *b* blng *V*(*B*)).

Now suppose we have an algebra built out of 1 and the elements of *S*,
obeying the axioms C1-C8. We also suppose that the definitions C9-C11 are
used. Can this abstract algebra C(*S*) be interpreted as the digraph
algebra C(*S*) derived in 2.1?

THEOREM 1. *Necessary and sufficient conditions for an abstract algebra
C(S) to be interpretable as a digraph algebra of that type are (i) 1 not
blng S, (ii) the sets S and S x S have null intersection, (iii) the
elements of S are treated as irreducible.*

*Proof.* Necessity: (i) As a matter of notation, 1 is distinguished
from any element of *S*. (ii) is (2) applied to G(*S*). (iii) is
just (3).

Sufficiency: Given C1-C11 and (i)-(iii), we have to derive (1)-(8) under
the correspondence (9). (1) follows from C9, C10. (2) follows from C9,
C10, (ii). (3) is (iii). (4)-(8) are easy to obtain.

Theorem 1 is the result we were looking for. Two simple examples are:
*ab* is the digraph *a*o---->------o*b*, and *a + b*
is the digraph *a*o o*b*.

A poset is an ordered set whose order relation R is irreflexive and
transitive. Posets therefore correspond to certain digraphs. A poset in
which every pair of elements is relatively ordered is a *chain* (or
*linearly ordered* set). By repeated application of C8 we have that
the product *ab...k* is always a chain.

An abstract algebra whose elements must be posets has to have a more
complicated structure than C(*S*).

Last updated: 04 January 2005