most recent 30 from http://mathoverflow.net 2013-05-21T18:22:29Z http://mathoverflow.net/feeds/question/85196 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85196/distribution-of-big-component-of-set-partitions Igor Rivin 2012-01-08T15:34:51Z 2012-01-10T02:10:56Z

<p>Consider the set <code>$S_n = \{1, \dotsc, n\},$</code> and consider the set $P(n, k)$ of partitions of $S_n$ into $k$ parts (the cardinality of $P(n, k)$ is the Stirling number of the second kind $S(n, k).$ Define a function $M$ on $P(n, k),$ where $M(x)$ is the size of the biggest piece of the partition. Is there anything known about the distribution of the values of $M$ (as $n, k$ become large)? I assume that the answer is "yes", but am having trouble finding references.</p>

http://mathoverflow.net/questions/85196/distribution-of-big-component-of-set-partitions/85270#85270 Louigi Addario-Berry 2012-01-09T17:18:22Z 2012-01-10T02:10:56Z

<p>I haven't managed to find the answer to precisely your question but here are a couple of references that might be useful.</p> <p>Vershik and Yakubovich have a paper on <a href="http://www.ams.org/distribution/mmj/vol1-3-2001/vershik.pdf" rel="nofollow"><em>The limit shape and fluctuations of random partitions of naturals with a fixed number of summands</em></a>. It addresses partitions of $n$ with around $\sqrt{n}$ summands, but doesn't seem to have exactly the result you're asking about. </p> <p>If you haven't already looked at it, Chapter 1 of Pitman's <a href="http://works.bepress.com/cgi/viewcontent.cgi?article=1000&amp;context=jim_pitman" rel="nofollow"><em>Combinatorial stochastic processes</em></a> seems quite relevant to your question. In particular he states something which he calls "Kolchin's representation of Gibbs partitions". For the special case of uniformly random partitions, this can be stated as follows, I think. Fix a positive parameter $\xi$ and let $X_1,X_2,\ldots$ be iid with distribution Poisson$(\xi)$ (<b>Added on edit</b>: <em>the</em> $X_i$ <em>should be conditioned to be strictly positive</em>). Also, let $K$ be Poisson$(e^{\xi}-1)$ and independent of the $X_i$. </p> <p>Then for any $n$, conditional on the event that $X_1+\ldots+X_K=n$, the vector $(X_1,\ldots,X_K)$ is distributed as the vector of sizes of the parts of a uniformly random partition of <code>$\{1,\ldots,n\}$</code>, listed in exchangeable random order.</p> <p>You could then try conditioning both on $X_1+\ldots+X_K=n$ <em>and</em> on $K=k$, and playing with the parameter $\xi$, to read off information about partitions of <code>$\{1,\ldots,n\}$</code> into $k$ parts.</p>