From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/1254 Path: news.gmane.org!not-for-mail From: John Stell Newsgroups: gmane.science.mathematics.categories Subject: graph classifiers Date: Wed, 27 Oct 1999 16:30:25 +0100 Organization: Keele University Message-ID: <38171A91.7CCEF897@cs.keele.ac.uk> 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 1241017679 30205 80.91.229.2 (29 Apr 2009 15:07:59 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:07:59 +0000 (UTC) To: categories@mta.ca Original-X-From: cat-dist Wed Oct 27 15:36:36 1999 Original-Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id NAA01561 for categories-list; Wed, 27 Oct 1999 13:52:18 -0300 (ADT) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Mailer: Mozilla 4.08 [en] (WinNT; I) Original-Sender: cat-dist@mta.ca Precedence: bulk Original-Lines: 42 Xref: news.gmane.org gmane.science.mathematics.categories:1254 Archived-At: The classifier, \Omega, for subgraphs has two nodes and five edges. The bi-Heyting algebra of subgraphs of a graph has two complement like operators, $\neg$ and $\suppl$. These satisfy $G \meet \neg G = \bot$ and $G \join \suppl G = \top$. One of these ($\neg$) arises from an endomorphism of $\Omega$ but the other does not. The operations $\neg$ and $\suppl$ are nicely dual in some ways but only one can be described in terms of $\Omega$. Is there some kind of explanation for this? It is possible to find a graph $\Delta$ and to describe a given subgraph as a morphism to $\Delta$ and to obtain $\suppl$ as an endomorphism of $\Delta$. But although there is a morphism from $\Delta$ to $\Omega$, we don't get $\neg$ via any endomorphism of $\Delta$. $\Delta$ has four nodes corresponding to a classification of nodes as (1) out (2) in and with all incident edges in (3) in and with all incident edges out (4) in and with some incident edges in and some out. Of course this is analogous to the edges in $\Omega$. There are four kinds of edge identified by $\Omega$ (working with a version of $\Omega$ for undirected graphs) (1) in (2) out and with all incident nodes out (3) out and with all incident nodes in (4) out and with some incident nodes out and some in. Is there a formal sense in which $\Delta$ and $\Omega$ are dual to each other? Is there a better way to view $\suppl$ as coming from some kind of classifier of graphs? Does anyone have any comments or suggestions for relevant literature? John Stell -------------------------------------------------------------------- Dr John Stell Department of Computer Science email john@cs.keele.ac.uk Keele University Keele, Staffordshire, telephone +44 1782 584083 ST5 5BG U. K. fax +44 1782 713082 http://www.keele.ac.uk/depts/cs/Staff/Homes/John/homepage.html --------------------------------------------------------------------