Kybernetika 50 no. 5, 814-837, 2014

Cycle-free cuts of mutual rank probability relations

Karel De Loof, Bernard De Baets and Hans De MeyerDOI: 10.14736/kyb-2014-5-0814

Abstract:

It is well known that the linear extension majority (LEM) relation of a poset of size $n\geq 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\leq 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:

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

Classification:

06A06, 06A07

References:

  1. M. Aigner: Combinatorial Search. Wiley-Teubner, Chichester 1988.   CrossRef
  2. G. Brightwell, P. Fishburn and P. Winkler: Interval orders and linear extension cycles. Ars Combin. 36 (1993), 283-288.   CrossRef
  3. G. Brinkmann and B. McKay: Posets on up to 16 points. Order 19 (2002), 147-179.   CrossRef
  4. L. Comtet: Advanced Combinatorics. D. Reidel Publishing Company, Boston 1974.   CrossRef
  5. B. De Baets, H. De Meyer and K. De Loof: On the cycle-transitivity of the mutual rank probability relation of a poset. Fuzzy Sets and Systems 161 (2010), 2695-2708.   CrossRef
  6. K. De Loof, B. De Baets and H. De Meyer: A hitchhiker's guide to poset ranking. Comb. Chemistry and High Throughput Screening 11 (2008), 734-744   CrossRef
  7. K. De Loof, B. De Baets and H. De Meyer: Counting linear extension majority cycles in posets on up to 13 points. Computers Math. Appl. 59 (2010), 1541-1547.   CrossRef
  8. K. De Loof, H. De Meyer and B. De Baets: Exploiting the lattice of ideals representation of a poset. Fundam. Inform. 71 (2006), 309-321.   CrossRef
  9. K. Ewacha, P. Fishburn and W. Gehrlein: Linear extension majority cycles in height-1 orders. Order 6 (1990), 313-318.   CrossRef
  10. P. Fishburn: On the family of linear extensions of a partial order. J. Combin. Theory Ser.B 17 (1974), 240-243.   CrossRef
  11. P. Fishburn: On linear extension majority graphs of partial orders. J. Combin. Theory Ser.B 21 (1976), 65-70.   CrossRef
  12. P. Fishburn: Proportional transitivity in linear extensions of ordered sets. J. Combin. Theory Ser.B 41 (1986), 48-60.   CrossRef
  13. P. Fishburn and W. Gehrlein: A comparative analysis of methods for constructing weak orders from partial orders. J. Math. Sociol. 4 (1975), 93-102.   CrossRef
  14. B. Ganter, G. Hafner and W. Poguntke: On linear extensions of ordered sets with a symmetry. Discrete Math. 63 (1987), 153-156.   CrossRef
  15. W. Gehrlein: Frequency estimates for linear extension majority cycles on partial orders. RAIRO Oper. Res. 25 (1991), 359-364.   CrossRef
  16. W. Gehrlein: The effectiveness of weighted scoring rules when pairwise majority rule cycles exist. Math. Soc. Sci. 47 (2004), 69-85.   CrossRef
  17. W. Gehrlein and P. Fishburn: Linear extension majority cycles for partial orders. Ann. Oper. Res. 23 (1990), 311-322.   CrossRef
  18. W. Gehrlein and P. Fishburn: Linear extension majority cycles for small ($n≤9$) partial orders. Computers Math. Appl. 20 (1990), 41-44.   CrossRef
  19. J. Kahn and Y. Yu: Log-concave functions and poset probabilities. Combinatorica 18 (1998), 85-99.   CrossRef
  20. S. Kislitsyn: Finite partially ordered sets and their associated sets of permutations. Mat. Zametki 4 (1968), 511-518.   CrossRef
  21. G. Pruesse and F. Ruskey: Generating linear extensions fast. SIAM J. Comput. 23 (1994), 373-386.   CrossRef
  22. Y. Varol and D. Rotem: An algorithm to generate all topological sorting arrangements. Computer J. 24 (1981), 83-84.   CrossRef
  23. Y. Yu: On proportional transitivity of ordered sets. Order 15 (1998), 87-95.   CrossRef