categories: Re: Inevitability of ordering products

[Eduardo Dubuc <edubuc@math.uqam.ca>]

This is concerning the mail of Dusko in reply to my mail:

> 
> Eduardo Dubuc wrote:
> 
> > what sense has the concept of unlabeled graph ?
> >
> > try to put an unlabeled graph inside a computer  ?
> 
> you mean unordered? i would implement it as an ordered graph, with an
> additional involutive map on the edges, ie
> 
>         Edges <--inv-- Edges ==dom,cod==> Nodes
>         dom.inv = cod
>         inv.inv = id
> 
> --- which, in a way, confirms that
>


yours is not an answer to my question, which I shall explain now (I
thought that it needed no explanations)

by an unlabeled graph i mean the drawing of a graph, in paper, say, or a
graph buildt in space, the skeleton of a building for example. It has
vertices and edges, and everybody knows what it is. Mathematically you
could say a symetric relation on its (finete) set of vertices. But not
quite so ...

If you have n vertices, you have n! different labeling. Each labeling
gives you a different labeled graph.

The minute you have a set (in the mathematical sense) of vertices, you
have a labeling. Namely, the elements of that set are the labels!. So,
with a symetric relation (in the mathematical sense) what you got is a
labeled  graph. Not an unlabeled graph !.

And you become well aware of this fact when you want to put a concrete
unlabeled graph (say, the skeleton of a  building) inside a computer !!

REMEMBER I rise the question on unlabeled graph related to the question
that we were discussing:

INEVITABILITY OF NAMING (IN MATHEMATICS) 
 (naming is not the same as labeling ?)  

>> well, unlabeled graph has to be a quotient by an equivalent relation 
...

I said that. It seems possible. I explain now the  ...

  Given two graphs R, S (symetric relations) on a finite set X (of 
vertices), consider the natural action of the symetric group of X on the
power set of X x X. Then, R =~ S iff they are in the same orbit. The
elements of the quotient set are the unlabeled graphs.

    e.d.