From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/1853 Path: news.gmane.org!not-for-mail From: Eduardo Dubuc Newsgroups: gmane.science.mathematics.categories Subject: Re: Inevitability of ordering products Date: Wed, 14 Feb 2001 13:40:08 -0500 (EST) Message-ID: <200102141840.NAA09452@cogito.math.uqam.ca> References: <3A88BE0C.C3CA8E04@kestrel.edu> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241018152 819 80.91.229.2 (29 Apr 2009 15:15:52 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:15:52 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Thu Feb 15 16:08:27 2001 -0400 Return-Path: Original-Received: (from Majordom@localhost) by mailserv.mta.ca (8.11.1/8.11.1) id f1FJZ8N06247 for categories-list; Thu, 15 Feb 2001 15:35:08 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f In-Reply-To: <3A88BE0C.C3CA8E04@kestrel.edu> from "Dusko Pavlovic" at Feb 12, 2001 08:54:36 PM X-Mailer: ELM [version 2.5 PL2] Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 35 Original-Lines: 63 Xref: news.gmane.org gmane.science.mathematics.categories:1853 Archived-At: 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.