×

zbMATH — the first resource for mathematics

Cycle-free cuts of mutual rank probability relations. (English) Zbl 1323.06001
Summary: 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.

MSC:
06A06 Partial orders, general
06A07 Combinatorics of partially ordered sets
PDF BibTeX XML Cite
Full Text: Link
References:
[1] Aigner, M.: Combinatorial Search. Wiley-Teubner, Chichester 1988. · Zbl 0663.68076
[2] Brightwell, G., Fishburn, P., Winkler, P.: Interval orders and linear extension cycles. Ars Combin. 36 (1993), 283-288. · Zbl 0798.06002
[3] Brinkmann, G., McKay, B.: Posets on up to 16 points. Order 19 (2002), 147-179. · Zbl 1006.06003 · doi:10.1023/A:1016543307592
[4] Comtet, L.: Advanced Combinatorics. D. Reidel Publishing Company, Boston 1974. · Zbl 0283.05001
[5] Baets, B. De, Meyer, H. De, Loof, K. De: On the cycle-transitivity of the mutual rank probability relation of a poset. Fuzzy Sets and Systems 161 (2010), 2695-2708. · Zbl 1256.06001 · doi:10.1016/j.fss.2010.05.005
[6] Loof, K. De, Baets, B. De, Meyer, H. De: A hitchhiker’s guide to poset ranking. Comb. Chemistry and High Throughput Screening 11 (2008), 734-744 · doi:10.2174/138620708786306032
[7] Loof, K. De, Baets, B. De, Meyer, H. De: Counting linear extension majority cycles in posets on up to 13 points. Computers Math. Appl. 59 (2010), 1541-1547. · Zbl 1189.06001 · doi:10.1016/j.camwa.2009.12.021
[8] Loof, K. De, Meyer, H. De, Baets, B. De: Exploiting the lattice of ideals representation of a poset. Fundam. Inform. 71 (2006), 309-321. · Zbl 1110.06001
[9] Ewacha, K., Fishburn, P., Gehrlein, W.: Linear extension majority cycles in height-1 orders. Order 6 (1990), 313-318. · Zbl 0708.06002 · doi:10.1007/BF00346127
[10] Fishburn, P.: On the family of linear extensions of a partial order. J. Combin. Theory Ser.B 17 (1974), 240-243. · Zbl 0274.06003 · doi:10.1016/0095-8956(74)90030-6
[11] Fishburn, P.: On linear extension majority graphs of partial orders. J. Combin. Theory Ser.B 21 (1976), 65-70. · Zbl 0294.06001 · doi:10.1016/0095-8956(76)90028-9
[12] Fishburn, P.: Proportional transitivity in linear extensions of ordered sets. J. Combin. Theory Ser.B 41 (1986), 48-60. · Zbl 0566.06002 · doi:10.1016/0095-8956(86)90027-4
[13] Fishburn, P., Gehrlein, W.: A comparative analysis of methods for constructing weak orders from partial orders. J. Math. Sociol. 4 (1975), 93-102. · Zbl 0324.68071 · doi:10.1080/0022250X.1975.9989846
[14] Ganter, B., Hafner, G., Poguntke, W.: On linear extensions of ordered sets with a symmetry. Discrete Math. 63 (1987), 153-156. · Zbl 0607.06001 · doi:10.1016/0012-365X(87)90005-7
[15] Gehrlein, W.: Frequency estimates for linear extension majority cycles on partial orders. RAIRO Oper. Res. 25 (1991), 359-364. · Zbl 0755.06001 · eudml:105019
[16] Gehrlein, W.: The effectiveness of weighted scoring rules when pairwise majority rule cycles exist. Math. Soc. Sci. 47 (2004), 69-85. · Zbl 1069.91024 · doi:10.1016/S0165-4896(03)00080-5
[17] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for partial orders. Ann. Oper. Res. 23 (1990), 311-322. · Zbl 0715.90008 · doi:10.1007/BF02204855
[18] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for small (\(n\leq 9\)) partial orders. Computers Math. Appl. 20 (1990), 41-44. · Zbl 0708.06003 · doi:10.1016/0898-1221(90)90239-G
[19] Kahn, J., Yu, Y.: Log-concave functions and poset probabilities. Combinatorica 18 (1998), 85-99. · Zbl 0928.52006 · doi:10.1007/PL00009812
[20] Kislitsyn, S.: Finite partially ordered sets and their associated sets of permutations. Mat. Zametki 4 (1968), 511-518.
[21] Pruesse, G., Ruskey, F.: Generating linear extensions fast. SIAM J. Comput. 23 (1994), 373-386. · Zbl 0804.68055 · doi:10.1137/S0097539791202647
[22] Varol, Y., Rotem, D.: An algorithm to generate all topological sorting arrangements. Computer J. 24 (1981), 83-84. · Zbl 0454.68057 · doi:10.1093/comjnl/24.1.83
[23] Yu, Y.: On proportional transitivity of ordered sets. Order 15 (1998), 87-95. · Zbl 0912.06005 · doi:10.1023/A:1006086010382
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.