Graphical Compositions of Semirigid Equivalence Relations (Clone Theory and Discrete Mathematics・Algebra and Logic Related to Computer Science)
Masahiro Miyakawa, Maurice Pouzet, Ivo G. Rosenberg, Hisayuki Tatsumi · Institutional Repositories DataBase (IRDB) · 2013
A system of equivalence relations on a base set $A=\{1, \ldots,n\}$ is semirigid if only the trivial functions (i.e., projections and constant functions) preserve all the equivalence relation jointly.First we explore properties of semirigid systems $R$ of equivalence relations, especially we show that the graph correspond- ing to a such system has doubly-comectedness property.We show that $R=\{\theta_{12},\theta_{2{\},}\theta_{n-1,*},\theta_{*1}\}$ (a loop of $n$ nodes connected by distinctively colored $n$ edges) is semirigid where $\theta:j$ is a minimum partition of $A$ which has sole non-singleton block $\{i,j\}$ .In the last part of the paper we show that $n$ is the minimum of $|R|$ such that $R$ , a subset of $\{\theta_{:j} : 1\leq i