Tolerances induced by irredundant coverings.

DOI10.3233/FI-2015-1183MaRDI QIDQ2805430zbMATH OpenOpenAlexFDO

Authors Jouni Järvinen, Sándor Radeleczki

Publication date 11 May 2016

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5184

zbMATH Keywords

cliques of graphsHelly numbersirredundant coveringsquasiordered setstolerance relations

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Partial orders, general (06A06) Complemented lattices, orthocomplemented lattices and posets (06C15) Subalgebras, congruence relations (08A30)

Abstract: In this paper, we consider tolerances induced by irredundant coverings. Each tolerance $R$ on $U$ determines a quasiorder $lesssi{m}_R$ by setting $xlesssi{m}_{R}y$ if and only if $R(x)subseteqR(y)$. We prove that for a tolerance $R$ induced by a covering $mathcalH$ of $U$, the covering $mathcalH$ is irredundant if and only if the quasiordered set $(U,lesssi{m}_R)$ is bounded by minimal elements and the tolerance $R$ coincides with the product $gtrsi{m}_{R}circlesssi{m}_R$. We also show that in such a case $$m$isminimalin$(U,lesssim_R)$$, and for each minimal $m$, we have $R(m)=uparrowm$. Additionally, this irredundant covering $mathcalH$ inducing $R$ consists of some blocks of the tolerance $R$. We give necessary and sufficient conditions under which $mathcalH$ and the set of $R$-blocks coincide. These results are established by applying the notion of Helly numbers of quasiordered sets.

Review text

The authors study connctions between tolerance relations and quasiorders on a given set. Having a tolerance relation \(R\), a quasiorder \(\leq\) can be defined by \(x\leq y\) if \(R(x)\subset R(y)\). Conversely, having a quasiorder \(\leq\), a tolerance relation \(R\) can be induced as \(R=\geq\circ\leq\).NEWLINENEWLINE These assignments are investigated in the paper. Hence, an irredundant covering induced by a tolerance relation can be characterized by means of minimal elements with respect to the induced quasiorder. The irredundant covering \(\mathcal H\) induced by \(R\) consists of some blocks of \(R\). It is given a necessary and sufficient condition under which \(\mathcal H\) and the set of all blocks of \(R\) coincide. A quasiordered set \(U\) has \textit{Helly number} \(k\) if for any subset \(A\) of \(U\), if any \(k\) elements of \(A\) have a common lower bound then the whole of \(A\) has a common lower bound. It is shown that if a qusiorder is induced by a tolerance relation then its Helly number is equal to 2.

Recommendations

• On the coverings by tolerance classes
• Relations, coverings, hypergraphs and matroids
• Quasiorders, tolerance relations and corresponding ``partitions
• Irredundant coverings, tolerances, and related algebras
• scientific article; zbMATH DE number 3957192

Cited in

(9)

• On the coverings by tolerance classes
• On minimal absorbent sets for some types of tolerance relations
• Three lessons on the topological and algebraic hidden core of rough set theory
• Irredundant coverings, tolerances, and related algebras
• Relations, coverings, hypergraphs and matroids
• scientific article; zbMATH DE number 3957192 (Why is no real title available?)
• REPRESENTING REGULAR PSEUDOCOMPLEMENTED KLEENE ALGEBRAS BY TOLERANCE-BASED ROUGH SETS
• Quasiorders, tolerance relations and corresponding ``partitions
• Examples of clique closure systems

This page was built for publication: Tolerances induced by irredundant coverings.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805430)