How to prove that a binary relation is a strongly rigid relation? i.e. Polρ only contains projections

Question

I first quote a definition from Clone theory in Universal Algebra: A binary relation $\rho$ on a set U is strongly rigid if every universal algebra on U such that $\rho$ is a subuniverse of its square is trivial, i.e., the clone preserving ρ has only projections. It is known that there are only two strongly rigid relations on a 3-element domain. I found that

1) On a 4-element domain {0,1,2,3}, the following binary relation is possibly a strongly rigid relation: {(0,1), (0,2), (0,3), (1,0), (1,2), (2,0), (2,1), (2,3), (3,1), (3,2)}

2) On a 5-element domain {0,1,2,3,4}, the following relation is possibly a strongly rigid relation: {(0,2), (0,3), (0,4), (1,0), (1,3), (1,4), (2,0), (2,1), (2,4), (3,0), (3,1), (3,2), (3,4), (4,0), (4,1), (4,2), (4,3)}.

 Could you let me know if there is an easy way to prove the above statements?

This could be an algebraic proof, or by using a computer program.

Answer 1

I do not see an easy way to prove it. The characterization you mention was published in the 1970's by Anne Fearnley, and the proof was a nicely organized but mildly tedious examination of cases based on the size of $\rho$. I do not think you will completely avoid such in showing your candidates are strongly rigid.

Something which might help is a characterization of pairs $\langle \rho' , f \rangle$ where any relation containing $\rho'$ is preserved by a nontrivial $f$. Fearnly uses a constant function and the corresponding ordered pair to show irreflexivity of strongly rigid relations. If you had a triangle and a partition of U into three parts, you could use a trivalent function to show some relations are not strongly rigid by mapping every pair to one of the six directed edges of the triangle. Alternatively, use Rosenberg's classification of minimal clones as a testbed for showing relations to be not strongly rigid. You might even have a theorem like rho is strongly rigid iff rho is not preserved by any of Rosenberg's functions, but you would have to prove the theorem first.