Strongly representable atom structures of relation algebras

A relation algebra atom structure 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 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 , we construct a relation algebra atom structure and prove, for infinite , that is strongly representable if and only if the chromatic number of is infinite. A construction of Erdös shows that there are graphs () with infinite chromatic number, with a non-principal ultraproduct whose chromatic number is just two. It follows that is strongly representable (each ) but is not.