Infinite partitions of random graphs

We determine the set of canonical equivalence relations on [G]ⁿ, where G is a random graph, extending the result of Erd?s and Rado for the integers to random graphs.     

On random partitions

Let S be a finite set with n labeled elements. One of the partitions of S is selected at random each of them has the same probability. Harper determined the expected number of subsets in the random partition. Haigh studied the probability that the random partition has (at least one) subset of a given size. The present paper considers the expected number of subsets in a given size. Average and maximum are also determined. Results are generalized for the case if the number of subsets in the partition is also fixed.     

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     

Set partitions and moments of random variables

It is well known that the sequence of Bell numbers (Bn)_n?0 (Bn being the number of partitions of the set [n]) is the sequence of moments of a mean 1 Poisson random variable τ (a fact expressed in the Dobiński formula), and the shifted sequence (Bn+1)_n?0 is the sequence of moments of 1+τ. In this paper, we generalize these results by showing that both and (where is the number of m-partitions of [n], as they are defined in the paper) are moment sequences of certain random variables. Moreover, such sequences also are sequences of falling factorial moments of related random variables. Similar results are obtained when is replaced by the number of ordered m-partitions of [n]. In all cases, the respective random variables are constructed from sequences of independent standard Poisson processes.     

Entropy and maximal spacings for random partitions

Summary For rank-discounted partial sums and averages, forward and backward invariance principles are established through the use of the Bahadur-Kiefer representation of sample quantiles and the Kiefer process approximation of the sample distributions.Work supported by the Air Force Office of Scientific Research, USAF, AFSC, Grant No. AFOSR 74-2736     

Asymptotics of random partitions of a set

This paper contains two results on the asymptotic behavior of uniform probability measure on partitions of a finite set as its cardinality tends to infinity. The first one states that there exists a normalization of the corresponding Young diagrams such that the induced measure has a weak limit. This limit is shown to be a δ-measure supported by the unit square (Theorem 1). It implies that the majority of partition blocks have approximately the same length. Theorem 2 clarifies the limit distribution of these blocks. The techniques used can also be useful for deriving a range of analogous results. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 223, 1995, pp. 227–250. The paper is supported by International Science Foundation, grant MQV-100. Translated by Yu. Yakubovich     

Counting canonical partitions in the random graph

Joyce trees have concrete realizations as J-trees of sequences of 0’s and 1’s. Algorithms are given for computing the number of minimal height J-trees of d-ary sequences with n leaves and the number of them with minimal parent passing numbers to obtain polynomials ρ _n (d) for the full collection and α _n (d) for the subcollection. The number of traditional Joyce trees is the tangent number α _n (1); α _n (2) is the number of cells in the canonical partition by Laflamme, Sauer and Vuksanovic of n-element subsets of the infinite random (Rado) graph; and ρ _n (2) is the number of weak embedding types of rooted n-leaf J-trees of sequences of 0’s and 1’s. The author thanks the University of Tel Aviv for hospitality in April 2004 when much of this work was done.     

Infinite families of infinite families of congruences for k-regular partitions

Let k∈{10,15,20}, and let b _k (n) denote the number k-regular partitions of n. We prove for half of all primes p and any t≥1 that there exist p?1 arithmetic progressions modulo p ^2t such that b _k (n) is a multiple of 5 for each n in one of these progressions.     

Form factors,plane partitions,and random walks

An exactly solvable boson model, the so-called “phase model,” is considered. A relation between certain transition matrix elements of this model and boxed plane partitions, three-dimensional Young diagrams placed into a box of finite size, is established, It is shown that the natural model describing the behavior of friendly walkers, ones that can share the same lattice sites, is the “phase model.” An expression for the number of all admissible nests of lattice paths made by a fixed number of friendly walkers for a certain number of steps is obtained. Bibliography 35 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 5–30.     

Infinite families of congruences modulo 7 for broken 3-diamond partitions

The notion of broken k-diamond partitions was introduced by Andrews and Paule. Let \(\Delta _k(n)\) denote the number of broken k-diamond partitions of n for a fixed positive integer k. Recently, Paule and Radu conjectured that \(\Delta _3(343n+82)\equiv \Delta _3(343n+278)\equiv \Delta _3(343n+327)\equiv 0\ (\mathrm{mod} \ 7)\). Jameson confirmed this conjecture and proved that \(\Delta _3(343n+229)\equiv 0 \ (\mathrm{mod} \ 7)\) by using the theory of modular forms. In this paper, we prove several infinite families of Ramanujan-type congruences modulo 7 for \(\Delta _3(n)\) by establishing a recurrence relation for a sequence related to \(\Delta _3(7n+5)\). In the process, we also give new proofs of the four congruences due to Paule and Radu, and Jameson.     

Infinite-dimensional diffusions as limits of random walks on partitions

Starting with finite Markov chains on partitions of a natural number n we construct, via a scaling limit transition as n → ∞, a family of infinite-dimensional diffusion processes. The limit processes are ergodic; their stationary distributions, the so-called z-measures, appeared earlier in the problem of harmonic analysis for the infinite symmetric group. The generators of the processes are explicitly described.     

Infinite divisibility of random variables and their integer parts

It is examined to what extent the infinite divisibility of a random variable X entails the infinite divisibility of its integer part [X] or vice versa. As a special case passage times are considered in processes with independent increments such as the positive stable processes and the Gamma process. In spite of some interesting relationships, the results tend to be rather negative.     

Multiplicity of summands in the random partitions of an integer

In this paper, we prove a conjecture of Yakubovich regarding limit shapes of ‘slices’ of two-dimensional (2D) integer partitions and compositions of n when the number of summands m ~An ^α for some A?>?0 and $\alpha < \frac{1}{2}$ . We prove that the probability that there is a summand of multiplicity j in any randomly chosen partition or composition of an integer n goes to zero asymptotically with n provided j is larger than a critical value. As a corollary, we strengthen a result due to Erdös and Lehner (Duke Math. J. 8 (1941) 335–345) that concerns the relation between the number of integer partitions and compositions when $\alpha = \frac{1}{3}$ .     

Sequentially congruent partitions and partitions into squares

The Ramanujan Journal - In recent work, M. Schneider and the first author studied a curious class of integer partitions called “sequentiallyc congruent” partitions: the mth part is...     

无穷级数与无穷乘积

通过构造新的级数以研究原来级数通项的极限性质,从而得到其敛散性.该方法在精细判别和无穷乘积研究有重要有用.     

Optimal partitions

Consider a set of numbersZ={z ₁≥z ₂≥...≥z _n} and a functionf defined on subsets ofZ. LetP be a partition ofZ into disjoint subsetsS _i, say,g of them. The cost ofP is defined as $$C(P) = \sum\limits_{i = 1}^g {f(S_i )} .$$ By definition, in anordered partition, every pair of subsets has the property that the numbers in one subset are all greater than or equal to every number in the other subset. The problem of minimizingC(P) over all ordered partitions is called the optimal ordered partition problem. While no efficient method is known for solving the general optimal partition problem, the optimal ordered partition problem can be solved in quadratic time by dynamic programming. In this paper, we study the conditions onf under which an optimal ordered partition is indeed an optimal partition. In particular, we present an additive model and a multiplicative model for the functionf and give conditions such that the optimal partition problem can be reduced to the optimal ordered partition problem. We illustrate our results by applying them on problems which have been investigated previously in the literature.