Characterization of the \((\leq 3)\)-hypomorphy classes with the aid of interdictions (Q2869848)

The authors consider relations \(R\) on sets \(E\) as functions \(R:E\times E\to \{ +, -\} \). Two relations \(R\) and \(R^\prime\) on the same base set \(E\) are called \((\leq n)\)-hypomorphic iff, for every subset \(F\) of \(E\) with \(|F|\leq n\), we have that \(R|_{F\times F} \) and \(R|_{F'\times F^\prime} \) are isomorphic.NEWLINENEWLINENEWLINEGiven two relations \(R\) and \(R^\prime\) on the same base set \(E\) we define the difference relation \(D_{R,R^\prime} (x,y)\) by \(D_{R,R^\prime} (x,y)\) being true iff \(x=y\) or there is a sequence \(x=x_0 , \ldots , x_n = y\) so that, for all \(i=1, \ldots , n\), we have that \(R(x_{i-1} ,x_i ) \not= R(x_i ,x_{i-1} )\), \(R^\prime(x_{i-1} ,x_i ) \not= R^\prime(x_i ,x_{i-1} )\) and \(R(x_{i-1} ,x_i ) \not= R'(x_{i-1} , x_i )\). The difference relation is an equivalence relation.NEWLINENEWLINEA peak is a relation on a three-element set \(\{ a,b,c\} \) so that \(R(a,b)=R(c,b)\), \(R(b,a)=R(b,c)\), \(R(a,b)\not=R(b,a)\) and \(R(a,c)=R(c,a)\). A prohibited Rauzien (named after Rauzy, the deceased third author) is a relation on a \(4\)-element set \(\{ x,y,z,t\} \) so that \(R(x,y)\not= R(y,x)\), \(R(x,z)=R(z,x)=-\), \(R(y,z)=R(z,y)=+\), and so that (\(R(x,t)=R(t,x)\) and \(R(y,t)\not=R(t,y)\)) or (\(R(x,t)\not=R(t,x)\) and \(R(y,t)=R(t,y)\)).NEWLINENEWLINEThe authors prove that, for a relation \(R\), there is a relation \(R^\prime\) with the same base set that is \((\leq 3)\)-hypomorphic to \(R\) and so that the difference relation \(D_{R,R^\prime} \) has exactly one equivalence class iff \(R\) is connected, without peak and without prohibited Rauzien.