Confirming Two Conjectures About the Integer Partitions

摘要

For a given integer n, let #LAMBDA#_n denote the set of all integer partitions #lambda#_1 >= #lambda#_2 >= ... >= #lambda#_m > 0 (m >= 1), of n. For the dominance order "<=" on #LAMBDA#_n, we show that if two partitions #lambda#, #mu# are both chosen from #LAMBDA#_n uniformly at random, and independent of each other, then Pr(#lambda# <= #mu#)-> 0 as n -> infinity. This statement answers affirmatively a question posed by Macdonald in 1979. The proof is based on the limit joint distribution of the largest parts counts found by Fristedt. A slight modification of the argument confirms a conjecture made by Wilf in 1982, namely that, for n even, the probability of a random partition being graphical is zero in the limit. The proof of the latter follows the footsteps of Erdos and Richmond who saw that to confirm Will's conjecture it would be sufficient to show that the probability of the first k Erdos-Gallai conditions of a partition being graphical approaches 0 as n, and then k approach infinity. The reason that the proofs of two seemingly unrelated conjectures turned out to be so close is that, as the E-R analysis revealed, the (joint) distribution of the largest part sizes in a partition #lambda# and its dual #lambda#' coincides, in the limit, with the distribution of the largest part sizes for two independent partitions.