Cycle-free cuts of mutual rank probability relation

Title:

Cycle-free cuts of mutual rank probability relation

Creator:

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

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:bc7c444c-d7c5-4080-8d1a-822d93cb6aa4
uuid:bc7c444c-d7c5-4080-8d1a-822d93cb6aa4

Subject:

partially ordered set, linear extension majority cycle, mutual rank probability relation, minimum cutting level, and cycle-free cut

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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 αm such that the crisp relation obtained from the mutual rank probability relation by setting to 0 its elements smaller than or equal to αm, and to 1 its other elements, is free from cycles of length m. In a first part, theoretical upper bounds for α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 α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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

[814]-837

Source:

Kybernetika | 2014 Volume:50 | Number:5

Harvested from:

CDK

Metadata only:

false