A reduced upper bound for an edge-coloring problem from relation algebra

Abstract

Starting with the Johnson scheme J(14, 7), we construct an edge-coloring of $K_{N}$ (for $N = 3432$) in colors red, dark blue, and light blue, such that there are no monochromatic blue triangles and such that the coloring satisfies a certain strong universal-existential property. The edge-coloring of $K_{N}$ depends on a cyclic coloring of $K_{17}$ whose two color classes contain no monochromatic $K_{4}$, $K_{4,3}$, or $K_{5,2}$ subgraphs. This construction yields the smallest known representation of the relation algebra $32_{65}$, reducing the upper bound from 8192 to 3432.