Cycle-free cuts of mutual rank probability relations

De Loof, Karel, De Baets, Bernard, and De Meyer, Hans. "Cycle-free cuts of mutual rank probability relations." Kybernetika 50.5 (2014): 814-837. <http://eudml.org/doc/262209>.

@article{DeLoof2014,
abstract = {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$.},
author = {De Loof, Karel, De Baets, Bernard, De Meyer, Hans},
journal = {Kybernetika},
keywords = {partially ordered set; linear extension majority cycle; mutual rank probability relation; minimum cutting level; cycle-free cut; partially ordered sets; linear extension majority cycles; mutual rank probability relations; minimum cutting levels; cycle-free cuts},
language = {eng},
number = {5},
pages = {814-837},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Cycle-free cuts of mutual rank probability relations},
url = {http://eudml.org/doc/262209},
volume = {50},
year = {2014},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 50
IS - 5
SP - 814
EP - 837
AB - 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$.
LA - eng
KW - partially ordered set; linear extension majority cycle; mutual rank probability relation; minimum cutting level; cycle-free cut; partially ordered sets; linear extension majority cycles; mutual rank probability relations; minimum cutting levels; cycle-free cuts
UR - http://eudml.org/doc/262209
ER -