Cycle-free cuts of mutual rank probability relations

De Loof, Karel ; De Baets, Bernard ; De Meyer, Hans

Kybernetika, Tome 50 (2014) no. 5, pp. 814-837.

Résumé

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$.

Détail

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