Strongly representable atom structures of relation algebras

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 $\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.