Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Strongly representable atom structures of relation algebras


Authors: Robin Hirsch and Ian Hodkinson
Journal: Proc. Amer. Math. Soc. 130 (2002), 1819-1831
MSC (2000): Primary 03G15; Secondary 03C05, 05C80
Published electronically: May 23, 2001
MathSciNet review: 1887031
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

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 $\mathop{\mathfrak{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 $\Gamma_r$($r<\omega$) with infinite chromatic number, with a non-principal ultraproduct $\prod_D\Gamma_r$ whose chromatic number is just two. It follows that $\alpha(\Gamma_r)$ is strongly representable (each $r<\omega$) but $\prod_D(\alpha(\Gamma_r))$ is not.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03G15, 03C05, 05C80

Retrieve articles in all journals with MSC (2000): 03G15, 03C05, 05C80


Additional Information

Robin Hirsch
Affiliation: Department of Computer Science, University College, Gower Street, London WC1E 6BT, United Kingdom
Email: r.hirsch@cs.ucl.ac.uk

Ian Hodkinson
Affiliation: Department of Computing, Imperial College, Queen’s Gate, London SW7 2BZ, United Kingdom
Email: imh@doc.ic.ac.uk

DOI: http://dx.doi.org/10.1090/S0002-9939-01-06232-3
PII: S 0002-9939(01)06232-3
Keywords: Elementary class, complex algebra, relation algebra, representation
Received by editor(s): October 20, 2000
Received by editor(s) in revised form: November 27, 2000
Published electronically: May 23, 2001
Additional Notes: This research was partially supported by UK EPSRC grants GR/L85961, GR/K54946, GR/L85978. Thanks to Rob Goldblatt for valuable additions and suggestions, and Imre Leader for a helpful discussion about the graph-theoretic aspects. Thanks also to the referee for suggesting useful improvements to the paper.
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2001 American Mathematical Society