Improved bounds on the size of the smallest representation of relation algebra \(32_{65}\) (Q2159495)

The conjecture that a finite symmetric integral relation algebra is finitely representable if it has a flexible atom has been proved whenever all the diversity atoms are flexible (because all cycles occur) or there is a minimal set of cycles that make an atom flexible. Probabilistic methods work in both cases but yield only large bounds. This paper reports significant progress on the size of representations of relation algebras with a minimally flexible atom. There is a spectacular improvement in the upper bound (from exponential to polynomial in the number of atoms) plus an improvement in the lower bound. The simplest example of a relation algebra with a minimally flexible atom is shown to have a representation on 1024 elements and a lower bound illustrated by a nice picture of 26 points connected by colored lines.