Infinite wedge and random partitions

We use representation theory to obtain a number of exact results for random partitions. In particular, we prove a simple determinantal formula for correlation functions of what we call the Schur measure on partitions (which is a far reaching generalization of the Plancherel measure; see [3], [8]) and also observe that these correlations functions are t \tau -functions for the Toda lattice hierarchy. We also give a new proof of the formula due to Bloch and the author [5] for the so-called n-point functions of the uniform measure on partitions and comment on the local structure of a typical partition.     

Total variation asymptotics for independent process approximations of logarithmic multisets and selections

Many natural unlabeled combinatorial structures, such as random partitions of the integer n, or random monic polynomials over a finite field of degree n, or unlabeled mapping patterns on n points may be described as multisets. In the usual statistical language, a multiset is an unordered sample in which number of items is variable, but the sum is a fixed value n. For these structures, the process counting the number of components of various sizes is equal in distribution to a process of independent, but not identically distributed random variables, conditioned on the value of a weighted sum. By restricting to the first b coordinates, it is possible to compare the combinatorial process directly to the independent process, and to estimate the total variation distance d_b(n) between these distributions. For a broad class of examples similar to the Ewens sampling formula we give asymptotics for d_b(n) which are valid for b=o(n/log n). The polynomial and random mapping pattern examples are covered by this result, but not the example of partitions. Similar results for selections, which are multisets with no repeated parts, such as square free polynomials, are also derived. The proofs of these results use large deviations bounds and singularity analysis of generating functions. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 51–80, 1997     

Local Limit Theorems for Sums of Power Series Distributed Random Variables and for the Number of Components in Labelled Relational Structures

A Local limit theorem for the distribution of the number of components in random labelled relational structures of size n (e.g., a type of random graphs on n vertices, random permutations of n elements, etc.) is proved as n→∞. The case when the corresponding exponential generating functions diverge at their radii of convergence is considered.     

Enumeration of lattice paths and generating functions for skew plane partitions

n-dimensional lattice paths not touching the hyperplanesX _i–X _i+1=–1,i=1,2,...,n, are counted by four different statistics, one of which is MacMahon's major index. By a reflection-like proof, heavily relying on Zeilberger's (Discrete Math. 44(1983), 325–326) solution of then-candidate ballot problem, determinantal expressions are obtained. As corollaries the generating functions for skew plane partitions, column-strict skew plane partitions, reverse skew plane plane partitions and column-strict reverse skew plane partitions, respectively, are evaluated, thus establishing partly new results, partly new proofs for known theorems in the theory of plane partitions.     

The Typical Growth of the k th Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of .     

Compositions of n as alternating sequences of weakly increasing and strictly decreasing partitions

Compositions and partitions of positive integers are often studied in separate frameworks where partitions are given by q-series generating functions and compositions exhibiting specific patterns are designated by generating functions for these patterns. Here, we view compositions as alternating sequences of weakly increasing and strictly decreasing partitions (i.e. alternating blocks). We obtain generating functions for the number of such partitions in terms of the size of the composition, the number of parts and the total number of “valleys” and “peaks”. From this, we find the total number of “peaks” and “valleys” in the composition of n which have the mentioned pattern. We also obtain the generating function for compositions which split into just two partition blocks. Finally, we obtain the two generating functions for compositions of n that start either with a weakly increasing partition or a strictly decreasing partition.     

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002     

Jagged Partitions

By jagged partitions we refer to an ordered collection of non-negative integers (n₁, n₂,..., n_m) with n_m≥ p for some positive integer p, further subject to some weakly decreasing conditions that prevent them for being genuine partitions. The case analyzed in greater detail here corresponds to p = 1 and the following conditions n_i≥ n_i+1−1 and n_i≥ n_i+2. A number of properties for the corresponding partition function are derived, including rather remarkable congruence relations. An interesting application of jagged partitions concerns the derivation of generating functions for enumerating partitions with special restrictions, a point that is illustrated with various examples. 2000 Mathematics Subject Classification: Primary—05A15, 05A17, 05A19     

On the distribution of the longest run in number partitions

We consider the distribution of the longest run of equal elements in number partitions (equivalently, the distribution of the largest gap between subsequent elements); in a recent paper, Mutafchiev proved that the distribution of this random variable (appropriately rescaled) converges weakly. The corresponding distribution function is closely related to the generating function for number partitions. In this paper, this problem is considered in more detail—we study the behavior at the tails (especially the case that the longest run is comparatively small) and extend the asymptotics for the distribution function to the entire interval of possible values. Additionally, we prove a local limit theorem within a suitable region, i.e. when the longest run attains its typical order n ^1/2, and we observe another phase transition that occurs when the largest gap is of order n ^1/4: there, the conditional probability that the longest run has length d, given that it is ≤d, jumps from 1 to 0. Asymptotics for the mean and variance follow immediately from our considerations.     

Partitioning Sets of Triples into Small Planes

We study partitions of the set of all ₃ ^v triples chosen from a v-set intopairwise disjoint planes with three points per line. Our partitions may contain copies of PG(2,2) only (Fano partitions) or copies of AG(2, 3) only (affine partitions)or copies of some planes of each type (mixed partitions).We find necessary conditions for Fano or affine partitions to exist. Such partitions are already known in severalcases: Fano partitions for v = 8 and affine partitions for v = 9 or 10. We constructsuch partitions for several sporadic orders, namely, Fano partitions for v = 14, 16, 22, 23, 28, andan affine partition for v = 18. Using these as starter partitions, we prove that Fano partitionsexist for v = 7 ⁿ + 1, 13 ⁿ + 1,27 ⁿ + 1, and affine partitions for v = 8 ⁿ + 1,9 ⁿ + 1, 17 ⁿ + 1. In particular, both Fano and affine partitionsexist for v = 3⁶ⁿ + 1. Using properties of 3-wise balanced designs, weextend these results to show that affine partitions also exist for v = 3²ⁿ .Similarly, mixed partitions are shown to exist for v = 8 ⁿ ,9 ⁿ , 11 ⁿ + 1.     

From recursions to asymptotics: Durfee and dilogarithmic deductions

We consider two dimensional arrays p(n,k) which count a family of partitions of n by a second parameter k, usually the number of parts. Such arrays frequently satisfy a finite recursion of a certain form, detailed in formula (2), as well as an asymptotic relation

(∗)

For such situations, we can characterize (Theorem 1) the function g(u) in terms of a polynomial associated with the recursion. We also identify (Theorem 2) a class of families which satisfy both the desired recursion and the limit law (*). For such families, the function g(u) is characterized by Theorem 1, and this resolves a number of conjectures made in an earlier work [Electron. J. Combin. 5 (1998) R32] concerning asymptotic enumeration of partitions by the size of their Durfee square. Finally, we study a family of partitions introduced by Andrews [Amer. J. Math. 91 (1969) 18–24]. These partitions do satisfy the desired recursion, but it is not known for sure whether they also satisfy the accompanying limit law. We prove (Theorem 3), conditionally on the conjectured limit law holding, some identities involving the dilogarithm. These identities are seen empirically, by calculation to many decimal places, to be true.     

The central limit theorem on spaces of positive definite matrices

A central limit theorem is obtained for orthogonally invariant random variables on _n, the space of n × n real, positive definite symmetric matrices. The derivation requires the Taylor expansion of the spherical functions for the general linear group GL(n, R). This extends from the case n = 3 a result of Terras (J. Multivariate Anal. 23 (1987), 13–36).     

Random Partitions by Semigroup Methods

P of all partitions of {1,2,3,...}, or rather its distribution. There is a natural compact metrizable topology on P taking care of measurability questions. With respect to the maximum operation P becomes an abelian semigroup, and our first theorem characterizes random partitions as normalized positive definite functions on the subsemigroup of partitions "with finite support". We then present a new proof of Kingman's theorem stating that the exchangeable random partitions form a simplex whose extreme points are the so-called "paint-box distributions". An interesting moment problem which is still open arises in this connection.     

Twisted Gelfand Pairs of Complex Reflection Groups and r-Congruence Properties of Schur Functions

This note gives the r-congruence properties of Schur functions which arise from a twisted Gelfand pair (G(r, 1, n), S _n , sgn). Numerators of the Weyl character formula of type A appear in Specht modules for the complex reflection groups indexed by column partitions. This fact is applied to the study of Schur functions.     

Exchangeable and partially exchangeable random partitions

Summary Call a random partition of the positive integerspartially exchangeable if for each finite sequence of positive integersn ₁,...,n _k, the probability that the partition breaks the firstn ₁+...+n_k integers intok particular classes, of sizesn ₁,...,n_k in order of their first elements, has the same valuep(n ₁,...,n_k) for every possible choice of classes subject to the sizes constraint. A random partition is exchangeable iff it is partially exchangeable for a symmetric functionp(n ₁,...n_k). A representation is given for partially exchangeable random partitions which provides a useful variation of Kingman's representation in the exchangeable case. Results are illustrated by the two-parameter generalization of Ewens' partition structure.Research supported by N.S.F. Grants MCS91-07531 and DMS-9404345     

Bisecting sparse random graphs

Consider partitions of the vertex set of a graph G into two sets with sizes differing by at most 1: the bisection width of G is the minimum over all such partitions of the number of “cross edges” between the parts. We are interested in sparse random graphs G_{n, c/n} with edge probability c/n. We show that, if c>ln 4, then the bisection width is Ω(n) with high probability; while if c<ln 4, then it is equal to 0 with high probability. There are corresponding threshold results for partitioning into any fixed number of parts. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 31–38, 2001     

Linked partitions and linked cycles

The notion of noncrossing linked partition arose from the study of certain transforms in free probability theory. It is known that the number of noncrossing linked partitions of [n+1] is equal to the n-th large Schröder number r_n, which counts the number of Schröder paths. In this paper we give a bijective proof of this result. Then we introduce the structures of linked partitions and linked cycles. We present various combinatorial properties of noncrossing linked partitions, linked partitions, and linked cycles, and connect them to other combinatorial structures and results, including increasing trees, partial matchings, k-Stirling numbers of the second kind, and the symmetry between crossings and nestings over certain linear graphs.     

Brownian bridge asymptotics for random mappings

Uniform random mappings of an n-element set to itself have been much studied in the combinatorial literature. We introduce a new technique, which starts by specifying a coding of mappings as walks with ± 1 steps. The uniform random mapping is thereby coded as a nonuniform random walk, and our main result is that as n→∞ the random walk rescales to reflecting Brownian bridge. This result encompasses a large number of limit theorems for “global” characteristics of uniform random mappings. © 1994 John Wiley & Sons, Inc.     

Analysis of some new partition statistics

We study several statistics for integer partitions: for a random partition of an integer n we consider the average size of the smallest gap (missing part size), the multiplicity of the largest part, and the largest repeated part size. Furthermore, we estimate the number of gap-free partitions of n. 2000 Mathematics Subject Classification Primary—05A17; Secondary—11P82 Dedicated to Helmut Prodinger on the occasion of his 50th birthday P.J. Grabner is supported by the START-project Y96-MAT of the Austrian Science Fund. This material is based upon work supported by the National Research Foundation under grant number 2053740.