Successions in integer partitions

A partition of an integer n is a representation n=a ₁+a ₂+⋅⋅⋅+a _k , with integer parts 1≤a ₁≤a ₂≤…≤a _k . For any fixed positive integer p, a p-succession in a partition is defined to be a pair of adjacent parts such that a _i+1−a _i =p. We find generating functions for the number of partitions of n with no p-successions, as well as for the total number of such successions taken over all partitions of n. In the process, various interesting partition identities are derived. In addition, the Hardy-Ramanujan asymptotic formula for the number of partitions is used to obtain an asymptotic estimate for the average number of p-successions in the partitions of n. This material is based upon work supported by the National Research Foundation under grant number 2053740.     

Square-bounded partitions and Catalan numbers

For each integer k≥1, we define an algorithm which associates to a partition whose maximal value is at most k a certain subset of all partitions. In the case when we begin with a partition λ which is square-bounded, i.e. λ=(λ ₁≥⋅⋅⋅≥λ _k ) with λ ₁=k and λ _k =1, applying the algorithm ℓ times gives rise to a set whose cardinality is either the Catalan number c _ℓ−k+1 (the self dual case) or twice that Catalan number. The algorithm defines a tree and we study the propagation of the tree, which is not in the isomorphism class of the usual Catalan tree. The algorithm can also be modified to produce a two-parameter family of sets and the resulting cardinalities of the sets are the ballot numbers. Finally, we give a conjecture on the rank of a particular module for the ring of symmetric functions in 2ℓ+m variables.     

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     

Topology of spaces of hyperbolic polynomials and combinatorics of resonances

In this paper we study the topology of the strata, indexed by number partitions λ, in the natural stratification of the space of monic hyperbolic polynomials of degreen. We prove stabilization theorems for removing an independent block or an independent relation in λ. We also prove contractibility of the ‘one-point compactifications of the strata indexed by a large class of number partitions, including λ=(k ^m , 1 ^r ), form≥2. Furthermore, we study the maps between the homology groups of the strata, induced by imposing additional relations (resonances) on the number partition λ, or by merging some of the blocks of λ.     

A necessary and sufficient condition to a pareto optimal without optimizing the weighting criterion

The easiest thecnique to reduce the classical multiple criteria decision problem into a reasonable single criterion decision problem is the weighting method. Po-Lung Yu (1985) gives a well known necessary condition fory ⁰ to be a Pareto optimal, namelyy ⁰ maximizes λ^ty overY, for some λ ∈ℝ ^p, such that λ_i≥0 for alli and some λ_j>0. In this brief note we generalize the necessary condition of Po-Lung Yu.     

On the replications of certain multiplicative designs

Bounds on the number of row sums in ann×n, non-singular (0,1)-matrixA sarisfyingA ^tA=diag (k ₁-λ₁,…,k _n-λ_n),k _j>λ_j>0,λ₁=…=λ_e,λ_e+1=…=λ_n are obtained which extend previous results for such matrices.     

On core and bar-core partitions

If s and t are relatively prime integers, J.B. Olsson proved in (J. Comb. Theory, Ser. A 116:733–740, 2009) that the s-core of a t-core partition is again a t-core partition, and that the s-bar-core of a t-bar-core partition is again a t-bar-core partition. Here generalised results are proved for partitions and bar partitions when the restriction that s and t be relatively prime is removed.     

An asymptotic formula for the t-core partition function and a conjecture of Stanton

For a positive integer t, a partition is said to be a t-core if each of the hook numbers from its Ferrers-Young diagram is not a multiple of t. In 1996, Granville and Ono proved the t-core partition conjecture, that at(n), the number of t-core partitions of n, is positive for every nonnegative integer n as long as t?4. As part of their proof, they showed that if p?5 is prime, the generating function for ap(n) is essentially a multiple of an explicit Eisenstein Series together with a cusp form. This representation of the generating function leads to an asymptotic formula for ap(n) involving L-functions and divisor functions. In 1999, Stanton conjectured that for t?4 and n?t+1, at(n)?at+1(n). Here we prove a weaker form of this conjecture, that for t?4 and n sufficiently large, at(n)?at+1(n). Along the way, we obtain an asymptotic formula for at(n) which, in the cases where t is coprime to 6, is a generalization of the formula which follows from the work of Granville and Ono when t=p?5 is prime.     

Clustering of linearly interacting diffusions and universality of their long-time limit distribution

Let K⊂ℝ ^d (d≥ 1) be a compact convex set and Λ a countable Abelian group. We study a stochastic process X in K ^Λ, equipped with the product topology, where each coordinate solves a SDE of the form dX _i (t) = ∑ _j a(j−i) (X _j (t) −X _i (t))dt + σ (X _i (t))dB _i (t). Here a(·) is the kernel of a continuous-time random walk on Λ and σ is a continuous root of a diffusion matrix w on K. If X(t) converges in distribution to a limit X(∞) and the symmetrized random walk with kernel a _S (i) = a(i) + a(−i) is recurrent, then each component X _i (∞) is concentrated on {x∈K : σ(x) = 0 and the coordinates agree, i.e., the system clusters. Both these statements fail if a _S is transient. Under the assumption that the class of harmonic functions of the diffusion matrix w is preserved under linear transformations of K, we show that the system clusters for all spatially ergodic initial conditions and we determine the limit distribution of the components. This distribution turns out to be universal in all recurrent kernels a _S on Abelian groups Λ. Received: 10 May 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000     

On the influence of parameters determining anisotropic spaces of smooth functions on characteristics of the embedding theorems

An anisotropic Sobolev and Nikol'skii-Besov space on a domain G is determined by its integro-differential (shortly, ID) parameters. On the other hand, the geometry of G is characterized by the set Λ(G) of all vectors λ=(λ₁,..., λ_n) such that G satisfies the λ-horn condition. We study the dependence of the totality of possible embeddings upon the set Λ(G) and theID-parameters of the space. We consider only embeddings with q≥pⁱ, where pⁱ are the integral parameters of the space and q is the integral embedding parameter. For a given space, we introduce its initial matrix A₀ determined by theID-parameters. A₀ turns out to be a Z-matrix. On the basis of a natural classification of Z-matrices, a classification of anisotropic spaces is introduced. This classification allows one to restate the existence of an embedding with q≥pⁱ in terms of certain specific properties of A₀. Let A₀ be a nondegenerate M-matrix. Any vector λ∈Λ(G) gives rise to a certain set of admissible values of the embedding parameters. We call λ optimal if this set is the largest possible. It turns out that the optimal vector λ _G ^* is determined by Λ(G) and A₀, and may be found by a linear optimization procedure. The following cases are possible: a) , b) , c) λ _G ^* does not exist. In case a) the set of admissible values of the embedding parameters is the biggest, while in case c) no embeddings with q≥pⁱ exist. In case b) the so-called saturation phenomenon occurs, i.e., certain variations of some differential parameters of the space do not change the set of admissible values of the embedding parameters. The latter fact has some applications to the problem of extension of all functions belonging to the given space from G to Eⁿ. Bibliography: 20 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 201, 1992, pp. 22–94. Translated by A. A. Mekler.     

On the multiplicity of the eigenvalues of a graph

Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q ₁(t)q ₂(t)² ... q _m (t)^m, where each q _i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q _j (t). We give an algorithm to construct the polynomials q _i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λ_i| of G, where λ₁, λ₂, ..., λ_n are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.     

A remark on the unitary group of a tensor product of<Emphasis Type="Italic">n</Emphasis> finite-dimensional Hilbert spaces

LetH _i, 1 ≤ i ≤n be complex finite-dimensional Hilbert spaces of dimension d_i,1 ≤ i ≤n respectively withd _i ≥ 2 for everyi. By using the method of quantum circuits in the theory of quantum computing as outlined in Nielsen and Chuang [2] and using a key lemma of Jaikumar [1] we show that every unitary operator on the tensor productH =H ₁ ⊗H ₂ ⊗... ⊗H _n can be expressed as a composition of a finite number of unitary operators living on pair productsH _i ⊗H _j,1 ≤i,j ≤n. An estimate of the number of operators appearing in such a composition is obtained. Dedicated to Prof. A.K. Roy on his 62nd birthday.     

Net subrings of generalized matrix rings

Let Λ be a ring with the following properties: (a) Λ is a direct sum of left ideals P₁,..., P_n; (b) every nontrivial homomorphism P_i→P_j is a monomorphism; (c) for every i, j the intersection of any two submodules of P_j isomorphic to P_i contains a submodule isomorphic to P_i. Then Λ can be represented as a subring associated with a net of ideals in a generalized matrix ring. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 211, 1994, pp. 184–198. Translated by A. V. Yakovlev.     

On the evolution of islands

Letn cells be arranged in a ring, or alternatively, in a row. Initially, all cells are unmarked. Sequentially, one of the unmarked cells is chosen at random and marked until, aftern steps, each cell is marked. After thekth cell has been marked the configuration of marked cells defines some number of islands: maximal sets of adjacent marked cells. Let ξ _k denote the random number of islands afterk cells have been marked. We give explicit expressions for moments of products of ξ _k ’s and for moments of products of 1/ξ _k ’s. These are used in a companion paper to prove that if a random graph on the natural number is made by drawing an edge betweeni≧1 andj>i with probabilityλ/j, then the graph is almost surely connected ifλ>1/4 and almost surely disconnected ifλ≦1/4.     

Sudakov-type minoration for gaussian chaos processes

Consider a setA of symmetricn×n matricesa=(a _i,j) _i,j≤n . Consider an independent sequence (g _i) _i≤n of standard normal random variables, and letM=Esup_a∈A|Σ_i,j⪯na_i,jg_ig_j|. Denote byN ₂(A, α) (resp.N _t(A, α)) the smallest number of balls of radiusα for thel ₂ norm ofR ^{n 2} (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN ₂(A, α))^1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN _t≤K(δ)M. Work partially supported by an N.S.F. grant.     

On the blow-up of solutions to anisotropic parabolic equations with variable nonlinearity

The aim of this paper is to establish sufficient conditions of the finite time blow-up in solutions of the homogeneous Dirichlet problem for the anisotropic parabolic equations with variable nonlinearity $ u_t = \sum\nolimits_{i = 1}^n {D_i (a_i (x,t)|D_i u|^{p^i (x) - 2} D_i u) + \sum\nolimits_{i = 1}^K {b_i (x,t)|u|^{\sigma _i (x,t) - 2} u} } $ u_t = \sum\nolimits_{i = 1}^n {D_i (a_i (x,t)|D_i u|^{p^i (x) - 2} D_i u) + \sum\nolimits_{i = 1}^K {b_i (x,t)|u|^{\sigma _i (x,t) - 2} u} } . Two different cases are studied. In the first case a _i ≡ a _i (x), p _i ≡ 2, σ _i ≡ σ _i (x, t), and b _i (x, t) ≥ 0. We show that in this case every solution corresponding to a “large” initial function blows up in finite time if there exists at least one j for which min σ _j (x, t) > 2 and either b _j > 0, or b _j (x, t) ≥ 0 and Σ_π b _j ^−ρ(t)(x, t) dx < ∞ with some σ(t) > 0 depending on σ _j . In the case of the quasilinear equation with the exponents p _i and σ _i depending only on x, we show that the solutions may blow up if min σ _i ≥ max p _i , b _i ≥ 0, and there exists at least one j for which min σ _j > max p _j and b _j > 0. We extend these results to a semilinear equation with nonlocal forcing terms and quasilinear equations which combine the absorption (b _i ≤ 0) and reaction terms.     

Small deviations of the maximal element of a sequence of weighted independent random variables

Consider a sequence {X _i } of independent copies of a nonnegative random variable X and let M = sup _{j ≥ 1}λ _j X _j , where {λ _j } is a nonincreasing sequence of positive numbers for which P(M < ∞) = 1. The asymptotic behavior of -logP(M < r) as r → 0 is studied.     

Sparse exponential systems: Completeness with estimates

According to A. Beurling and H. Landau, if an exponential system {e ^iλt }_λ∈Λ is a frame in L ² on a set S of positive measure, then Λ must satisfy a strong density condition. We replace the frame concept by a weaker condition and prove that if S is a finite union of segments then the result holds. However, for “generic” S, very sparse sequences Λ are admitted. Supported in part by the Israel Science Foundation.     

Moderate Deviations for Random Sums of Heavy-Tailed Random Variables

Let {Xn;n≥ 1} be a sequence of independent non-negative random variables with common distribution function F having extended regularly varying tail and finite mean μ = E（X1） and let {N（t）; t ≥0} be a random process taking non-negative integer values with finite mean λ（t） = E（N（t）） and independent of {Xn; n ≥1}. In this paper, asymptotic expressions of P（（X1 ＋… ＋XN（t）） -λ（t）μ 〉 x） uniformly for x ∈[γb（t）, ∞） are obtained, where γ〉 0 and b（t） can be taken to be a positive function with limt→∞ b（t）/λ（t） = 0.