Random preorders and alignments. (English) Zbl 1228.05028
Summary: A preorder consists of linearly ordered equivalence classes called blocks, and an alignment is a sequence of cycles. We investigate the block structure of a preorder chosen uniformly at random among all preorders on \(n\) elements, and also the distribution of cycles in a random alignment chosen uniformly at random among all alignments on \(n\) elements, as \(n\to\infty\).
MSC:
| 05A15 | Exact enumeration problems, generating functions |
| 06A05 | Total orders |
| 06A06 | Partial orders, general |
References:
| [1] | Bailey, R. W., The number of weak orderings on a finite set, Soc. Choice Welf., 15, 559-562 (1997) · Zbl 1066.91527 |
| [2] | Barthelemy, J. P., An asymptotic equivalent for the number of total preorders on a finite set, Discrete Math., 29, 311-313 (1980) · Zbl 0445.05011 |
| [3] | Bender, E. A., Central and local limit theorems applied to asymptotic enumeration, J. Combin. Theory Ser. A, 15, 91-111 (1973) · Zbl 0242.05006 |
| [4] | Bergeron, F.; Labelle, G.; Leroux, P., (Combinatorial Species and Tree-Like Structures. Combinatorial Species and Tree-Like Structures, Encyclopedia of Mathematics and its Applications, vol. 67 (1998), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0888.05001 |
| [5] | Bollobás, B., Random Graphs (1985), Academic Press · Zbl 0567.05042 |
| [6] | Cameron, P., (Oligomorphic Permutation Groups. Oligomorphic Permutation Groups, London Mathematical Society Lecture Notes, vol. 152 (1990), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0813.20002 |
| [7] | Cameron, P., Combinatorics: Topics, Techniques, Algorithms (1994), Cambridge University Press · Zbl 0806.05001 |
| [8] | Cameron, P.; Prellberg, T.; Stark, D., Asymptotic enumeration of incidence matrices, J. Phys.: Conf. Ser., 42, 59-70 (2006) |
| [9] | P. Flajolet, R. Sedgewick, Analytic combinatorics, Version of 14 February 2007 (last updated on 3 May 2007), available online at: http://algo.inria.fr/flajolet/Publications/book070503.pdf; P. Flajolet, R. Sedgewick, Analytic combinatorics, Version of 14 February 2007 (last updated on 3 May 2007), available online at: http://algo.inria.fr/flajolet/Publications/book070503.pdf · Zbl 1165.05001 |
| [10] | Fraïssé, R., Theory of Relations (1986), North-Holland: North-Holland Amsterdam · Zbl 0593.04001 |
| [11] | Gehrlein, W. V., Condorcet’s Paradox and the Likelihood of its Occurrence: Different perspectives on balanced preferences, Theory and Decision, 52, 171-199 (2002) · Zbl 1030.91500 |
| [12] | Gourdon, X., Largest component in random combinatorial structures, Discrete Math., 180, 185-209 (1998) · Zbl 0898.60014 |
| [13] | Joyal, A., Une théorie combinatoire des séries formelles, Adv. Math., 42, 1-82 (1981) · Zbl 0491.05007 |
| [14] | Maassen, H.; Bezembinder, T., Generating random weak orders and the probability of a Condorcet winner, Soc. Choice Welf., 19, 517-532 (2002) · Zbl 1072.91531 |
| [15] | Odlyzko, A. M., (Asymptotic Enumeration Methods. Asymptotic Enumeration Methods, Handbook of Combinatorics, vols. 1, 2 (1995), Elsevier: Elsevier Amsterdam), 1063-1229 · Zbl 0845.05005 |
| [16] | Pittel, B., Random set partitions: Asymptotics of subset counts, J. Combin. Theory Ser. A, 79, 326-359 (1997) · Zbl 0895.60008 |
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.
