Counting linear extension majority cycles in partially ordered sets on up to 13 elements. (English) Zbl 1189.06001
Summary: It is well known that the linear extension majority relation of a partially ordered set \((P,\leq P)\) can contain cycles when at least 9 elements are present in \(P\). Computer experiments have uncovered all posets with 9 elements containing such cycles and limited frequency estimates for linear extension majority cycles (or LEM cycles) in posets on up to 12 elements are available. In this contribution, we present an efficient approach which allows us to count and store all posets containing LEM cycles on up to 13 elements.
MSC:
| 06A07 | Combinatorics of partially ordered sets |
Keywords:
partially ordered set; linear extension; linear extension majority cycle; mutual rank probabilityReferences:
| [1] | Davey, B.; Priestley, H., Introduction to Lattices and Order (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1002.06001 |
| [2] | De Loof, K.; De Baets, B.; De Meyer, H., On the random generation and counting of weak order extensions of a poset with given class cardinalities, Information Sciences, 177, 220-230 (2007) · Zbl 1111.06001 |
| [3] | Kislitsyn, S., Finite partially ordered sets and their associated sets of permutations, Matematicheskiye Zametki, 4, 511-518 (1968) |
| [4] | Fishburn, P., On the family of linear extensions of a partial order, Journal of Combinatorial Theory, Series B, 17, 240-243 (1974) · Zbl 0274.06003 |
| [5] | Aigner, M., Combinatorial Search (1988), Wiley-Teubner: Wiley-Teubner Chichester · Zbl 0663.68076 |
| [6] | Fishburn, P., On linear extension majority graphs of partial orders, Journal of Combinatorial Theory, Series B, 21, 65-70 (1976) · Zbl 0294.06001 |
| [7] | Fishburn, P., Proportional transitivity in linear extensions of ordered sets, Journal of Combinatorial Theory, Series B, 41, 48-60 (1986) · Zbl 0566.06002 |
| [8] | Fishburn, P.; Gehrlein, W., A comparative analysis of methods for constructing weak orders from partial orders, Journal of Mathematical Sociology, 4, 93-102 (1975) · Zbl 0324.68071 |
| [9] | Ganter, B.; Hafner, G.; Poguntke, W., On linear extensions of ordered sets with a symmetry, Discrete Mathematics, 63, 153-156 (1987) · Zbl 0607.06001 |
| [10] | Gehrlein, W., The effectiveness of weighted scoring rules when pairwise majority rule cycles exist, Mathematical Social Sciences, 47, 69-85 (2004) · Zbl 1069.91024 |
| [11] | Gehrlein, W.; Fishburn, P., Linear extension majority cycles for small \((n \leq 9)\) partial orders, Computers & Mathematics with Applications, 20, 41-44 (1990) · Zbl 0708.06003 |
| [12] | Gehrlein, W., Frequency estimates for linear extension majority cycles on partial orders, RAIRO-Operations Research, 25, 359-364 (1991) · Zbl 0755.06001 |
| [13] | Gehrlein, W.; Fishburn, P., Linear extension majority cycles for partial orders, Annals of Operations Research, 23, 311-322 (1990) · Zbl 0715.90008 |
| [14] | Brightwell, G.; Fishburn, P.; Winkler, P., Interval orders and linear extension cycles, Ars Combinatoria, 36, 283-288 (1993) · Zbl 0798.06002 |
| [15] | Ewacha, K.; Fishburn, P.; Gehrlein, W., Linear extension majority cycles in height-1 orders, Order, 6, 313-318 (1990) · Zbl 0708.06002 |
| [16] | B. De Baets, H. De Meyer, K. De Loof, On the cycle-transitivity of the mutual rank probability relation of a poset, Fuzzy Sets and Systems (submitted); B. De Baets, H. De Meyer, K. De Loof, On the cycle-transitivity of the mutual rank probability relation of a poset, Fuzzy Sets and Systems (submitted) · Zbl 1256.06001 |
| [17] | Kahn, J.; Yu, Y., Log-concave functions and poset probabilities, Combinatorica, 18, 85-99 (1998) · Zbl 0928.52006 |
| [18] | Yu, Y., On proportional transitivity of ordered sets, Order, 15, 87-95 (1998) · Zbl 0912.06005 |
| [19] | Brüggemann, R.; Simon, U.; Mey, S., Estimation of averaged ranks by extended local partial order models, MATCH Communications in Mathematical and in Computer Chemistry, 54, 489-518 (2005) · Zbl 1082.92503 |
| [20] | Brüggemann, R.; Voigt, K., Basic principles of hasse diagram technique in chemistry, Combinatorial Chemistry & High Throughput Screening, 11, 756-769 (2008) |
| [21] | Carlsen, L.; Lerche, D.; Sørensen, P., Improving the predicting power of partial order based qsars through linear extensions, Journal of Chemical Information and Computer Sciences, 42, 806-811 (2002) |
| [22] | De Loof, K.; De Baets, B.; De Meyer, H., A hitchhiker’s guide to poset ranking, Combinatorial Chemistry & High Throughput Screening, 11, 734-744 (2008) |
| [23] | De Loof, K.; De Meyer, H.; De Baets, B., Graded stochastic dominance as a tool for ranking the elements of a poset, (Lawry, J.; Miranda, E.; Bugarin, A.; Li, S.; Gil, M.; Grzegorzewski, P.; Hyrniewicz, O., Soft Methods for Integrated Uncertainty Modelling. Soft Methods for Integrated Uncertainty Modelling, Advances in Soft Computing (2006), Springer-Verlag: Springer-Verlag Berlin), 53-60 · Zbl 1106.60026 |
| [24] | Lerche, D.; Sørensen, P., Evaluation of the ranking probabilities for partial orders based on random linear extensions, Chemosphere, 53, 981-992 (2003) |
| [25] | Lerche, D.; Sørensen, P.; Brüggemann, R., Improved estimation of the ranking probabilities in partial orders using random linear extensions by approximation of the mutual ranking probability, Journal of Chemical Information and Computer Science, 43, 1471-1480 (2003) |
| [26] | Patil, G.; Taillie, C., Multiple indicators, partially ordered sets, and linear extensions: Multi-criterion ranking and prioritization, Environmental and Ecological Statistics, 11, 199-228 (2004) |
| [27] | De Loof, K.; De Meyer, H.; De Baets, B., Exploiting the lattice of ideals representation of a poset, Fundamenta Informaticae, 71, 309-321 (2006) · Zbl 1110.06001 |
| [28] | Brinkmann, G.; McKay, B., Posets on up to 16 points, Order, 19, 147-179 (2002) · Zbl 1006.06003 |
| [29] | Habib, M.; Medina, R.; Nourine, L.; Steiner, G., Efficient algorithms on distributive lattices, Discrete Applied Mathematics, 110, 169-187 (2001) · Zbl 0983.06009 |
| [30] | Varol, Y.; Rotem, D., An algorithm to generate all topological sorting arrangements, The Computer Journal, 24, 83-84 (1981) · Zbl 0454.68057 |
| [31] | Brightwell, G.; Felsner, S.; Trotter, W., Balancing pairs and the cross product conjecture, Order, 12, 327-349 (1995) · Zbl 0839.06002 |
| [32] | Brightwell, G., Balanced pairs in partial orders, Discrete Mathematics, 201, 25-52 (1999) · Zbl 0940.06002 |
| [33] | M. Peczarski, Computer assisted research of posets, Ph.D. Thesis, University of Warsaw, 2006; M. Peczarski, Computer assisted research of posets, Ph.D. Thesis, University of Warsaw, 2006 · Zbl 1184.68624 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
