Atlas home || Conferences | Abstracts | about Atlas

AAA61: 61st Workshop on General Algebra + 16th Conference of Young Algebraists
February 2-4, 2001
TU Darmstadt
Darmstadt, Germany

View Abstracts
Conference Homepage

Strongly representable relation algebra atom structures
by
Robin Hirsch
Computer Science, University College, London
Coauthors: Ian Hodkinson (Computing, Imperial College, London)

A relation algebra atom structure \alpha is said to be strongly representable if all atomic relation algebras with that atom structure are representable. This is equivalent to saying that the complex algebra ( Cm)

 
\alpha is a representable relation algebra. We show that the class of all strongly representable relation algebra atom structures is not closed under ultraproducts and is therefore not elementary. This answers a question of Maddux (1982).

Our proof is based on the following construction. From an arbitrary undirected, loop-free graph \Gamma, we construct a relation algebra atom structure \alpha(\Gamma) and prove, for infinite \Gamma, that \alpha(\Gamma) is strongly representable if and only if the chromatic number of \Gamma is infinite. A construction of Erdös shows that there are graphs \Gammar (r < \omega) with infinite chromatic number, with a non-principal ultraproduct \prodD\Gammar whose chromatic number is just two. It follows that \alpha(\Gammar) is strongly representable (each r < \omega) but \prodD(\alpha(\Gammar)) is not.

Date received: January 8, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafo-58.