Re: definition of K_n in graph theory
From: Ron Sperber (ronsperber_at_optonline.net)
Date: 12/28/04
- Next message: Michael Mendelsohn: "Re: Is zero even or odd?"
- Previous message: Scott Seidman: "Re: Is zero even or odd?"
- In reply to: Marc Olschok: "Re: definition of K_n in graph theory"
- Next in thread: Ron Sperber: "Re: definition of K_n in graph theory"
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 28 Dec 2004 16:09:01 -0500
Marc Olschok wrote:
> Ron Sperber <ronsperber@optonline.net> wrote:
>
>>Marc Olschok wrote:
>>[...]
>>
>>>There are at least two slightly different descriptions:
>>>
>>>(1) yours above without the explicit use of cartesian products:
>>>here a graph consists of two sets E and V, together with maps
>>>s: E ---> V and t: E ---> V.
>>>A graph homomorphism from (E,V,s,t) to (E',V',s',t') then consists
>>>of two maps f_e: E ---> E' and f_v: V ---> V' such that
>>>s'(f_e(x) = f_v(s(x)) and t'(f_e(x) = f_v(t(x)) for all x in E.
>>>In short: a graph is a contravariant (set valued) functor on a the
>>>category C with two objects A, D and exactly four morphisms, such
>>>that |C(A,D)|=2 and |C(D,A)|=0
>>>(it is easier to draw than to write down :-).
>>>A graph homomorphism between two such graphs is just a
>>>natural transformation.
>>
>>[...]
>>
>>>(2) throwing together edges and vertices, allowing collapsing:
>>>here a graph is a set W together with two idempotent maps
>>>s: W ---> W and t: W ---> W such that s(t(x))= t(x) and t(s(x))=s(x)
>>>for all x in W.
>>>A graph homomorphism f: (W,s,t) ---> (W',s',t') is a map f: W ---> W
>>>satisfying the same compatibility conditions as in (1).
>>>In short: a graph is an M-set, where M is the monoid
>>>< s,t | ss=s, tt=t, st=t, ts=s >
>>
>>[...]
>>Ah, so we do need sets of some kind, so once again we're back to the
>>question of what is _the_ graph K_n. Of course this is quite a pedantic
>>point, but it was what this all started with.
>
>
> Actually, I never quite understood the relevance of the original
> question. After all you rarely ask, 'what _is_ the 3-element group?'.
> Graph theory should not differ from e.g. group theory with respect
> to such questions.
>
>
>> If we go to a
>>category-theoretic point of view, I suppose the right thing to do is
>>take a skeleton of the category Graph with the usual functor
>>F:Graph->Skel(Graph) and define K_n=F(your favorite description of K_n).
>
>
> Of course the instant generalisation is to allow other target categories
> different from Sets; so we can speak of 'graphs in groups',
> 'graphs in vector spaces' etc.
>
> But the categorical point of view can do more. You can look at the two
> small categories above, that encode the axioms for graphs in the above.
> These provide in a sense the 'absolute version of the theory' independent
> of a particular interpretation in the target category.
>
> Marc
I understand what you're saying. It only is relevant because someone
gave a definition of K_n as some equivalence class of graphs and taking
equivalence classes when your objects don't form a set is a little
dubious. I'd much rather define K_n as _a_ graph with n vertices and
every pair of distinct vertices joined by exactly one edge rather than
_the_ graph and just recognize that any 2 such graphs are isormorphic.
And you're right that rarely does such a distinction come up in any
meaningful fashion, and now I think anything further on this would be
beating the proverbial deceased equine.
- Next message: Michael Mendelsohn: "Re: Is zero even or odd?"
- Previous message: Scott Seidman: "Re: Is zero even or odd?"
- In reply to: Marc Olschok: "Re: definition of K_n in graph theory"
- Next in thread: Ron Sperber: "Re: definition of K_n in graph theory"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
