DIRECTED GRAPHS, MAGIC SQUARES, AND GROTHENDIECK TOPOLOGIES

Min Ho Lee

1. Introduction. It is well–known that a graph can be represented by a square matrix by considering its adjacency matrix. One of the goals of this paper is to give an algebraic description of such a correspondence for directed graphs.

A directed graph can be viewed as an order pair (α, β) of mappings from the set of directed edges to the set of vertices in such a way that a directed edge e is the one with the initial vertex α(e) and the terminal vertex β(e) [4]. Thus, with an appropriate morphism, we can consider the category of directed graphs whose objects are ordered pairs of mappings of finite sets. More precisely, we consider the category of directed graphs with a fixed set X of vertices whose objects are viewed as the set of ordered pairs (α, β) of mappings α, β: Y → X from various finite sets Y to the given set X. We extend the set of isomorphism classes of the objects in this category to a set which has a ring structure and prove that the resulting ring is isomorphic to the ring of m × m integral matrices, where m is the number of elements in X (Theorem 1). We also consider a subring of this ring corresponding to regular digraphs and show that it is isomorphic to the ring of generalized magic squares (Theorem 2).

Given a finite set X, the category of single mappings ϕ: Z → X can be regarded as a Grothendieck topology on the category of finite sets [2, 3]. In Section 7, we discuss the action of the ring associated to directed graphs above on the objects of this category.

2. Directed Graphs. A directed graph G = (V, E) consists of a finite set V of vertices and a finite set E of edges, where each edge is an ordered pair of vertices. Let V = {v_{1}, …, v_{n}} and E = {e_{1}, …, e_{n}}. If e_{l} = (v_{i}, v_{j}), then v_{i} is called the initial vertex and v_{j} is called the terminal vertex of e_{l}.

To each directed graph G = (V, E), we can associate an ordered pair (α, β) of mappings α, β: E → V such that, for each edge e ∈ E, α(e) is the initial vertex and β(e) is the terminal vertex of e [4]. Conversely, to each ordered pair (f, g) of mappings f, g: Y → X of finite sets, we can associate a directed graph such that X is the set of vertices, Y is the set of edges, and each y ∈ Y has the initial vertex f(y) and the terminal vertex g(y). This correspondence leads us to the following definition of the category of directed graphs.

\underline{Definition 1}. The category DG of directed graphs is defined by the following:

(i) The objects of DG are ordered pairs (f, g) of mappings f, g: Y → X of finite sets.

(ii) A morphism from the pair (f_{1}, g_{1}) of mappings f_{1}, g_{1}: Y_{1} → X_{1} to the pair (f_{2}, g_{2}) of mappings f_{2}, g_{2}: Y_{2} → X_{2} is a pair (μ, ν) of mappings μ: Y_{1} → Y_{2} and ν: X_{1} → X_{2} such that f_{2} ∘ μ = ν ∘ f_{1} and g_{2} ∘ μ = ν ∘ g_{1}.

\underline{Remark 1}. It can be easily shown that the pair (μ, ν) in (ii) of the above definition is indeed a morphism in a category with (id, id) the identity morphism.

\underline{Definition 2}. Let X be a fixed finite set. The category DG_{X} of directed graphs with vertices X is the subcategory of DG defined as follows:

(i) The objects of DG_{X} are triples (Y, f, g), where Y is a finite set and f, g: Y → X are mappings of Y into X.

(ii) A morphism from the triple (Y_{1}, f_{1}, g_{1}) to the triple (Y_{2}, f_{2}, g_{2}) is a mapping φ: Y_{1} → Y_{2} such that f_{1} = f_{2} ∘ φ and g_{1} = g_{2} ∘ φ.

3. The Multiplication Operation. We define an operation ⊙ on the set of objects of the category DG_{X} as follows. Given two objects (Y_{1}, f_{1}, g_{1}) and (Y_{2}, f_{2}, g_{2}) of DG_{X}, let U be the pullback of g_{1}: Y_{1} → X and f_{2}: Y_{2} → X and let p: U → Y_{1} and q: U → Y_{2} be the canonical projection mappings. Thus, we have U = {(y_{1}, y_{2}) ∈ Y_{1} × Y_{2} | g_{1}(y_{1}) = f_{2}(y_{2})} and g_{1} ∘ p = f_{2} ∘ q. We set (Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2}) = (U, f_{1} ∘ p, g_{2} ∘ q). Then the triple (U, f_{1} ∘ p, g_{2} ∘ q) is an object of DG_{X} and therefore ⊙ is an operation on DG_{X}.

\underline{Remark 2}. In graph–theoretic terms, the product of two graphs G_{1} = (X, E_{1}) and G_{2} = (X, E_{2}) with vertices X and sets of edges E_{1} and E_{2}, respectively, is the graph G = (X, E) with vertices X and edges E = E_{1} ∘ E_{2}, where “∘” denotes the composition of relations.

\underline{Proposition 1}. Suppose that (Y_{1}, f_{1}, g_{1}), (Y_{2}, f_{2}, g_{2}) are objects of DG_{X} that are isomorphic to the objects (Y′_{1}, f′_{1}, g′_{1}), (Y′_{2}, f′_{2}, g′_{2}) of DG_{X}, respectively. Then there is a canonical isomorphism between (Y_{1}, f_{1}, g_{1})⊙(Y_{2}, f_{2}, g_{2}) and (Y′_{1}, f′_{1}, g′_{1})⊙ (Y′_{2}, f′_{2}, g′_{2}).

\underline{Proof}. Let ϕ_{1}: Y_{1} → Y′_{1} and ϕ_{2}: Y_{2} → Y′_{2} be bijections such that f′_{1} ∘ ϕ_{1} = f_{1}, g′_{1} ∘ ϕ_{1} = g_{1}, f′_{2} ∘ ϕ_{2} = f_{2}, and g′_{2} ∘ ϕ_{2} = g_{2}. Let (U, f_{1} ∘ p, g_{2} ∘ q) = (Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2}) and (U′, f′_{1} ∘ p′, g′_{2} ∘ q′) = (Y′_{1}, f′_{1}, g′_{1}) ⊙ (Y′_{2}, f′_{2}, g′_{2}), where p: U → Y_{1}, q: U → Y_{2}, p′: U′ → Y′_{1}, and q′: U′ → Y′_{2} are projections, and U = {(y_{1}, y_{2}) ∈ Y_{1} × Y_{2} | g_{1}y_{1} = f_{2}y_{2}}, U′ = {(y′_{1}, y′_{2}) ∈ Y′_{1} × Y′_{2} | g′_{1}y′_{1} = f′_{2}y′_{2}}. We define ϕ: U → U′ by ϕ(y_{1}, y_{2}) = (ϕ_{1}(y_{1}), ϕ_{2}(y_{2})). If (y_{1}, y_{2}) ∈ U, then (f′_{1} ∘ p′)(ϕ(y′_{1}, y′_{2})) = f′_{1} ∘ p′(ϕ_{1}(y_{1}), ϕ_{2}(y_{2})) = f′_{1} ∘ ϕ_{1}(y_{1}) = f_{1}(y_{1}) = f_{1} ∘ p(y_{1}, y_{2}) and (g′_{2} ∘ q′)(ϕ(y′_{1}, y′_{2})) = g′_{2} ∘ q′(ϕ_{1}(y_{1}), ϕ_{2}(y_{2})) = g′_{2} ∘ ϕ_{2}(y_{2}) = g_{2}(y_{2}) = g_{2} ∘ q(y_{1}, y_{2}). Thus, we have (f′_{1} ∘ p′) ∘ ϕ = f_{1} ∘ p and (g′_{2} ∘ q′) ∘ ϕ = g_{2} ∘ q; hence the isomorphism follows.

\underline{Proposition 2}. There is a canonical isomorphism ((Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2})) ⊙ (Y_{3}, f_{3}, g_{3}) ≅ (Y_{1}, f_{1}, g_{1}) ⊙ ((Y_{2}, f_{2}, g_{2}) ⊙ (Y_{3}, f_{3}, g_{3})) for (Y_{i}, f_{i}, g_{i}) ∈ DG_{X}, i = 1, 2, 3.

\underline{Proof}. Let (U, p, g) = (Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2}) and (V, p′, q′) = (Y_{2}, f_{2}, g_{2}) ⊙ (Y_{3}, f_{3}, g_{3}). Thus, U = {(y_{1}, y_{2}) ∈ Y_{1} × Y_{2} | g_{1}y_{1} = f_{2}y_{2}}, V = {(y_{2}, y_{3}) ∈ Y_{2} × Y_{3} | g_{2}y_{2} = f_{3}y_{3}} and p: U → Y_{1}, q: U → Y_{2}, p′: V → Y_{2}, q′: V → Y_{3} are the natural projections. We have

(U, p, q) ⊙ (Y_{3}, f_{3}, g_{3}) = {((y_{1}, y_{2}), y_{3}) ∈ U × Y_{3} | g_{2} ∘ q(y_{1}, y_{2}) = f_{3}y_{3}}
= {((y_{1}, y_{2}), y_{3}) ∈ U × Y_{3} | g_{2}y_{2} = f_{3}y_{3}}
= {((y_{1}, y_{2}), y_{3}) ∈ (Y_{1} × Y_{2}) × Y_{3} | g_{1}y_{1} = f_{2}y_{2}, g_{2}y_{2} = f_{3}y_{3}}.

Similarly, (Y_{1}, f_{1}, g_{1}) ⊙ (V, p′, q′) is equal to {(y_{1}, (y_{2}, y_{3})) ∈ Y_{1} × (Y_{2} × Y_{3}) | g_{1}y_{1} = f_{2}y_{2}, g_{2}y_{2} = f_{3}y_{3}}.

Thus, the mapping ((y_{1}, y_{2}), y_{3}) ↦ (y_{1}, (y_{2}, y_{3})) determines a canonical isomorphism.

We denote by M_{X} the set of isomorphism classes M_{X} = Obj(DG_{X})/ ≅ of objects of DG_{X}. By Proposition 1, the operation ⊙ on DG_{X} induces an operation on M_{X} which will also be denoted by ⊙.

\underline{Proposition 3}. If 1_{X} is the identity mapping on X, then the set M_{X} together with the operation ⊙ is a monoid with (X, 1_{X}, 1_{X}) the identity element.

\underline{Proof}. Obviously, (X, 1_{X}, 1_{X}) is an identity with respect to the operation ⊙. The operation ⊙ is associative by Proposition 2; hence the proposition follows.

4. The Sum Operation. Given two directed graphs (Y_{1}, f_{1}, g_{1}) and (Y_{2}, f_{2}, g_{2}) in DG_{X}, we define Y_{1}⨿Y_{2} to be the disjoint union of Y_{1} and Y_{2} with inclusions i_{1}: Y_{1} → Y_{1}⨿Y_{2} and i_{2}: Y_{2} → Y_{1}⨿Y_{2}. We denote by f_{1}⨿f_{2}, g_{1}⨿g_{2}: Y_{1}⨿Y_{2} → X the mappings that satisfy

(f_{1} ⨿ f_{2}) ∘ i_{1} = f_{1}, (f_{1} ⨿ f_{2}) ∘ i_{2} = f_{2}, (g_{1} ⨿ g_{2}) ∘ i_{1} = g_{1}, (g_{1} ⨿ g_{2}) ∘ i_{2} = g_{2}.

Then, we define the operations ⊕ on DG_{X} by (Y_{1}, f_{1}, g_{1}) ⊕ (Y_{2}, f_{2}, g_{2}) = (Y_{1} ⨿ Y_{2}, f_{1} ⨿ f_{2}, g_{1} ⨿ g_{2}).

\underline{Remark 3}. In graph–theoretic terms, the sum G_{1} ⊕ G_{2} of the graphs G_{1} = (X, E_{1}) and G_{2} = (X, E_{2}) is (X, E), where E is just the disjoint union of the sets of edges E_{1} and E_{2}.

\underline{Lemma 1}. Suppose that (Y_{1}, f_{1}, g_{1}) and (Y_{2}, f_{2}, g_{2}) are objects of DG_{X} that are isomorphic to the objects (Y′_{1}, f′_{1}, g′_{1}) and (Y′_{2}, f′_{2}, g′_{2}) of DG_{X}, respectively. Then there is a canonical isomorphism (Y_{1}, f_{1}, g_{1})⊕(Y_{2}, f_{2}, g_{2}) ≅ (Y′_{1}, f′_{1}, g′_{1})⊕(Y′_{2}, f′_{2}, g′_{2}).

\underline{Proof}. Let ϕ_{1}: Y_{1} → Y′_{1} and ϕ_{2}: Y_{2} → Y′_{2} be bijections such that f′_{1} ∘ ϕ_{1} = f_{1}, g′_{1} ∘ ϕ_{1} = g_{1}, f′_{2} ∘ ϕ_{2} = f_{2}, and g′_{2} ∘ ϕ_{2} = g_{2}. Define ϕ: Y_{1} ⨿ Y_{2} → Y′_{1} ⨿ Y′_{2} to be the mapping satisfying ϕ(y_{1}) = ϕ_{1}(y_{1}) if y_{1} ∈ Y_{1} and ϕ(y_{2}) = ϕ_{2}(y_{2}) if y_{2} ∈ Y_{2}. It can be easily shown that ϕ induces an isomorphism between (Y_{1} ⨿ Y_{2}, f_{1} ⨿ f_{2}, g_{1} ⨿ g_{2}) and (Y′_{1} ⨿ Y′_{2}, f′_{1} ⨿ f′_{2}, g′_{1} ⨿ g′_{2}).

\underline{Lemma 2}. Let (Y_{1}, f_{1}, g_{1}), (Y_{2}, f_{2}, g_{2}), and (Y_{3}, f_{3}, g_{3}) be objects of DG_{X} that are isomorphic to the objects (Y′_{1}, f′_{1}, g′_{1}), (Y′_{2}, f′_{2}, g′_{2}), and (Y′_{3}, f′_{3}, g′_{3}), respectively.

Then there are canonical isomorphisms (Y_{1}, f_{1}, g_{1}) ⊕ (Y_{2}, f_{2}, g_{2}) ≅ (Y′_{2}, f′_{2}, g′_{2}) ⊕ (Y′_{1}, f′_{1}, g′_{1}) and

((Y_{1}, f_{1}, g_{1}) ⊕ (Y_{2}, f_{2}, g_{2})) ⊕ (Y_{3}, f_{3}, g_{3}) ≅ (Y′_{1}, f′_{1}, g′_{1}) ⊕ ((Y′_{2}, f′_{2}, g′_{2}) ⊕ (Y′_{3}, f′_{3}, g′_{3})).

\underline{Proof}. The proof is straightforward and will be omitted.

\underline{Proposition 4}. There are canonical isomorphisms

(Y_{1}, f_{1}, g_{1}) ⊙ ((Y_{2}, f_{2}, g_{2}) ⊕ (Y_{3}, f_{3}, g_{3}))
≅ ((Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2})) ⊕ ((Y_{1}, f_{1}, g_{1}) ⊙ (Y_{3}, f_{3}, g_{3})),
((Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2})) ⊕ (Y_{3}, f_{3}, g_{3})
≅ ((Y_{1}, f_{1}, g_{1}) ⊙ (Y_{3}, f_{3}, g_{3})) ⊕ ((Y_{2}, f_{2}, g_{2}) ⊙ (Y_{3}, f_{3}, g_{3})).

\underline{Proof}. We shall prove the first isomorphism. The second one can be proved similarly. Let (U, α, β) and (V, γ, δ) be the left and the right hand sides of the isomorphism, respectively. Then we have (U, α, β) = (Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2} ⨿ Y_{3}, f_{2} ⨿ f_{3}, g_{2} ⨿ g_{3}), where

U = {(y_{1}, y) ∈ Y_{1} × (Y_{2} ⨿ Y_{3}) | g_{1}y_{1} = (f_{2} ⨿ f_{3})y}.

But we have

(f_{2} ⨿ f_{3})y = \{ \begin{matrix}f_{2}y_{2}, & if y = i_{2}(y_{2}), y_{2} ∈ Y_{2} \\ f_{3}y_{3}, & if y = i_{3}(y_{3}), y_{3} ∈ Y_{3}, \end{matrix}

where i_{2}: Y_{2} → Y_{2} ⨿ Y_{3} and i_{3}: Y_{3} → Y_{2} ⨿ Y_{3} are the natural embeddings. Thus, it follows that U is equal to the set

{(y_{1}, i_{2}(y_{2})) ∈ Y_{1} ×i_{2}(Y_{2}) | g_{1}y_{1} = f_{2}y_{2}}⨿{(y_{1}, i_{3}(y_{3})) ∈ Y_{1} ×i_{3}(Y_{3}) | g_{1}y_{1} = f_{3}y_{3}}.

On the other hand, V = V_{1} ⨿ V_{2}, where

V_{1} = {(y_{1}, y_{2}) ∈ Y_{1} × Y_{2} | g_{1}y_{1} = f_{2}y_{2}}, V_{2} = {(y_{1}, y_{3}) ∈ Y_{1} × Y_{3} | g_{1}y_{1} = f_{3}y_{3}}.

We denote by j_{1}: V_{1} → V_{1} ⨿ V_{2} and j_{2}: V_{2} → V_{1} ⨿ V_{2} the natural embeddings and define a mapping ϕ: V → U by ϕ(j_{1}(y_{1}, y_{2})) = (y_{1}, i_{2}(y_{2})) and ϕ(j_{2}(y_{1}, y_{3})) = (y_{1}, i_{3}(y_{3})) for (y_{1}, y_{2}) ∈ V_{1} and (y_{1}, y_{2}) ∈ V_{2}. Then ϕ is a bijection and it remains to show that γ = α ∘ ϕ and δ = β ∘ ϕ. Indeed, we have

α ∘ ϕ(j_{1}(y_{1}, y_{2})) = α(y_{1}, i_{2}(y_{2})) = f_{1} ∘ pr_{1}(y_{1}, i_{2}(y_{2})) = f_{1}(y_{1}),

where pr_{1} is the projection onto Y_{1}. On the other hand, we have

γ(j_{1}(y_{1}, y_{2})) = (f_{1} ∘ p_{1} ⨿ g_{3} ∘ p_{3})(j_{1}(y_{1}, y_{2})) = f_{1} ∘ p_{1}(y_{1}, y_{2}) = f_{1}(y_{1}),

where p_{1} and p_{3} are natural projections onto Y_{1} and Y_{3}, respectively. It follows that γ = α ∘ ϕ. Similarly, we can show that δ = β ∘ ϕ.

By Lemma 1, the operation ⊕ is well–defined on M_{X} and by Lemma 2, it is commutative and associative. The operation ⊕ is also distributive over ⊙ on M_{X} by Proposition 4.

5. The Ring Structure. From the results of Sections 3 and 4, it follows that the operations ⊙ and ⊕ on the set M_{X} of isomorphism classes of the objects of DG_{X} satisfy most of the axioms necessary to make (M_{X}, ⊙, ⊕) a ring, except the existence of an identity and an inverse for the operation ⊕. In order to remedy this problem, we shall extend the operation ⊕ to the addition operation in the monoid algebra ℤ[M_{X}] of M_{X} over ℤ. More precisely, we define the ring R_{X} by R_{X} = ℤ[M_{X}]/I, where I is the ideal of ℤ[M_{X}] generated by the elements of the form x ⊕ y − x − y, with x, y ∈ M_{X}.

\underline{Theorem 1}. If X is a finite set with m elements, then R_{X} is isomorphic to the ring M_{m}(ℤ) of m × m matrices of integers.

\underline{Proof}. We shall first construct a mapping ψ: ℤ[M_{X}] → M_{m}(ℤ) from the monoid algebra ℤ[M_{X}] to the set M_{m}(ℤ) of m × m matrices of integers. Suppose X = {x_{1}, …, x_{m}}. If ({y}, f, g) ∈ M_{X} with f(y) = x_{i} and g(y) = x_{j}, then we set ψ({y}, f, g) = e_{i,j}, where {e_{i,j} | 1 ≤ i, j ≤ m} is the standard basis for M_{m}(ℤ). Consider an element

V = ∑_{j=1}^{k} n_{j}(Y_{j}, f_{j}, g_{j}) ∈ ℤ[M_{X}].

For 1 ≤ j ≤ k, we assume that Y_{j} = {y_{j,i} | 1 ≤ i ≤ l_{j}} and denote by f_{j,i}, g_{j,i}, the restrictions of f_{j}, g_{j} to the set {y_{j,i}}. Then we have (Y_{j}, f_{j}, g_{j}) = ⊕_{i=1}^{l_{j}}({y_{j,i}, f_{j,i}, g_{j,i}}). We define ψ(V) by

ψ(V) = ∑_{j=1}^{k} ∑_{i=1}^{l_{j}} n_{j}ψ({y_{j,i}, f_{j,i}, g_{j,i}}).

Now, using the fact that two elements ({x}, f, g) and ({y}, f′, g′) in ℤ[M_{X}] are isomorphic if and only if f(x) = f′(y) and g(x) = g′(y), it follows that ψ induces a homomorphism of abelian groups from R_{X} to M_{m}(ℤ). In order to consider the product operations, suppose ψ({y_{1}}, f_{1}, g_{1}) = e_{i,j}, ψ({y_{2}}, f_{2}, g_{2}) = e_{k,l}, so that f_{1}(y_{1}) = x_{i}, g_{1}(y_{1}) = x_{j}, f_{2}(y_{2}) = x_{k}, and g_{2}(y_{2}) = x_{l}. Let ({y_{1}}, f_{1}, g_{1}) ⊙ ({y_{2}}, f_{2}, g_{2}) = (U, λ, μ) with

U = \{(y_{1}, y_{2}) ∈ \{y_{1}\} × \{y_{2}\} | g_{1}(y_{1}) = f_{2}(y_{2})\} = \{ \begin{matrix}∅, & if x_{j} ≠ x_{k} \\ \{(y_{1}, y_{2})\}, & if x_{j} = x_{k}. \end{matrix}

If x_{j} = x_{k}, then

λ(y_{1}, y_{2}) = f_{1} ∘pr_{1}(y_{1}, y_{2}) = f_{1}(y_{1}) = x_{i}, μ(y_{1}, y_{2}) = g_{2} ∘pr_{2}(y_{1}, y_{2}) = g_{2}(y_{2}) = x_{l}.

Hence, we have

ψ(U, λ, μ) = \{ \begin{matrix}0, & if j ≠ k \\ e_{i,l}, & if j = k. \end{matrix}

Thus, ψ transfers the operation ⊙ to the multiplication operation of matrices. It follows that ψ induces a ring homomorphism from R_{X} to M_{m}(ℤ).

6. Magic Squares. In this section we slightly generalize the usual definition of magic squares and show that these generalized magic squares correspond to regular digraphs under the isomorphism described in Theorem 1.

\underline{Definition 3}. An element A = (a_{i,j}) of M_{m}(ℤ) is a generalized magic square if

∑_{i=1}^{m} a_{i,j} = ∑_{l=1}^{m} a_{k,l}

for all j, k ∈ {1, …, m}.

The set of generalized magic squares in M_{m}(ℤ) is a subring of M_{m}(ℤ), which we denote by M_{m}^{0}(ℤ).

\underline{Definition 4}. An object (Y, f, g) of DG_{X} is regular if f and g are surjective and

|f^{−1}(x)| = |g^{−1}(x)| = |Y |/|X|

for all x ∈ X, where | · | denotes the cardinality of a set.

\underline{Remark 4}. The directed graph represented by a regular object (Y, f, g) is a (|Y |/|X|) – regular digraph in the usual sense (see e.g. [1]), that is, a directed graph such that the in–degree and the out–degree of each vertex is equal to |Y |/|X|.

Let DG_{X}^{0} be the subcategory of DG_{X} consisting of the objects of DG_{X} that are regular. If (Y_{1}, f_{1}, g_{1}) and (Y_{2}, f_{2}, g_{2}) are objects of DG_{X}^{0}, then both (Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2}) and (Y_{1}, f_{1}, g_{1}) ⊕ (Y_{2}, f_{2}, g_{2}) are objects of DG_{X}^{0}. Thus, if we set

M_{X}^{0} = DG_{X}^{0}/ ≅, R_{X}^{0} = ℤ[M_{X}^{0}]/I^{0},

where I^{0} is the ideal of ℤ[M_{X}^{0}] generated by elements of the form x ⊕ y − x − y, with x, y ∈ M_{X}^{0}, then R_{X}^{0} becomes a subring of R_{X}.

\underline{Theorem 2}. The isomorphism described in Theorem 1 induces an isomorphism between R_{X}^{0} and M_{m}^{0}(ℤ).

\underline{Proof}. Let ψ̃: R_{X} → M_{m}(ℤ) be the isomorphism constructed in the proof of Theorem 1 and let V = ∑_{j=1}^{k} n_{j}(Y_{j}, f_{j}, g_{j}) ∈ ℤ[M_{X}] be a representative of Ṽ ∈ R_{X}. For 1 ≤ j ≤ k, we assume that Y_{j} = {y_{j,i} | 1 ≤ i ≤ l_{j}} and denote by f_{j,i}, g_{j,i}, the restrictions of f_{j}, g_{j} to the set {y_{j,i}}. If ψ̃(Ṽ) = (ν_{a,b}) ∈ M_{m}(ℤ), with 1 < a, b < m, then we have

ν_{a,b} = ∑_{j=1}^{K} n_{j}|f_{j}^{−1}(x_{a}) ∩ g_{j}^{−1}(x_{b})|;

hence, we have

∑_{a=1}^{m} ν_{a,b} = ∑_{j=1}^{k} n_{j}|( ⋃_{a=1}^{m} f_{j}^{−1}(x_{a})) ∩ g_{j}^{−1}(x_{b})| = ∑_{j=1}^{k} n_{j}|g_{j}^{−1}(x_{b})| = ∑_{j=1}^{k} \frac{n_{j}|Y |}{|X|}.

Similarly, we have

∑_{b=1}^{m} ν_{a,b} = ∑_{j=1}^{k} n_{j}|f_{j}^{−1}(x_{a}) ∩ (⋃_{b=1}^{m} g_{j}^{−1}(x_{b}))| = ∑_{j=1}^{k} n_{j}|f_{j}^{−1}(x_{a})| = ∑_{j=1}^{k} \frac{n_{j}|Y |}{|X|}.

Thus, it follows that (ν_{a,b}) ∈ M_{m}^{0}(ℤ).

7. Grothendieck Topologies. In the previous sections we regarded directed graphs as the objects in the category of pairs of mappings of finite sets. In this section, we consider the category of single mappings of finite sets, which is essentially a Grothendieck topology on the category of finite sets.

\underline{Definition 5}. We define S to be the category whose objects are mappings of finite sets ψ: A → B and whose morphisms from ψ: A → B to ψ′: A′ → B′ are pairs of mappings α: A → A′ and β: B → B′, such that β ∘ ψ = ψ′ ∘ α.

\underline{Definition 6}. Given a finite set X, we define S_{X} to be the subcategory of S whose objects are the mappings ϕ: Z → X in S and whose morphisms from ϕ: Z → X to ϕ′: Z′ → X are maps ν: Z → Z′ such that ϕ = ϕ′ ∘ ν.

\underline{Remark 5}. The category S can be regarded as a Grothendieck topology on the category of finite sets by using the objects of S_{X} as a covering of X, and therefore the category of finite sets equipped with this topology is a site (see [2, 3]).

Given objects (Y, f, g) and (Z, ϕ) of DG_{X} and S_{X}, respectively, let W be the pullback of g: Y → X and ϕ: Z → X, that is, W = {(y, z) ∈ Y × Z | g(y) = ϕ(z)}. Then we define the action of (Y, f, g) on (Z, ϕ) by (Y, f, g) · (Z, ϕ) = (W, f ∘ π_{Y}), where π_{Y}: W → Y is the natural projection. If (M_{X}, ⊙) denotes the monoid considered in Proposition 3, then it follows from the next theorem that M_{X} acts on the set Obj(S_{X}) of objects of S_{X}.

\underline{Theorem 3}. Given a pair of objects (Y_{1}, f_{1}, g_{1}) and (Y_{2}, f_{2}, g_{2}) of DG_{X} and an object (Z, ϕ) of S_{X}, we have

(Y_{1}, f_{1}, g_{1}) · ((Y_{2}, f_{2}, g_{2}) · (Z, ϕ)) = ((Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2})) · (Z, ϕ).

\underline{Proof}. We have (Y_{2}, f_{2}, g_{2}) · (Z, ϕ) = (W, f_{2} ∘ π_{Y_{2}}), where π_{Y_{2}}: W → Y_{2} is the natural projection and W = {(y_{2}, z) ∈ Y_{2} × Z | g_{2}(y_{2}) = ϕ(z)}. Thus, we obtain

(Y_{1}, f_{1}, g_{1}) · ((Y_{2}, f_{2}, g_{2}) · (Z, ϕ)) = (W′, f_{1} ∘ π_{Y_{1}}),

with

W′ = {(y_{1}, y_{2}, z) ∈ Y_{1} × Y_{2} × Z | g_{1}(y_{1}) = (f_{2} ∘ π_{Y_{2}})(y_{2}, z) = f_{2}(y_{2})},

π_{Y_{1}}: W′ → Y_{1}, π_{Y_{2}}: W′ → Y_{2}, and (f_{1} ∘ π_{Y_{1}})(y_{1}, y_{2}, z) = f_{1}(y_{1}). On the other hand, we have

(Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2}) = (U, f_{1} ∘ π′_{Y_{1}}, g_{2} ∘ π′_{Y_{2}}),

where π′_{Y_{1}}: U → Y_{1} and π′_{Y_{2}}: U → Y_{2} are natural projections and

U = {(y_{1}, y_{2}) ∈ Y_{1} × Y_{2} | g_{1}(y_{1}) = f_{2}(y_{2})};

hence, it follows that

((Y_{1}, f_{1}, g_{1}) ⊙ (Y_{2}, f_{2}, g_{2})) · (Z, ϕ) = (U′, (f_{1} ∘ π′_{Y_{1}}) ∘ π′_{U}),

with

U′ = {(y_{1}, y_{2}, z) ∈ Y_{1} × Y_{2} × Z | g_{2} ∘ π′_{Y_{2}}(y_{1}, y_{2}) = g_{2}(y_{2}) = ϕ(z)},

π′_{U}: U′ → U and ((f_{1} ∘ π′_{Y_{1}}) ∘ π′_{U})(y_{1}, y_{2}, z) = (f_{1} ∘ π′_{Y_{1}})(y_{1}, y_{2}) = f_{1}(y_{1}). Therefore, we have W′ = U and f_{1} ∘ π_{Y_{1}} = (f_{1} ∘ π′_{Y_{1}}) ∘ π′_{U}; hence, the theorem follows.

\underline{References}

1. G. Chartrand, M. Behzad, and L. Lesniak–Foster, Graphs and Digraphs, Prindle, Weber, and Schmidt, Boston, 1979.

2. S. MacLane and I. Moeerdijk, Sheaves in Geometry and Logic, Springer–Verlag, Heidelberg, 1992.

3. G. Tamme, Introduction to Étale Cohomology, Springer–Verlag, Heidelberg, 1994.

4. R. Walter, Categories and Computer Science, Cambridge Univ. Press, Cambridge, 1991.

Min Ho Lee Department of Mathematics University of Northern Iowa Cedar Falls, IA 50614 email: lee@math.uni.edu