On the sign-imbalance of partition shapes

Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2^⌊n/2⌋. We present a stronger theorem with a purely combinatorial proof using the Robinson-Schensted correspondence and a new concept called chess tableaux.We also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. The proof is built on a remarkably simple relation between the sign of a permutation and the signs of its RS-corresponding tableaux.     

On the convergence to the multiple Wiener-Itô integral

We study the convergence to the multiple Wiener-Itô integral from processes with absolutely continuous paths. More precisely, consider a family of processes, with paths in the Cameron-Martin space, that converges weakly to a standard Brownian motion in C₀([0,T]). Using these processes, we construct a family that converges weakly, in the sense of the finite dimensional distributions, to the multiple Wiener-Itô integral process of a function f∈L²(n[0,T]). We prove also the weak convergence in the space C₀([0,T]) to the second-order integral for two important families of processes that converge to a standard Brownian motion.     

Spanning forests and the golden ratio

For a graph G, let f_ij be the number of spanning rooted forests in which vertex j belongs to a tree rooted at i. In this paper, we show that for a path, the f_ij's can be expressed as the products of Fibonacci numbers; for a cycle, they are products of Fibonacci and Lucas numbers. The doubly stochastic graph matrix is the matrix F=(f_ij)_n×n/f, where f is the total number of spanning rooted forests of G and n is the number of vertices in G. F provides a proximity measure for graph vertices. By the matrix forest theorem, F^-1=I+L, where L is the Laplacian matrix of G. We show that for the paths and the so-called T-caterpillars, some diagonal entries of F (which provide a measure of the self-connectivity of vertices) converge to φ^-1 or to 1-φ^-1, where φ is the golden ratio, as the number of vertices goes to infinity. Thereby, in the asymptotic, the corresponding vertices can be metaphorically considered as “golden introverts” and “golden extroverts,” respectively. This metaphor is reinforced by a Markov chain interpretation of the doubly stochastic graph matrix, according to which F equals the overall transition matrix of a random walk with a random number of steps on G.     

Circular law, extreme singular values and potential theory

Consider the empirical spectral distribution of complex random n×n matrix whose entries are independent and identically distributed random variables with mean zero and variance 1/n. In this paper, via applying potential theory in the complex plane and analyzing extreme singular values, we prove that this distribution converges, with probability one, to the uniform distribution over the unit disk in the complex plane, i.e. the well known circular law, under the finite fourth moment assumption on matrix elements.     

Connected permutation graphs

A permutation graph is a simple graph associated with a permutation. Let c_n be the number of connected permutation graphs on n vertices. Then the sequence {c_n} satisfies an interesting recurrence relation such that it provides partitions of n! as . We also see that, if uniformly chosen at random, asymptotically almost all permutation graphs are connected.     

Graded tensor products

We study the polynomial identities of regular algebras, introduced in [A. Regev, T. Seeman, Z₂-graded tensor products of P.I. algebras, J. Algebra 291 (2005) 274-296]. For example, a finite-dimensional algebra is regular if it has a basis whose multiplication table satisfies some commutation relations. The matrix algebra M_n(F) over the field F is regular, which is closely related to M_n(F) being Z_n-graded. We study the polynomial identities of various types of tensor products of such algebras. In particular, using the theory of Hopf algebras, we prove a far reaching extension of the A⊗B theorem for Z₂-graded PI algebras.     

A test of location for exchangeable multivariate normal data with unknown correlation

We consider the problem of testing whether the common mean of a single n-vector of multivariate normal random variables with known variance and unknown common correlation ρ is zero. We derive the standardized likelihood ratio test for known ρ and explore different ways of proceeding with ρ unknown. We evaluate the performance of the standardized statistic where ρ is replaced with an estimate of ρ and determine the critical value c_n that controls the type I error rate for the least favorable ρ in [0,1]. The constant c_n increases with n and this procedure has pathological behavior if ρ depends on n and ρ_n converges to zero at a certain rate. As an alternate approach, we replace ρ with the upper limit of a (1−β_n) confidence interval chosen so that c_n=c for all n. We determine β_n so that the type I error rate is exactly controlled for all ρ in [0,1]. We also investigate a simpler approach where we bound the type I error rate. The former method performs well for all n while the less powerful bound method may be a useful in some settings as a simple approach. The proposed tests can be used in different applications, including within-cluster resampling and combining exchangeable p-values.     

Cycle extendability in graphs and digraphs

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every k×k principle submatrix of A that dominates a full cycle permutation k×k matrix is a principle submatrix of a (k+1)×(k+1) principle submatrix of A that dominates a (k+1)×(k+1) full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with S⊆{1,2,…,n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i∈S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.     

Expected length of the longest common subsequence for large alphabets

We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield that E[L]/n converges to a constant γ_k. We prove a conjecture of Sankoff and Mainville from the early 1980s claiming that as k→∞.     

The Markov chain asymptotics of random mapping graphs

In this paper the limit behavior of random mappings with n vertices is investigated. We first compute the asymptotic probability that a fixed class of finite non-intersected subsets of vertices are located in different components and use this result to construct a scheme of allocating particles with a related Markov chain. We then prove that the limit behavior of random mappings is actually embedded in such a scheme in a certain way. As an application, we shall give the asymptotic moments of the size of the largest component.     

Critical fluctuations of sums of weakly dependent random vectors

Summary LetS _n be sums of iid random vectors taking values in a Banach space andF be a smooth function. We study the fluctuations ofS _n under the transformed measureP _n given byd P _n/d P=exp (nF(S _n/n))/Z _n. If degeneracy occurs then the projection ofS _n onto the degenerate subspace, properly centered and scaled, converges to a non-Gaussian probability measure with the degenerate subspace as its support. The projection ofS _n onto the non-degenerate subspace, scaled with the usual order converges to a Gaussian probability measure with the non-degenerate subspace as its support. The two projective limits are in general dependent. We apply this theory to the critical mean field Heisenberg model and prove a central limit type theorem for the empirical measure of this model.Supported by a grant from the Swiss National Science Foundation (21–29833.90)     

Long unimodal subsequences: a problem of F.R.K. Chung

Let l(n) be the expected length of the longest unimodal subsequence of a random permutation. It is proved here that l(n)?√n converges to 2√2.This settles a conjecture of F.R.K. Chung.     

A note on weak convergence of mean residual life of stationary mixing random variables

For a sequence of strictly stationary uniform or strong mixing we estimate the mean residual time of the marginal distribution from the first n observations. Under appropriate conditions it is shown that the estimate converges weakly to a well-defined Gaussian process even when the sample size is random.     

Geometric ergodicity of Harris recurrent Marcov chains with applications to renewal theory

Let (X_n) be a positive recurrent Harris chain on a general state space, with invariant probability measure π. We give necessary and sufficient conditions for the geometric convergence of λPⁿf towards its limit π(f), and show that when such convergence happens it is, in fact, uniform over f and in L¹(π)-norm. As a corollary we obtain that, when (Xn) is geometrically ergodic, ∝ π(dx)6Pⁿ(x,·)-π6 converges to zero geometrically fast. We also characterize the geometric ergodicity of (X_n) in terms of hitting time distributions. We show that here the so-called small sets act like individual points of a countable state space chain. We give a test function criterion for geometric ergodicity and apply it to random walks on the positive half line. We apply these results to non-singular renewal processes on [0,∞) providing a probabilistic approach to the exponencial convergence of renewal measures.     

On the trajectory of an individual chosen according to supercritical Gibbs measure in the branching random walk

Consider a branching random walk on the real line. Madaule (2016) showed the renormalized trajectory of an individual selected according to the critical Gibbs measure converges in law to a Brownian meander. Besides, Chen (2015) proved that the renormalized trajectory leading to the leftmost individual at time $n$ converges in law to a standard Brownian excursion. In this article, we prove that the renormalized trajectory of an individual selected according to a supercritical Gibbs measure also converges in law toward the Brownian excursion. Moreover, refinements of this results enables to express the probability for the trajectories of two individuals selected according to the Gibbs measure to have split before time $t$, partially answering a question of Derrida and Spohn (1988).     

Pointwise properties of convergence in probability

If a sequence of random variables X_n converges to X in probability we know little about the pointwise behavior X_n(ω). In this note we show that if X_n converges to X quickly enough (for example, like n^?α for α > 0) then, for almost all ω, X_n(ω) converges to X(ω) outside a set of density zero.     

Card shuffling and a transformation on S n

Summary We consider two card shuffling schemes. The first, which has appeared in the literature previously ([G], [RB], [T]), is as follows: start with a deck ofn cards, and pick a random tuplet { 1, 2, , n} ⁿ ; interchange cards 1 andt ₁, then interchange cards 2 andt ₂, etc. The second scheme, which can be viewed as a transformation on the symmetric groupS _n , is given by the restriction of the former shuffling scheme to tuplest which form a permutation of {1, 2,,n}.We determine the bias of each of these shuffling schemes with respect to the sets of transpositions and derangements, and the expected number of fixed points of a permutation generated by each of these shuffling schemes. For the latter scheme we prove combinatorially that the permutation which arises with the highest probability is the identity. The same question is open for the former scheme. We refute a candidate answer suggested by numerical evidence [RB].This work was carried out in part while R.S. was visiting the Institute for Mathematics and its Applications and was partly supported through NSF Grant CCR-8707539.     

Departure from normality of increasing-dimension martingales

In this paper, we consider sequences of vector martingale differences of increasing dimension. We show that the Kantorovich distance from the distribution of the k(n)-dimensional average of n martingale differences to the corresponding Gaussian distribution satisfies certain inequalities. As a consequence, if the growth of k(n) is not too fast, then the Kantorovich distance converges to zero. Two applications of this result are presented. The first is a precise proof of the asymptotic distribution of the multivariate portmanteau statistic applied to the residuals of an autoregressive model and the second is a proof of the asymptotic normality of the estimates of a finite autoregressive model when the process is an AR(∞) and the order of the model grows with the length of the series.     

Rings and semigroups with permutable zero products

We consider rings R, not necessarily with 1, for which there is a nontrivial permutation σ on n letters such that x₁?x_n=0 implies x_σ(1)?x_σ(n)=0 for all x₁,…,x_n∈R. We prove that this condition alone implies very strong permutability conditions for zero products with sufficiently many factors. To this end we study the infinite sequences of permutation groups P_n(R) consisting of those permutations σ on n letters for which the condition above is satisfied in R. We give the full characterization of such sequences both for rings and for semigroups with 0. This enables us to generalize some recent results by Cohn on reversible rings and by Lambek, Anderson and Camillo on rings and semigroups whose zero products commute. In particular, we prove that rings with permutable zero products satisfy the Köthe conjecture.     

The Length of the Longest Increasing Subsequence of a Random Mallows Permutation

The Mallows measure on the symmetric group S _n is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i<j such that π _i >π _j . We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1?q) has a limit in R.