Small representations of the relation algebra \(\mathcal E_{n+1}(1,2,3)\) (Q1344846)

The finite relation algebra \({\mathcal E}_{n+ 1}(1, 2,3)\) is defined as follows. The algebra is symmetric, i.e. \(\breve x= x\) for every \(x\), and its atoms are \(1^{^ ,},a_ 1, a_ 2,\dots, a_ n\). Applying combinatorial methods, the authors prove that \({\mathcal E}_{n+ 1}(1, 2,3)\) is finitely representable, for all \(n\geq 1\), by at most \((2+ o(1))n^ 2\) elements as \(n\to\infty\), and they explicitly construct a representation of size \(\leq 4\cdot 5n^ 2\) for every \(n\geq 1\). Another proof of finite representability of \({\mathcal E}_{n+ 1}(1, 2,3)\) is also given, based on probabilistic methods which originate with Erdős.