New results on the common consequent index of a binary relation (Q1971799)

Let \(R\) be a binary relation on a finite set \(V\). For \(a\in V\), denote by \(aR= \{x\in V; (a,x)\in R\}\) and for a pair \((a,b)\in V^2\), \(a\neq b\), let \(s>0\) be the least integer with \(aR^s\cap bR^s\neq \emptyset\). If such an \(s\) exists, it is denoted by \(L_R(a,b)\). Moreover, set \(L(R)= \max L_R(a, b)\), where \((a,b)\) runs through \(V^2\); if no such \((a,b)\in V^2\) exists, \(L(R)= 0\). \(L(R)\) is called a common consequent of \(R\). Several authors stated various estimations on \(L(R)\) (e.g., A. Paz, in 1971, gave \(L(R)\leq{n(n- 1)\over 2}\)). The authors obtain a better estimation for symmetric and reducible relations. These relations are introduced and characterized by means of \(L(R)\) in the paper.