Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
partially ordered set; linear extension majority cycle; mutual rank probability relation; minimum cutting level; cycle-free cut
partially ordered set; linear extension majority cycle; mutual rank probability relation; minimum cutting level; cycle-free cut
Summary:
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$.
References:
[1] Aigner, M.: Combinatorial Search. Wiley-Teubner, Chichester 1988. MR 0973401 | Zbl 0663.68076
[2] Brightwell, G., Fishburn, P., Winkler, P.: Interval orders and linear extension cycles. Ars Combin. 36 (1993), 283-288. MR 1246924 | Zbl 0798.06002
[3] Brinkmann, G., McKay, B.: Posets on up to 16 points. Order 19 (2002), 147-179. DOI 10.1023/A:1016543307592 | MR 1922916 | Zbl 1006.06003
[4] Comtet, L.: Advanced Combinatorics. D. Reidel Publishing Company, Boston 1974. MR 0460128 | 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. MR 2673612 | Zbl 1256.06001
[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. DOI 10.1016/j.camwa.2009.12.021 | MR 2591944
[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. MR 2245338 | Zbl 1110.06001
[9] Ewacha, K., Fishburn, P., Gehrlein, W.: Linear extension majority cycles in height-1 orders. Order 6 (1990), 313-318. DOI 10.1007/BF00346127 | MR 1063814 | Zbl 0708.06002
[10] Fishburn, P.: On the family of linear extensions of a partial order. J. Combin. Theory Ser.B 17 (1974), 240-243. DOI 10.1016/0095-8956(74)90030-6 | MR 0366761 | Zbl 0274.06003
[11] Fishburn, P.: On linear extension majority graphs of partial orders. J. Combin. Theory Ser.B 21 (1976), 65-70. DOI 10.1016/0095-8956(76)90028-9 | MR 0469811 | Zbl 0294.06001
[12] Fishburn, P.: Proportional transitivity in linear extensions of ordered sets. J. Combin. Theory Ser.B 41 (1986), 48-60. DOI 10.1016/0095-8956(86)90027-4 | MR 0854603 | Zbl 0566.06002
[13] Fishburn, P., Gehrlein, W.: A comparative analysis of methods for constructing weak orders from partial orders. J. Math. Sociol. 4 (1975), 93-102. DOI 10.1080/0022250X.1975.9989846 | MR 0406580 | Zbl 0324.68071
[14] Ganter, B., Hafner, G., Poguntke, W.: On linear extensions of ordered sets with a symmetry. Discrete Math. 63 (1987), 153-156. DOI 10.1016/0012-365X(87)90005-7 | MR 0885494 | Zbl 0607.06001
[15] Gehrlein, W.: Frequency estimates for linear extension majority cycles on partial orders. RAIRO Oper. Res. 25 (1991), 359-364. Zbl 0755.06001
[16] Gehrlein, W.: The effectiveness of weighted scoring rules when pairwise majority rule cycles exist. Math. Soc. Sci. 47 (2004), 69-85. DOI 10.1016/S0165-4896(03)00080-5 | MR 2023982 | Zbl 1069.91024
[17] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for partial orders. Ann. Oper. Res. 23 (1990), 311-322. DOI 10.1007/BF02204855 | MR 1066341
[18] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for small ($n≤9$) partial orders. Computers Math. Appl. 20 (1990), 41-44. DOI 10.1016/0898-1221(90)90239-G | MR 1062303
[19] Kahn, J., Yu, Y.: Log-concave functions and poset probabilities. Combinatorica 18 (1998), 85-99. DOI 10.1007/PL00009812 | MR 1645654
[20] Kislitsyn, S.: Finite partially ordered sets and their associated sets of permutations. Mat. Zametki 4 (1968), 511-518. MR 0244113
[21] Pruesse, G., Ruskey, F.: Generating linear extensions fast. SIAM J. Comput. 23 (1994), 373-386. DOI 10.1137/S0097539791202647 | MR 1267216 | Zbl 0804.68055
[22] Varol, Y., Rotem, D.: An algorithm to generate all topological sorting arrangements. Computer J. 24 (1981), 83-84. DOI 10.1093/comjnl/24.1.83 | Zbl 0454.68057
[23] Yu, Y.: On proportional transitivity of ordered sets. Order 15 (1998), 87-95. DOI 10.1023/A:1006086010382 | MR 1652877 | Zbl 0912.06005
Search
Partner of
