Permutation of elements in double semigroups

Double semigroups have two associative operations $\circ ,\bullet$ related by the interchange relation: $(a\bullet b)\circ (c\bullet d)\equiv (a\circ c)\bullet (b\circ d)$. Kock \cite{Kock2007} (2007) discovered a commutativity property in degree 16 for double semigroups: associativity and the interchange relation combine to produce permutations of elements. We show that such properties can be expressed in terms of cycles in directed graphs with edges labelled by permutations. We use computer algebra to show that 9 is the lowest degree for which commutativity occurs, and we give self-contained proofs of the commutativity properties in degree 9.