Advanced search
1 file | 319.15 KB

Cycle-free cuts of mutual rank probability relations

Karel De Loof (UGent) , Bernard De Baets (UGent) and Hans De Meyer (UGent)
(2014) KYBERNETIKA. 50(5). p.814-837
Author
Organization
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 am such that the crisp relation obtained from the mutual rank probability relation by setting to 0 its elements smaller than or equal to am, and to 1 its other elements, is free from cycles of length m. In a first part, theoretical upper bounds for am 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.
Keywords
cycle-free cut, minimum cutting level, EXTENSION MAJORITY CYCLES, PARTIAL ORDERS, LINEAR EXTENSIONS, PROPORTIONAL TRANSITIVITY, SETS, POSET, linear extension majority cycle, mutual rank probability relation, partially ordered set

Downloads

  • KERMIT-A1-345.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 319.15 KB

Citation

Please use this url to cite or link to this publication:

Chicago
De Loof, Karel, Bernard De Baets, and Hans De Meyer. 2014. “Cycle-free Cuts of Mutual Rank Probability Relations.” Kybernetika 50 (5): 814–837.
APA
De Loof, K., De Baets, B., & De Meyer, H. (2014). Cycle-free cuts of mutual rank probability relations. KYBERNETIKA, 50(5), 814–837.
Vancouver
1.
De Loof K, De Baets B, De Meyer H. Cycle-free cuts of mutual rank probability relations. KYBERNETIKA. 2014;50(5):814–37.
MLA
De Loof, Karel, Bernard De Baets, and Hans De Meyer. “Cycle-free Cuts of Mutual Rank Probability Relations.” KYBERNETIKA 50.5 (2014): 814–837. Print.
@article{6846755,
  abstract     = {It is well known that the linear extension majority (LEM) relation of a poset of size n {\textrangle}= 9 can contain cycles. In this paper we are interested in obtaining minimum cutting levels am such that the crisp relation obtained from the mutual rank probability relation by setting to 0 its elements smaller than or equal to am, and to 1 its other elements, is free from cycles of length m. In a first part, theoretical upper bounds for am are derived using known transitivity properties of the mutual rank probability relation. Next, we experimentally obtain minimum cutting levels for posets of size n {\textlangle}= 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 and De Baets, Bernard and De Meyer, Hans},
  issn         = {0023-5954},
  journal      = {KYBERNETIKA},
  language     = {eng},
  number       = {5},
  pages        = {814--837},
  title        = {Cycle-free cuts of mutual rank probability relations},
  url          = {http://dx.doi.org/10.14736/kyb-2014-5-0814},
  volume       = {50},
  year         = {2014},
}

Altmetric
View in Altmetric
Web of Science
Times cited: