Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Category & Graph Theory

2 views
Skip to first unread message

Adam Smith

unread,
Mar 20, 2011, 3:16:36 PM3/20/11
to
I am not a mathematician put try to keep abreast of development in the
field, since we can't do with out it.

My questions are -
[i] What is the difference between Graph Theory and Category Theory?
[ii] Are there restrictions on the complexity of edges that can be
conceptualized in the graph.
Ex:
V = {1, 2, 3, 4, 5, 6, 7}
E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}, {6, 7}}.

Is it possible to have more complex edges incorporating three
or more vertices? probably they are no longer edges and therein
lies my confusion. i.e. is
E = {{1, 2}, {1, 2,}, {1, 3}, {1, 4}, {1, 5}, {1, 2, 4}, {1, 2, 4}, ...
{6, 7}}.

valid?

Thanks!

Arturo Magidin

unread,
Mar 20, 2011, 5:20:22 PM3/20/11
to
On Mar 20, 2:16 pm, Adam Smith <adamsm...@nospam.com> wrote:
> I am not a mathematician put try to keep abreast of development in the
> field, since we can't do with out it.

It is hard enough for an active mathematician to keep abreast of
developments in his or her own subfield; I find it hard to believe
that *anyone*, even an active mathematician of the first rank, could
even be dimly aware of the developments in *all* of mathematics, let
alone keep abreast of them.

> My questions are -
> [i] What is the difference between Graph Theory and Category Theory?

Graph theory studies "graphs"; these are structures made up of two
sets, V a set of "vertices", and E a set of "edges" which is a subset
of V x V.

Category Theory studies categories. A category is an object consisting
of two collections (that need not be sets; they can be proper classes
or even undefined concepts), "objects" O, and for any two objects a
and b (not necessarily distinct), a collection of "arrows" C(a,b).

In addition, there are three primitive notions:

dom: an assignation from the collection of all arrows to the
collection of all objects that assigns to every arrow a "domain";

cod: an assignation from the collection of all arrows to the
collection of all objects that assigns to every arrow a "codomain";

moreover, an arrow f is in C(a,b) if and only if dom(f) = a and
cod(f)=b.

Finally, there is a notion of "composition" that is a partially
defined operation on the arrows of C: for every pair of arrows f and
g, if cod(f) = dom(g), then there exists an arrow x called "the
composition of f and g", x=gof.

Composition is required to be assocative: ho(gof) = (hog)of, provided
they all exist. And for every object a, there is an arrow in C(a,a)
called id_a (the identity of a) with the property that for every
objects b and c and every arrows h in C(b,a) and k in C(a,c), (id_a)oh
= h and ko(id_a) = k.

As you can see, they are very different stuff.

> [ii] Are there restrictions on the complexity of edges that can be
> conceptualized in the graph.
> Ex:
> V = {1, 2, 3, 4, 5, 6, 7}
> E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}, {6, 7}}.
>
>         Is it possible to have more complex edges incorporating three
>         or more vertices?

In the usual notion of "graph", no. The concept you are looking for is
called a "hypergraph" (http://en.wikipedia.org/wiki/Hypergraph).

--
Arturo Magidin

Adam Smith

unread,
Mar 20, 2011, 8:28:22 PM3/20/11
to
On 3/20/2011 2:20 PM, Arturo Magidin wrote:
> On Mar 20, 2:16 pm, Adam Smith<adamsm...@nospam.com> wrote:
>> I am not a mathematician put try to keep abreast of development in the
>> field, since we can't do with out it.
>
> It is hard enough for an active mathematician to keep abreast of
> developments in his or her own subfield; I find it hard to believe
> that *anyone*, even an active mathematician of the first rank, could
> even be dimly aware of the developments in *all* of mathematics, let
> alone keep abreast of them.


THANKS! Arturo - well, i do admit i cannot keep abreast of everything,
just superficially enough that I can avail myself of new tools for research.

Your explanation was superb, and thanks for the guidance to
'hybergraphs', THANKS again.

Frederick Williams

unread,
Mar 22, 2011, 7:36:50 PM3/22/11
to
Arturo Magidin wrote:
>
> On Mar 20, 2:16 pm, Adam Smith <adamsm...@nospam.com> wrote:

> > [i] What is the difference between Graph Theory and Category Theory?
>

> [...]


>
> As you can see, they are very different stuff.

I'm feeling argumentative :-).

See the second paragraph (it starts "A category is a graph with...") of
Section 2 of Chapter 1 of Mac Lane's 'Categories for the Working
Mathematician'.

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

Arturo Magidin

unread,
Mar 23, 2011, 11:44:59 AM3/23/11
to
On Mar 22, 6:36 pm, Frederick Williams <freddywilli...@btinternet.com>
wrote:

> Arturo Magidin wrote:
>
> > On Mar 20, 2:16 pm, Adam Smith <adamsm...@nospam.com> wrote:
> > > [i] What is the difference between Graph Theory and Category Theory?
>
> > [...]
>
> > As you can see, they are very different stuff.
>
> I'm feeling argumentative :-).
>
> See the second paragraph (it starts "A category is a graph with...") of
> Section 2 of Chapter 1 of Mac Lane's 'Categories for the Working
> Mathematician'.

And then you drop all the context...

First, in section one he discusses "metagraphs" and "metacategories".
A metagraph is a collection of objects and a collectio of arrows,
together with an assignment of "domain" and "codomain" from arrows to
objects. A metacategory is a metagraph with identity (an assignation
from objects to arrows) and "composition" (an operation on arrows that
is associative and satisfeis the unit laws). Section 2 then first says
that

"a category is an interpretation of the category axioms within set
theory."

Then he says "A graph (also called a "diagram scheme") is a set of
objects O and a set of arrows A, and two functions, domain and
codomain. In this graph, the set of composable pairs of arrows is the
set A x_O A = {<g,f> | g,f arrows, dom(g) = cod(f)} called the
"product over O". A category is a graph with two additional
functions..."

So his definition of **graph** is my definition of category; in fact,
he points out that what he is calling a graph is not universally
called a 'graph' ("also called a 'diagram scheme'").

So, Mac Lane is hardly asserting that "category" in the sense of
category theory and "graph" in the sense of graph theory are the same.
--
Arturo Magidin

0 new messages