Geodesic
Cycle-free cuts of mutual rank probability relations
Kybernetika, Tome 50 (2014) no. 5, pp. 814-837
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.14736/kyb-2014-5-0814
Classification : 06A06, 06A07
Keywords: partially ordered set; linear extension majority cycle; mutual rank probability relation; minimum cutting level; cycle-free cut 
@article{10_14736_kyb_2014_5_0814,
     author = {De Loof, Karel and De Baets, Bernard and De Meyer, Hans},
     title = {Cycle-free cuts of mutual rank probability relations},
     journal = {Kybernetika},
     pages = {814--837},
     year = {2014},
     volume = {50},
     number = {5},
     doi = {10.14736/kyb-2014-5-0814},
     mrnumber = {3301863},
     zbl = {06410706},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-5-0814/}
}
TY  - JOUR
AU  - De Loof, Karel
AU  - De Baets, Bernard
AU  - De Meyer, Hans
TI  - Cycle-free cuts of mutual rank probability relations
JO  - Kybernetika
PY  - 2014
SP  - 814
EP  - 837
VL  - 50
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-5-0814/
DO  - 10.14736/kyb-2014-5-0814
LA  - en
ID  - 10_14736_kyb_2014_5_0814
ER  - 
%0 Journal Article
%A De Loof, Karel
%A De Baets, Bernard
%A De Meyer, Hans
%T Cycle-free cuts of mutual rank probability relations
%J Kybernetika
%D 2014
%P 814-837
%V 50
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-5-0814/
%R 10.14736/kyb-2014-5-0814
%G en
%F 10_14736_kyb_2014_5_0814
De Loof, Karel; De Baets, Bernard; De Meyer, Hans. Cycle-free cuts of mutual rank probability relations. Kybernetika, Tome 50 (2014) no. 5, pp. 814-837. doi: 10.14736/kyb-2014-5-0814

[1] Aigner, M.: Combinatorial Search. Wiley-Teubner, Chichester 1988. | MR | Zbl

[2] Brightwell, G., Fishburn, P., Winkler, P.: Interval orders and linear extension cycles. Ars Combin. 36 (1993), 283-288. | MR | Zbl

[3] Brinkmann, G., McKay, B.: Posets on up to 16 points. Order 19 (2002), 147-179. | DOI | MR | Zbl

[4] Comtet, L.: Advanced Combinatorics. D. Reidel Publishing Company, Boston 1974. | MR | Zbl

[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 | Zbl

[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

[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 | MR

[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 | Zbl

[9] Ewacha, K., Fishburn, P., Gehrlein, W.: Linear extension majority cycles in height-1 orders. Order 6 (1990), 313-318. | DOI | MR | Zbl

[10] Fishburn, P.: On the family of linear extensions of a partial order. J. Combin. Theory Ser.B 17 (1974), 240-243. | DOI | MR | Zbl

[11] Fishburn, P.: On linear extension majority graphs of partial orders. J. Combin. Theory Ser.B 21 (1976), 65-70. | DOI | MR | Zbl

[12] Fishburn, P.: Proportional transitivity in linear extensions of ordered sets. J. Combin. Theory Ser.B 41 (1986), 48-60. | DOI | MR | Zbl

[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 | MR | Zbl

[14] Ganter, B., Hafner, G., Poguntke, W.: On linear extensions of ordered sets with a symmetry. Discrete Math. 63 (1987), 153-156. | DOI | MR | Zbl

[15] Gehrlein, W.: Frequency estimates for linear extension majority cycles on partial orders. RAIRO Oper. Res. 25 (1991), 359-364. | Zbl

[16] Gehrlein, W.: The effectiveness of weighted scoring rules when pairwise majority rule cycles exist. Math. Soc. Sci. 47 (2004), 69-85. | DOI | MR | Zbl

[17] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for partial orders. Ann. Oper. Res. 23 (1990), 311-322. | DOI | MR

[18] Gehrlein, W., Fishburn, P.: Linear extension majority cycles for small ($n≤9$) partial orders. Computers Math. Appl. 20 (1990), 41-44. | DOI | MR

[19] Kahn, J., Yu, Y.: Log-concave functions and poset probabilities. Combinatorica 18 (1998), 85-99. | DOI | MR

[20] Kislitsyn, S.: Finite partially ordered sets and their associated sets of permutations. Mat. Zametki 4 (1968), 511-518. | MR

[21] Pruesse, G., Ruskey, F.: Generating linear extensions fast. SIAM J. Comput. 23 (1994), 373-386. | DOI | MR | Zbl

[22] Varol, Y., Rotem, D.: An algorithm to generate all topological sorting arrangements. Computer J. 24 (1981), 83-84. | DOI | Zbl

[23] Yu, Y.: On proportional transitivity of ordered sets. Order 15 (1998), 87-95. | DOI | MR | Zbl

Cité par Sources :