Markov processes on partitions

We introduce and study a family of Markov processes on partitions. The processes preserve the so-called z-measures on partitions previously studied in connection with harmonic analysis on the infinite symmetric group. We show that the dynamical correlation functions of these processes have determinantal structure and we explicitly compute their correlation kernels. We also compute the scaling limits of the kernels in two different regimes. The limit kernels describe the asymptotic behavior of large rows and columns of the corresponding random Young diagrams, and the behavior of the Young diagrams near the diagonal. Our results show that recently discovered analogy between random partitions arising in representation theory and spectra of random matrices extends to the associated time– dependent models.     

Asymptotics of q-plancherel measures

In this paper, we are interested in the asymptotic size of the rows and columns of a random Young diagram under a natural deformation of the Plancherel measure coming from Hecke algebras. The first lines of such diagrams are typically of order n, so it does not fit in the context of the work of Biane (Int Math Res Notices 4:179–192, 2001) and ?niady (Probab. Theory Relat Fields 136:263–297, 2006). Using the theory of polynomial functions on Young diagrams of Kerov and Olshanski, we are able to compute explicitly the first- and second-order asymptotics of the length of the first rows. Our method also works for other measures, for example those coming from Schur–Weyl representations.     

Rigidity and Edge Universality of Discrete β-Ensembles

We study discrete β-ensembles as introduced in [17]. We obtain rigidity estimates on the particle locations; i.e., with high probability, the particles are close to their classical locations with an optimal error estimate. We prove the edge universality of the discrete β-ensembles; i.e., for β ≥ 1, the distribution of extreme particles converges to the Tracy-Widom β-distribution. As far as we know, this is the first proof of general Tracy-Widom β-distributions in the discrete setting. A special case of our main results implies that under the Jack deformation of the Plancherel measure, the distribution of the lengths of the first few rows in Young diagrams converges to the Tracy-Widom β-distribution, which answers an open problem in [38]. Our proof relies on Nekrasov's (or loop) equations, a multiscale analysis, and a comparison argument with continuous β-ensembles. © 2019 Wiley Periodicals, Inc.     

Asymptotical behavior of the variance of sums of random variables with random replacements

In this paper, we introduce a scheme of summation of independent random variables with random replacements. We consider a series of double arrays of identically distributed random variables that are row-wise independent, but such that neighboring rows contain a random common part of the repeating terms. By this-scheme we bscribe a model of strongly dependent noise. To investigate the sample mean of this noise, we consider the sum of random variables over the whole double array and its conditional variance with respect to replacements. For columns of the arrays we prove a covariance inequality. As a corollary of it, we demonstrate the law of large numbers for conditional variances. Bibliography: 4 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 216, 1994, pp. 124–143. Translated by A. Sudakov.     

Cellularity of a New Class of Diagram Algebras

A diagram algebra in which the diagrams include n rows of n points is constructed. Moreover, we prove that the algebra is cellular and quasi-hereditary.     

Multidimensional Hypergeometric Distribution and Characters of the Unitary Group

This paper presents the working notes by S. V. Kerov (1946–2000) written in 1993. The author introduces a multidimensional analog of the classical hypergeometric distribution. This is a probability measure M_n on the set of Young diagrams contained in the rectangle with n rows and m columns. The fact that the expression for M_n defines a probability measure is a nontrivial combinatorial identity, which is proved in various ways. Another combinatorial identity analyzed in the paper expresses a certain coherence between the measures M_n and M_n+1. A connection with Selberg-type integrals is also pointed out. The work is motivated by harmonic analysis on the infinite-dimensional unitary group. Bibliography: 25 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 301, 2003, pp. 35–91.     

Gaussian fluctuations of characters of symmetric groups and of Young diagrams

We study asymptotics of reducible representations of the symmetric groups S _q for large q. We decompose such a representation as a sum of irreducible components (or, alternatively, Young diagrams) and we ask what is the character of a randomly chosen component (or, what is the shape of a randomly chosen Young diagram). Our main result is that for a large class of representations the fluctuations of characters (and fluctuations of the shape of the Young diagrams) are asymptotically Gaussian; in this way we generalize Kerov's central limit theorem. The considered class consists of representations for which the characters almost factorize and this class includes, for example, the left-regular representation (Plancherel measure), irreducible representations and tensor representations. This class is also closed under induction, restriction, outer product and tensor product of representations. Our main tool in the proof is the method of genus expansion, well known from the random matrix theory.     

Modeling of an Asymptotically Central Markov Process on 3D Young Graph

The paper discusses the asymptotics of path probabilities in Markov processes close to a central one on 3D Young graph. We consider a one-parameter family of such processes and compute the parameter value in such a way that the centrality condition is satisfied with the greatest possible accuracy. We defined a normalized dimension of paths in the 3D Young graph. We study the growth and oscillations of these normalized dimensions along greedy and random trajectories of the processes using large computer experiments involving 3D Young diagrams with millions of boxes.     

Algebras satisfying a Capelli identity

The sequence of cocharacters (c.c.s.) of a P.I. algebra is studied. We prove that an algebra satisfies a Capelli identity if, and only if, all the Young diagrams associated with its cocharacters are of a bounded height. This result is then applied to study the identities of certain P.I. algebras, includingF _k .     

A Lanczos‐type algorithm for the QR factorization of regular Cauchy matrices

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non‐zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd.     

Central Limit Theorem for Random Strict Partitions

We consider the set of all partitions of a number n into distinct summands (the so-called strict partitions) with the uniform distribution on it and study fluctuations of a random partition near its limit shape, for large n. The use of geometrical language allows us to state the problem in terms of the limit behavior of random step functions (Young diagrams). A central limit theorem for such functions is proven. Our method essentially uses the notion of large canonical ensemble of partitions. Bibliography: 7 titles.     

Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams

We consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). For general sets of entries, these numbers of matrices are not polynomials in q (Stembridge in Ann. Comb. 2(4):365, 1998); however, when the set of entries is a Young diagram, the numbers, up to a power of q?1, are polynomials with nonnegative coefficients (Haglund in Adv. Appl. Math. 20(4):450, 1998). In this paper, we give a number of conditions under which these numbers are polynomials in q, or even polynomials with nonnegative integer coefficients. We extend Haglund’s result to complements of skew Young diagrams, and we apply this result to the case where the set of entries is the Rothe diagram of a permutation. In particular, we give a necessary and sufficient condition on the permutation for its Rothe diagram to be the complement of a skew Young diagram up to rearrangement of rows and columns. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order.     

Large deviations for increasing sequences on the plane

We prove a large deviation principle with explicit rate functions for the length of the longest increasing sequence among Poisson points on the plane. The rate function for lower tail deviations is derived from a 1977 result of Logan and Shepp about Young diagrams of random permutations. For the upper tail we use a coupling with Hammersley's particle process and convex-analytic techniques. Along the way we obtain the rate function for the lower tail of a tagged particle in a totally asymmetric Hammersley's process. Received: 22 July 1997 / Revised version: 23 March 1998     

Nearly magic rectangles

Magic squares have been extremely useful and popular in combinatorics and statistics. One generalization of magic squares is magic rectangles which are useful for designing experiments in statistics. A necessary and sufficient condition for the existence of magic rectangles restricts the number of rows and columns to be either both odd or both even. In this paper, we generalize magic rectangles to even by odd nearly magic rectangles. We also prove necessary and sufficient conditions for the existence of a nearly magic rectangle, and construct one for each parameter set for which they exist.     

Constructing weighing matrices by the method of weaving

We describe a way of obtaining new weighing matrices from old, which we call weaving because it involves distributing rows and columns of given matrices along the columns and rows of an array to form a partitioned matrix whose blocks have rank one. The method generalizes both the direct sum and direct product of matrices. We use the method to construct some new weighing matrices of relatively small order. © 1995 John Wiley & Sons, Inc.     

Unimodality and Lie Superalgebras

It is well-known how the representation theory of the Lie algebra sl(2, ?) can be used to prove that certain sequences of integers are unimodal and that certain posets have the Sperner property. Here an analogous theory is developed for the Lie superalgebra osp(1,2). We obtain new classes of unimodal sequences (described in terms of cycle index polynomials) and a new class of posets (the “super analogue” of the lattice L(m,n) of Young diagrams contained in an m × n rectangle) which have the Sperner property.     

On growth,recurrence and the Choquet-Deny Theorem for <Emphasis Type="Italic">p</Emphasis>-adic Lie groups

We first study the growth properties of p-adic Lie groups and its connection with p-adic Lie groups of type R and prove that a non-type R p-adic Lie group has compact neighbourhoods of identity having exponential growth. This is applied to prove the growth dichotomy for a large class of p-adic Lie groups which includes p-adic algebraic groups. We next study p-adic Lie groups that admit recurrent random walks and prove the natural growth conjecture connecting growth and the existence of recurrent random walks, precisely we show that a p-adic Lie group admits a recurrent random walk if and only if it has polynomial growth of degree at most two. We prove this conjecture for some other classes of groups also. We also prove the Choquet-Deny Theorem for compactly generated p-adic Lie groups of polynomial growth and also show that polynomial growth is necessary and sufficient for the validity of the Choquet-Deny for all spread-out probabilities on Zariski-connected p-adic algebraic groups. Counter example is also given to show that certain assumptions made in the main results can not be relaxed.     

Some new results regarding spikes and a heuristic for spike construction

This paper addresses the problem of minimizing the number of columns with superdiagonal nonzeroes (viz., spiked columns) in a square, nonsingular linear system of equations which is to be solved by Gaussian elimination. The exact focus is on a class of min-spike heuristics in which the rows and columns of the coefficient matrix are first permuted to block lower-triangular form. Subsequently, the number of spiked columns in each irreducible block and their heights above the diagonal are minimized heuristically.We show that ifevery column in an irreducible block has exactly two nonzeroes, i.e., is a doubleton, then there is exactly one spiked column. Further, if there is at least one non-doubleton column, there isalways an optimal permutation of rows and columns under whichnone of the doubleton columns are spiked.An analysis of a few benchmark linear programs suggests that singleton and doubleton columns can abound in practice. Hence, it appears that the results of this paper can be practically useful. In the rest of the paper, we develop a polynomial-time min-spike heuristic based on the above results and on a graph-theoretic interpretation of doubleton columns.     

Limiting Empirical Singular Value Distribution of?Restrictions of?Discrete Fourier Transform Matrices

We determine the limiting empirical singular value distribution for discrete Fourier transform (DFT) matrices when a random set of columns and rows is removed.     

Self-clique graphs and matrix permutations

The clique graph of a graph is the intersection graph of its (maximal) cliques. A graph is self-clique when it is isomorphic with its clique graph, and is clique-Helly when its cliques satisfy the Helly property. We prove that a graph is clique-Helly and self-clique if and only if it admits a quasi-symmetric clique matrix, that is, a clique matrix whose families of row and column vectors are identical. We also give a characterization of such graphs in terms of vertex-clique duality. We describe new classes of self-clique and 2-self-clique graphs. Further, we consider some problems on permuted matrices (matrices obtained by permuting the rows and/or columns of a given matrix). We prove that deciding whether a (0,1)-matrix admits a symmetric (quasi-symmetric) permuted matrix is graph (hypergraph) isomorphism complete. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 178–192, 2003