Strongly representable atom structures

Robin Hirsch and Ian Hodkinson

A relation algebra atom structure $\alpha$ is said to be strongly representable if all 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 atoms structures is not closed under ultraproducts and is therefore not elementary.

Our proof uses graphs \Gamma_r (r<\omega), discovered by Erdos, that cannot be coloured with any finite number of colours but where all of their `small' induced subgraphs can be coloured with just two colours.  From these graphs we build  `rainbow atom structures' \alpha(\Gamma_r).  The fact that \Gamma_r cannot be coloured finitely is enough to prove that \alpha(\Gamma_r)` is strongly representable and the fact that `small induced subgraphs' of each \Gamma_r can be two-coloured is enough to prove that a non-principal ultraproduct \Pi_D \; \Gamma_r can be two-coloured and this suffices to show that \Pi_D \; \alpha(\Gamma_r) is not strongly representable.  Thus the class of strongly representable atom structures is not closed under ultraproducts.

Postscript file