Geodesic
Cycle-free cuts of mutual rank probability relations
Kybernetika, Tome 50 (2014) no. 5, pp. 814-837 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

It is well known that the linear extension majority (LEM) relation of a poset of size $n≥9$ can contain cycles. In this paper we are interested in obtaining minimum cutting levels $\alpha_m$ such that the crisp relation obtained from the mutual rank probability relation by setting to $0$ its elements smaller than or equal to $\alpha_m$, and to $1$ its other elements, is free from cycles of length $m$. In a first part, theoretical upper bounds for $\alpha_m$ are derived using known transitivity properties of the mutual rank probability relation. Next, we experimentally obtain minimum cutting levels for posets of size $n≤13$. We study the posets requiring these cutting levels in order to have a cycle-free strict cut of their mutual rank probability relation. Finally, a lower bound for the minimum cutting level $\alpha_4$ is computed. To accomplish this, a family of posets is used that is inspired by the experimentally obtained $12$-element poset requiring the highest cutting level to avoid cycles of length $4$.
It is well known that the linear extension majority (LEM) relation of a poset of size $n≥9$ can contain cycles. In this paper we are interested in obtaining minimum cutting levels $\alpha_m$ such that the crisp relation obtained from the mutual rank probability relation by setting to $0$ its elements smaller than or equal to $\alpha_m$, and to $1$ its other elements, is free from cycles of length $m$. In a first part, theoretical upper bounds for $\alpha_m$ are derived using known transitivity properties of the mutual rank probability relation. Next, we experimentally obtain minimum cutting levels for posets of size $n≤13$. We study the posets requiring these cutting levels in order to have a cycle-free strict cut of their mutual rank probability relation. Finally, a lower bound for the minimum cutting level $\alpha_4$ is computed. To accomplish this, a family of posets is used that is inspired by the experimentally obtained $12$-element poset requiring the highest cutting level to avoid cycles of length $4$.
DOI : 10.14736/kyb-2014-5-0814
Classification : 06A06, 06A07
Keywords: partially ordered set; linear extension majority cycle; mutual rank probability relation; minimum cutting level; cycle-free cut 
@article{10_14736_kyb_2014_5_0814,
     author = {De Loof, Karel and De Baets, Bernard and De Meyer, Hans},
     title = {Cycle-free cuts of mutual rank probability relations},
     journal = {Kybernetika},
     pages = {814--837},
     year = {2014},
     volume = {50},
     number = {5},
     doi = {10.14736/kyb-2014-5-0814},
     mrnumber = {3301863},
     zbl = {06410706},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-5-0814/}
}
TY  - JOUR
AU  - De Loof, Karel
AU  - De Baets, Bernard
AU  - De Meyer, Hans
TI  - Cycle-free cuts of mutual rank probability relations
JO  - Kybernetika
PY  - 2014
SP  - 814
EP  - 837
VL  - 50
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-5-0814/
DO  - 10.14736/kyb-2014-5-0814
LA  - en
ID  - 10_14736_kyb_2014_5_0814
ER  - 
%0 Journal Article
%A De Loof, Karel
%A De Baets, Bernard
%A De Meyer, Hans
%T Cycle-free cuts of mutual rank probability relations
%J Kybernetika
%D 2014
%P 814-837
%V 50
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-5-0814/
%R 10.14736/kyb-2014-5-0814
%G en
%F 10_14736_kyb_2014_5_0814
De Loof, Karel; De Baets, Bernard; De Meyer, Hans. Cycle-free cuts of mutual rank probability relations. Kybernetika, Tome 50 (2014) no. 5, pp. 814-837. doi: 10.14736/kyb-2014-5-0814

Cité par Sources :