×

zbMATH — the first resource for mathematics

Confirming two conjectures about the integer partitions. (English) Zbl 0937.05008
The author answers a question posed by I. G. Macdonald in [Symmetric functions and Hall polynomials. 2nd ed. (Clarendon Press, Oxford) (1995; Zbl 0824.05059)]. He proves that if two partitions, \(\lambda\) and \(\mu\), are chosen uniformly at random and independent of each other from the set of partitions of \(n\), then the probability that \(\lambda\) and \(\mu\) are comparable in the usual dominance order approaches 0 as \(n\) approaches infinity. From the Gale-Ryser theorem, it follows that if \(\pi_n\) is the probability that there exists a bipartite graph on \((X,Y)\) such that \(\lambda\) and \(\mu\) are the degree sequences of the respective vertex sets, then \(\lim_{n\to \infty} \pi_n = 0\). The same methods enable the author to prove a conjecture made by Wilf in 1982: The probability that a randomly chosen partition of \(n\) is the degree sequence of a graph approaches 0 as \(n\) approaches infinity.

MSC:
05A17 Combinatorial aspects of partitions of integers
05C07 Vertex degrees
60F05 Central limit and other weak theorems
60F20 Zero-one laws
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Auluck, F.C.; Chowla, S.; Gupta, H., On the maximum value of partitions of n into k parts, J. Indian math. soc., 6, 105-112, (1942) · Zbl 0063.00139
[2] Barnes, T.M.; Savage, C.D., A recurrence for counting graphical partitions, Electron. J. combin., 2, (1995) · Zbl 0818.05003
[3] Brualdi, R.A.; Ryser, H.J., Combinatorial matrix theory, Encyclopedia of mathematics and its applications, (1992), Cambridge University Press Cambridge
[4] Brylawski, T., The lattice of integer partitions, Discrete mathematics, 6, 201-219, (1973) · Zbl 0283.06003
[5] Diaconis, P., Group representations in probability and statistics, Institute of mathematical statistics, Lecture notes—monograph series, 11, (1988), Hayward · Zbl 0695.60012
[6] Erdős, P.; Gallai, T., Graphs with given degree of vertices, Mat. lapok, 11, 264-274, (1960)
[7] Erdős, P.; Lehner, J., The distribution of the number of summands in the partition of a positive integer, Duke math. J., 8, 335-345, (1941) · JFM 67.0126.02
[8] Erdős, P.; Richmond, L.B., On graphical partitions, Combinatorica, 13, 57-63, (1993)
[9] Feller, W., An introduction to probability theory and its applications, II, (1971), John Wiley & Sons New York · Zbl 0219.60003
[10] Fristedt, B., The structure of random partitions of large integers, Trans. amer. math. soc., 337, 703-735, (1993) · Zbl 0795.05009
[11] Macdonald, I.G., Symmetric functions and Hall polynomials, 2nd edition, (1995), Oxford Univ. PressOxford Sci. Publ London · Zbl 0487.20007
[12] Pittel, B., On a likely shape of the random Ferrers diagram, Adv. in appl. math., 18, 432-488, (1997) · Zbl 0894.11039
[13] Rousseau, C.; Ali, F., On a conjecture concerning graphical partitions, Congr. numer., 104, 150-160, (1994) · Zbl 0836.05006
[14] Sagan, B.E., The symmetric group: representations, combinatorial algorithms, & symmetric functions, (1991), Wadsworth & Brooks/Cole Pacific Grove · Zbl 0823.05061
[15] Sierksma, G.; Hoogeveen, H., Seven criteria for integer sequences being graphic, Journal of graph theory, 15, 223-231, (1991) · Zbl 0752.05052
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.