Strongly representable atom structures of relation algebras (Q2781354)

The atom structure \(\alpha\) of an atomic relation algebra is said to be strongly representable if the complex algebra of \(\alpha\) is a representable relation algebra. This paper proves that the class of strongly representable atom structures of atomic relation algebras is not closed under the formation of ultraproducts, and therefore not an elementary class. This result solves a problem posed by the reviewer in ``Some varieties containing relation algebras'' [Trans. Am. Math. Soc. 272, 501-526 (1982; Zbl 0515.03039)]. The heart of the proof is the construction, from any symmetric irreflexive binary relation \(\Gamma\), of an atom structure \(\alpha(\Gamma)\) with the remarkable property that \(\alpha(\Gamma)\) is strongly representable if and only if the chromatic number of \(\Gamma\) is infinite. Using a result of Erdös, that there exist finite graphs with arbitrarily large girth and chromatic number, the authors construct, for each positive integer \(r\), a graph \(\Gamma_r\) with girth greater than \(r\) and infinite chromatic number. Every \(\alpha(\Gamma_r)\) is strongly representable, but every non-principal ultraproduct of the atom structures \(\alpha(\Gamma_r)\) has infinite girth, consequently has chromatic number 2, and is therefore not strongly representable.