Improved bounds on the size of the smallest representation of relation algebra $32_{65}$

Abstract

In this paper, we shed new light on the spectrum of the relation algebra we call $A_n$, which is obtained by splitting the non-flexible diversity atom of $6_7$ into $n$ symmetric atoms. Precisely, we show that the minimum value in $\text{Spec}(A_n)$ is at most $2n^{6+o(1)}$, which is the first polynomial bound and improves upon the previous bound due to Dodd \& Hirsch (\textit{J. Relational Methods in Computer Science} 2013). We also improve the lower bound to $2n^2+4n+1$, which is asymptotically double the trivial bound of $n^2+2n+3$. In the process, we obtain stronger results regarding $\text{Spec}(A_2)=\text{Spec}(32_{65})$. Namely, we show that $1024$ is in the spectrum, and no number smaller than 26 is in the spectrum. Our improved lower bounds were obtained by employing a SAT solver, which suggests that such tools may be more generally useful in obtaining representation results.

arXiv comment17 pages