| Title:
|
Cycle-free cuts of mutual rank probability relations (English) |
| Author:
|
De Loof, Karel |
| Author:
|
De Baets, Bernard |
| Author:
|
De Meyer, Hans |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
50 |
| Issue:
|
5 |
| Year:
|
2014 |
| Pages:
|
814-837 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
partially ordered set |
| Keyword:
|
linear extension majority cycle |
| Keyword:
|
mutual rank probability relation |
| Keyword:
|
minimum cutting level |
| Keyword:
|
cycle-free cut |
| MSC:
|
06A06 |
| MSC:
|
06A07 |
| idZBL:
|
Zbl 06410706 |
| idMR:
|
MR3301863 |
| DOI:
|
10.14736/kyb-2014-5-0814 |
| . |
| Date available:
|
2015-01-13T09:41:46Z |
| Last updated:
|
2016-01-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144109 |
| . |
| Reference:
|
[1] Aigner, M.: Combinatorial Search..Wiley-Teubner, Chichester 1988. Zbl 0663.68076, MR 0973401 |
| Reference:
|
[2] Brightwell, G., Fishburn, P., Winkler, P.: Interval orders and linear extension cycles..Ars Combin. 36 (1993), 283-288. Zbl 0798.06002, MR 1246924 |
| Reference:
|
[3] Brinkmann, G., McKay, B.: Posets on up to 16 points..Order 19 (2002), 147-179. Zbl 1006.06003, MR 1922916, 10.1023/A:1016543307592 |
| Reference:
|
[4] Comtet, L.: Advanced Combinatorics..D. Reidel Publishing Company, Boston 1974. Zbl 0283.05001, MR 0460128 |
| Reference:
|
[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, MR 2673612 |
| Reference:
|
[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 10.2174/138620708786306032 |
| Reference:
|
[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. MR 2591944, 10.1016/j.camwa.2009.12.021 |
| Reference:
|
[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, MR 2245338 |
| Reference:
|
[9] Ewacha, K., Fishburn, P., Gehrlein, W.: Linear extension majority cycles in height-1 orders..Order 6 (1990), 313-318. Zbl 0708.06002, MR 1063814, 10.1007/BF00346127 |
| Reference:
|
[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, MR 0366761, 10.1016/0095-8956(74)90030-6 |
| Reference:
|
[11] Fishburn, P.: On linear extension majority graphs of partial orders..J. Combin. Theory Ser.B 21 (1976), 65-70. Zbl 0294.06001, MR 0469811, 10.1016/0095-8956(76)90028-9 |
| Reference:
|
[12] Fishburn, P.: Proportional transitivity in linear extensions of ordered sets..J. Combin. Theory Ser.B 41 (1986), 48-60. Zbl 0566.06002, MR 0854603, 10.1016/0095-8956(86)90027-4 |
| Reference:
|
[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, MR 0406580, 10.1080/0022250X.1975.9989846 |
| Reference:
|
[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, MR 0885494, 10.1016/0012-365X(87)90005-7 |
| Reference:
|
[15] Gehrlein, W.: Frequency estimates for linear extension majority cycles on partial orders..RAIRO Oper. Res. 25 (1991), 359-364. Zbl 0755.06001 |
| Reference:
|
[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, MR 2023982, 10.1016/S0165-4896(03)00080-5 |
| Reference:
|
[17] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for partial orders..Ann. Oper. Res. 23 (1990), 311-322. MR 1066341, 10.1007/BF02204855 |
| Reference:
|
[18] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for small ($n≤9$) partial orders..Computers Math. Appl. 20 (1990), 41-44. MR 1062303, 10.1016/0898-1221(90)90239-G |
| Reference:
|
[19] Kahn, J., Yu, Y.: Log-concave functions and poset probabilities..Combinatorica 18 (1998), 85-99. MR 1645654, 10.1007/PL00009812 |
| Reference:
|
[20] Kislitsyn, S.: Finite partially ordered sets and their associated sets of permutations..Mat. Zametki 4 (1968), 511-518. MR 0244113 |
| Reference:
|
[21] Pruesse, G., Ruskey, F.: Generating linear extensions fast..SIAM J. Comput. 23 (1994), 373-386. Zbl 0804.68055, MR 1267216, 10.1137/S0097539791202647 |
| Reference:
|
[22] Varol, Y., Rotem, D.: An algorithm to generate all topological sorting arrangements..Computer J. 24 (1981), 83-84. Zbl 0454.68057, 10.1093/comjnl/24.1.83 |
| Reference:
|
[23] Yu, Y.: On proportional transitivity of ordered sets..Order 15 (1998), 87-95. Zbl 0912.06005, MR 1652877, 10.1023/A:1006086010382 |
| . |
