✦ LIBER ✦

Random Set Partitions: Asymptotics of Subset Counts

✍ Scribed by Boris Pittel

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 450 KB
Volume: 79
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1997.2791

No coin nor oath required. For personal study only.

✦ Synopsis

We study the asymptotics of subset counts for the uniformly random partition of the set [n]. It is known that typically most of the subsets of the random partition are of size r, with re r =n. Confirming a conjecture formulated by Arratia and Tavare , we prove that the counts of other subsets are close, in terms of the total variation distance, to the corresponding segments of a sequence [Z j ] of independent, Poisson (r j Âj!) distributed random variables. DeLaurentis and Pittel had proved that the finite dimensional distributions of a continuous time process that counts the typical size subsets converge to those of the Brownian Bridge process. Combining the two results allows to prove a functional limit theorem which covers a broad class of the integral functionals. Among illustrations, we prove that the total number of refinements of a random partition is asymptotically lognormal.

📜 SIMILAR VOLUMES

Counting subsets of the random partition

Counting subsets of the random partition and the ‘Brownian Bridge’ process

✍ J.M. DeLaurentis; B.G. Pittel 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 522 KB

Maximum Antichains in Random Subsets of

Maximum Antichains in Random Subsets of a Finite Set

✍ Deryk Osthus 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 125 KB

We consider the random poset P(n, p) which is generated by first selecting each subset of [n]=[1, ..., n] with probability p and then ordering the selected subsets by inclusion. We give asymptotic estimates of the size of the maximum antichain for arbitrary p= p(n). In particular, we prove that if p

On the asymptotic distributions of subgr

On the asymptotic distributions of subgraph counts in a random tournament

✍ Pontus Andersson 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

A random tournament T is obtained by independently orienting the edges of n 1 the complete graph on n vertices, with probability for each direction. We study the 2 asymptotic distribution, as n tends to infinity, of a suitable normalization of the number of subgraphs of T that are isomorphic to a gi

Partitions of the 4-subsets of a 13-set

Partitions of the 4-subsets of a 13-set into disjoint projective planes

✍ Leo G. Chouinard II 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 422 KB

For I G t < k CI u. let S(t, k, u) denote a Steiner system and let Pr, (u) be the set of all k-subsets of theset {i,2,..., u}. We partition PJ 13) into 55 mutually disjoint S(2.4, 13)'s (projective planes). This is the first known example of a complete partition of Pk(u) into disjoint S(t, k, u)'s f

Generation of a random partition of a fi

Generation of a random partition of a finite set by an urn model

✍ A.J Stam 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 427 KB

Counting Pattern-free Set Partitions I:

Counting Pattern-free Set Partitions I: A Generalization of Stirling Numbers of the Second Kind

✍ Martin Klazar 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 160 KB

A partition u of [k] = {1, 2, . . . , k} is contained in another partition v of [l] if [l] has a k-subset on which v induces u. We are interested in counting partitions v not containing a given partition u or a given set of partitions R. This concept is related to that of forbidden permutations. A s