Bottom-Up: a New Algorithm to Generate Random Linear Extensions of a Poset
| dc.contributor.author | García Segador, Pedro | |
| dc.contributor.author | Miranda Menéndez, Pedro | |
| dc.date.accessioned | 2023-06-17T13:21:20Z | |
| dc.date.available | 2023-06-17T13:21:20Z | |
| dc.date.issued | 2018-10-09 | |
| dc.description.abstract | In this paper we present a new method for deriving a random linear extension of a poset. This new strategy combines Probability with Combinatorics and obtains a procedure where each minimal element of a sequence of subposets is selected via a probability distribution. The method consists in obtaining a weight vector on the elements of P, so that an element is selected with a probability proportional to its weight. From some properties on the graph of adjacent linear extensions, it is shown that the probability distribution can be obtained by solving a linear system. The number of equations involved in this system relies on the number of what we have called positioned antichains, that allows a reduced number of equations. Finally, we give some examples of the applicability of the algorithm. This procedure cannot be applied to every poset, but it is exact when it can be used. Moreover, the method is quick and easy to implement. Besides, it allows a simple way to derive the number of linear extensions of a given poset. | |
| dc.description.department | Depto. de Estadística e Investigación Operativa | |
| dc.description.faculty | Fac. de Ciencias Matemáticas | |
| dc.description.refereed | TRUE | |
| dc.description.sponsorship | Ministerio de Economía y Competitividad (MINECO) | |
| dc.description.status | pub | |
| dc.eprint.id | https://eprints.ucm.es/id/eprint/54907 | |
| dc.identifier.citation | García-Segador P, Miranda P. Bottom-Up: a New Algorithm to Generate Random Linear Extensions of a Poset. Order 2019; 36: 437–462. [DOI: 10.1007/s11083-018-9476-1] | |
| dc.identifier.doi | 10.1007/s11083-018-9476-1 | |
| dc.identifier.issn | 0167-8094 | |
| dc.identifier.officialurl | https://doi.org/10.1007/s11083-018-9476-1 | |
| dc.identifier.relatedurl | https://link.springer.com/journal/11083 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.14352/13212 | |
| dc.journal.title | Order | |
| dc.language.iso | eng | |
| dc.page.final | 26 | |
| dc.page.initial | 1 | |
| dc.publisher | Springer Netherlands | |
| dc.relation.projectID | MTM-2015-67057 | |
| dc.rights.accessRights | open access | |
| dc.rights.uri | https://creativecommons.org/licenses/by/3.0/es/ | |
| dc.subject.cdu | 517.98 | |
| dc.subject.keyword | Poset | |
| dc.subject.keyword | Linear extension | |
| dc.subject.keyword | Random generation | |
| dc.subject.keyword | Probability | |
| dc.subject.ucm | Análisis funcional y teoría de operadores | |
| dc.subject.ucm | Probabilidades (Matemáticas) | |
| dc.title | Bottom-Up: a New Algorithm to Generate Random Linear Extensions of a Poset | |
| dc.type | journal article | |
| dcterms.references | 1. Ayyer, A., Klee, S., Shilling, A.: Combinatorial Markov chains on linear extensions. J. Algebr. Comb. 39(4), 853–881 (2014) MathSciNetCrossRefGoogle Scholar 2. Bollobás, B., Brightwell, G., Sidorenko, A.: Geometrical techniques for estimating numbers of linear extensions. Eur. J. Comb. 20, 329–335 (1999) MathSciNetCrossRefGoogle Scholar 3. Brightwell, G: The number of linear extensions of ranked posets. CDAM Research Report (2003) Google Scholar 4. Brightwell, G., Tetali, P.: The number of linear extensions of the Boolean Lattice. Order 20(3), 333–345 (2003) MathSciNetCrossRefGoogle Scholar 5. Brightwell, G., Winkler, P.: Counting linear extensions. Order 8(3), 225–242 (1991) MathSciNetCrossRefGoogle Scholar 6. Bubley, R., Dyer, M.: Faster random generation of linear extensions. Discret. Math. 20, 81–88 (1999) MathSciNetCrossRefGoogle Scholar 7. Choquet, G: Theory of capacities. Ann. Inst. Fourier 5, 131–295 (1953) MathSciNetCrossRefGoogle Scholar 8. Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (2002) CrossRefGoogle Scholar 9. Denneberg, D.: Non-additive Measures and Integral. Kluwer Academic, Dordrecht (1994) CrossRefGoogle Scholar 10. Devroye, L.: Non-uniform Random Variate Generation. Springer, New York (1986) CrossRefGoogle Scholar 11. Edelman, P., Hibi, T., Stanley, R.: A recurrence for linear extensions. Order 6(1), 15–18 (1989) MathSciNetCrossRefGoogle Scholar 12. Eriksson, K., Jonsson, M., Sjöstrand, J.: Markov chains on graded posets: compatibility of up-directed and down-directed transition probabilities. Order, Online Open Access. https://doi.org/10.1007/s11083-016-9420-1 (2016) CrossRefGoogle Scholar 13. Greene, C., Nijenhuis, A., Wilf, H.: A probabilistic proof of a formula for the number of Young Tableaux of a given shape. Adv. Math. 31, 104–109 (1979) MathSciNetCrossRefGoogle Scholar 14. Grabisch, M., Murofushi, T., Sugeno, M. (eds.): Fuzzy Measures and Integrals- Theory and Applications. Number 40 in Studies in Fuzziness and Soft Computing. Physica–Verlag, Heidelberg (2000) Google Scholar 15. Huber, M.: Fast perfect sampling from linear extensions. Discret. Math. 306, 420–428 (2006) MathSciNetCrossRefGoogle Scholar 16. Huber, M.: Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction. Chic. J. Theor. Comput. Sci. 03, 1–16 (2014) MathSciNetzbMATHGoogle Scholar 17. Kalvin, A.D., Varol, Y.L.: On the generation of all topological sortings. J. Algorithms 4(2), 150–162 (1983) MathSciNetCrossRefGoogle Scholar 18. Karzanov, A., Khachiyan, L.: On the conductance of order Markov chains. Order 8(1), 7–15 (1995) MathSciNetCrossRefGoogle Scholar 19. Knuth, D.E., Szwarcfiter, J.: A structured program to generate all topological sorting arrangements. Inform. Process. Lett. 2(6), 153–157 (1974) CrossRefGoogle Scholar 20. Korsh, J.F., Lafollette, P.S.: Loopless generation of linear extensions of a poset. Order 19, 115–126 (2002) MathSciNetCrossRefGoogle Scholar 21. Levin, D., Peres, Y., Wilmer, E.: Markov Mixing and Mixing Times. American Mathematical Society (2008) Google Scholar 22. Leydold, J., Hörmann, W.: A sweep-plane algorithm for generating random tuples in simple polytopes. J. Math. Comput. 67(224), 1617–1635 (1998) MathSciNetCrossRefGoogle Scholar 23. Matousek, J: Lectures on Discrete Geometry. Springer, New York (2002) CrossRefGoogle Scholar 24. Nakada, K., Okamura, S.: An algorithm which generates linear extensions for a generalized Young diagram with uniform probability. DMTCS, proc. AN, pp. 801–808 (2010) Google Scholar 25. Neggers, J., Kim, H. S.: Basic Posets. World Scientific, Singapore (1998) CrossRefGoogle Scholar 26. Pruesse, G., Ruskey, F.: Generating linear extensions fast. SIAM J. Comput. 23(2), 373–386 (1994) MathSciNetCrossRefGoogle Scholar 27. Ruskey, F.: Generating linear extensions of posets by transpositions. J. Comb. Theory, Ser. B 54, 77–101 (1992) MathSciNetCrossRefGoogle Scholar 28. Stanley, R.: Two poset polytopes. Discrete Comput. Geom. 1(1), 9–23 (1986) MathSciNetCrossRefGoogle Scholar 29. Stanley, R.: Enumerative Combinatorics. Cambridge University Press, Cambridge (2012) zbMATHGoogle Scholar 30. Sugeno, M.: Theory of fuzzy integrals and its applications. PhD thesis, Tokyo Institute of Technology (1974) Google Scholar 31. Varol, Y.L., Rotem, D.: An algorithm to generate all topological sorting arrangements. Comput. J. 24(1), 83–84 (1981) CrossRefGoogle Scholar 32. Vose, M.D.: A linear algorithm for generating random numbers with a given distribution. IEEE Trans. Softw. Eng. 17(9), 972–975 (1991) MathSciNetCrossRefGoogle Scholar 33. Wilf, H.S.: Generating Functionology. Academic, New York (1994) Google Scholar | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | 5416c727-ae1e-4a30-9118-a87352c1a7be | |
| relation.isAuthorOfPublication | d940fcaa-13c3-4bad-8198-1025a668ed71 | |
| relation.isAuthorOfPublication.latestForDiscovery | d940fcaa-13c3-4bad-8198-1025a668ed71 |
