On the Lipschitz constant of the RSK correspondence

We view the RSK correspondence as associating to each permutation π∈Sn a Young diagram λ=λ(π), i.e. a partition of n. Suppose now that π is left-multiplied by t transpositions, what is the largest number of cells in λ that can change as a result? It is natural refer to this question as the search for the Lipschitz constant of the RSK correspondence.We show upper bounds on this Lipschitz constant as a function of t. For t=1, we give a construction of permutations that achieve this bound exactly. For larger t we construct permutations which come close to matching the upper bound that we prove.     

The peak and descent statistics over ballot permutations

A ballot permutation is a permutation π such that in any prefix of π the descent number is not more than the ascent number. By using a reversal-concatenation map, we (i) give a formula for the joint distribution (pk, des) of the peak and descent statistics over ballot permutations, (ii) connect this distribution and the joint distribution (pk, des) over ordinary permutations in terms of generating functions, and (iii) confirm Spiro's conjecture which finds the equidistribution of the descent statistic for ballot permutations and an analogue of the descent statistic for odd order permutations.     

Signatures of Strings

The parity of a permutation π can be defined as the parity of the number of inversions in π. The signature ε(π) of π is an encoding of the parity in a multiplicative group of order 2: ε(π) = (?1)^inv(π). It is also well known that half of the permutations of a finite set are even and half are odd. In this paper, we explore the natural notion of parity for larger moduli; that is, we define the m-signature of a permutation π to be the number of inversions of π, reduced modulo m. Unlike with the 2-signatures of permutations of sets, the m-signatures of the permutations of a multiset are not typically equi-distributed among the modulo m residue classes, though the distribution is close to uniform. We present a recursive method of calculating the distribution of m-signatures of permutations of a multiset, develop properties of this distribution, and present sufficient conditions for the distribution to be uniform.     

Some permutation problems

Put Z_n = {1, 2,…, n} and let π denote an arbitrary permutation of Z_n. Problem I. Let π = (π(1), π(2), …, π(n)). π has an up, down, or fixed point at a according as a < π(a), a > π(a), or a = π(a). Let $\text{A}\text{(r, s, t)}$ be the number of π ∈ Z_n with r ups, s downs, and t fixed points. Problem II. Consider the triple π^?1(a), a, π(a). Let R denote an up and F a down of π and let B(n, r, s) denote the number of π ∈ Z_n with r occurrences of π^?1(a)RaRπ(a) and s occurrences of π^?1(a)FaFπ(a). Generating functions are obtained for each enumerant as well as for a refinement of the second. In each case use is made of the cycle structure of permutations.     

Counting strings in Dyck paths

This paper deals with the enumeration of Dyck paths according to the statistic “number of occurrences of τ”, for an arbitrary string τ. In this direction, the statistic “number of occurrences of τ at height j” is considered. It is shown that the corresponding generating function can be evaluated with the aid of Chebyshev polynomials of the second kind. This is applied to every string of length 4. Further results are obtained for the statistic “number of occurrences of τ at even (or odd) height”.     

Standing waves in a counter-rotating vortex filament pair

The distance among two counter-rotating vortex filaments satisfies a beam-type of equation according to the model derived in [15]. This equation has an explicit solution where two straight filaments travel with constant speed at a constant distance. The boundary condition of the filaments is 2π-periodic. Using the distance of the filaments as bifurcating parameter, an infinite number of branches of periodic standing waves bifurcate from this initial configuration with constant rational frequency along each branch.     

Uniform distribution of generalized Kakutani’s sequences of partitions

We consider a generalized version of Kakutani’s splitting procedure where an arbitrary starting partition π is given and in each step all intervals of maximal length are split into m parts, according to a splitting rule ρ. We give conditions on π and ρ under which the resulting sequence of partitions is uniformly distributed.     

Nonrepetitive colorings of trees

A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number, denoted by π(G). A famous theorem of Thue asserts that π(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that π(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with π(T)=4 we show that any of them has a sufficiently large subdivision H such that π(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words. We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most Δ+1 colors without repetitions on paths.     

Order estimates for irreducible projections in L2 of a nilmanifold

Let π be an irreducible representation occurring in $\text{L}$²(Г?N), where N is a nilpotent Lie group and Γ is a discrete, cocompact subgroup. The projection onto the π-equivariant subspace is given by convolution against a distribution D_π. For certain π, we obtain an estimate on the order of D_π. The condition on π involves an extension of the “canonical objects” associated to elements of the Kirillov orbit of π; there does not appear to be an example in the literature where it is not satisfied.     

Perfect state transfer in cubelike graphs

Suppose C is a subset of non-zero vectors from the vector space . The cubelike graphX(C) has as its vertex set, and two elements of are adjacent if their difference is in C. If M is the d×|C| matrix with the elements of C as its columns, we call the row space of M the code of X. We use this code to study perfect state transfer on cubelike graphs. Bernasconi et al. have shown that perfect state transfer occurs on X(C) at time π/2 if and only if the sum of the elements of C is not zero. Here we consider what happens when this sum is zero. We prove that if perfect state transfer occurs on a cubelike graph, then it must take place at time τ=π/2D, where D is the greatest common divisor of the weights of the code words. We show that perfect state transfer occurs at time π/4 if and only if D=2 and the code is self-orthogonal.     

Bruhat intervals as rooks on skew Ferrers boards

We characterise the permutations π such that the elements in the closed lower Bruhat interval [id,π] of the symmetric group correspond to non-taking rook configurations on a skew Ferrers board. It turns out that these are exactly the permutations π such that [id,π] corresponds to a flag manifold defined by inclusions, studied by Gasharov and Reiner.Our characterisation connects the Poincaré polynomials (rank-generating function) of Bruhat intervals with q-rook polynomials, and we are able to compute the Poincaré polynomial of some particularly interesting intervals in the finite Weyl groups An and Bn. The expressions involve q-Stirling numbers of the second kind, and for the group An putting q=1 yields the poly-Bernoulli numbers defined by Kaneko.     

An example of the Weierstrass semigroup of a pointed curve on K3 surfaces

Let X be a K3 surface with Picard number one which is given by a double cover π:X→?². Let C be a smooth curve on X with π ^?1 π(C)=C which is not the ramification divisor of π, and let P be a ramification point of π| _C :C→π(C). In this paper, in the case where the intersection multiplicity at π(P) of the curve π(C) and the tangent line at π(P) on π(C) is equal to deg(π(C)) or deg(π(C))?1, we investigate the Weierstrass semigroup of the pointed curve (C,P).     

Partitions of a set satisfying certain set of conditions

In this paper we present a new combinatorial class enumerated by Catalan numbers. More precisely, we establish a bijection between the set of partitions π₁π₂?π_n of [n] such that π_i+1−π_i≤1 for all i=,1,2…,n−1, and the set of Dyck paths of semilength n. Moreover, we find an explicit formula for the generating function for the number of partitions π₁π₂?π_n of [n] such that either π_i+?−π_i≤1 for all i=1,2,…,n−?, or π_i+1−π_i≤m for all i=1,2,…,n−1.     

Applications of character estimates to statistical problems for the symmetric group

Let π,σ ∈ S _n be chosen at random. Using character estimates we show that in various aspects the elements πσ ⁱ behave like independent random variables. As application we show that almost surely the Cayley graph determined by π and σ has diameter O(n ³ logn), and the directed Cayley-graph has almost surely diameter O(n ⁴ logn). Further we describe an algorithm for the black-box-recognition of the symmetric group, and show that for each element τ moving a positive proportion of all points, the number of cycles of a random element σ and of τσ are nearly independent.     

Bounded, attractive and repulsive Markov specifications on trees and on the one-dimensional lattice

Let Π be a homogenous Markov specification associated with a countable state space S and countably infinite parameter space A possessing a neighbor relation ~ such that (A,~) is the regular tree with d +1 edges meeting at each vertex. Let $\text{g}$(π)be the simplex of corresponding Markov random fields. We show that if Π satisfies a ‘boundedness’ condition then $\text{g}$(π).We further study the structure of $\text{g}$(π) when Π is either attractive or repulsive with respect to a linear ordering on S. When d = 1, so that (A, ~) is the one-dimensional lattice, we relax the requirement of homogeneity to that of stationarity; here we give sufficient conditions for $\text{g}$(π) and for $\text{g}$(π)to have precisely one member.     

Equidistribution of numerical semigroup gaps modulo m

For a positive integer m, a finite set of integers is said to be equidistributed modulo m if the set contains an equal number of elements in each congruence class modulo m. In this paper, we consider the problem of determining when the set of gaps of a numerical semigroup S is equidistributed modulo m. Of particular interest is the case when the nonzero elements of an Apéry set of S form an arithmetic sequence. We explicitly describe such numerical semigroups S and determine conditions for which the sets of gaps of these numerical semigroups are equidistributed modulo m.     

On the number of conjugacy classes of π-elements in finite groups

Let G be a finite group and π be a set of primes. Put ${d_{\pi}(G) = k_{\pi}(G)/|G|_{\pi}}$ , where ${k_{\pi}(G)}$ is the number of conjugacy classes of π-elements in G and |G| _π is the π-part of the order of G. In this paper we initiate the study of this invariant by showing that if ${d_{\pi}(G) > 5/8}$ then G possesses an abelian Hall π-subgroup, all Hall π-subgroups of G are conjugate, and every π-subgroup of G lies in some Hall π-subgroup of G. Furthermore, we have ${d_{\pi}(G) = 1}$ or ${d_{\pi}(G) = 2/3}$ . This extends and generalizes a result of W. H. Gustafson.     

Restricted partitions and q-Pell numbers

In this paper, we provide new combinatorial interpretations for the Pell numbers p _n in terms of finite set partitions. In particular, we identify six classes of partitions of size n, each avoiding a set of three classical patterns of length four, all of which have cardinality given by p _n . By restricting the statistic recording the number of inversions to one of these classes, and taking it jointly with the statistic recording the number of blocks, we obtain a new polynomial generalization of p _n . Similar considerations using the comajor index statistic yields a further generalization of the q-Pell number studied by Santos and Sills.     

Permutations and β-shifts

Given a real number β>1, a permutation π of length n is realized by the β-shift if there is some x∈[0,1] such that the relative order of the sequence x,f(x),…,fn−1(x), where f(x) is the fractional part of βx, is the same as that of the entries of π. Widely studied from such diverse fields as number theory and automata theory, β-shifts are prototypical examples of one-dimensional chaotic dynamical systems. When β is an integer, permutations realized by shifts were studied in Elizalde (2009) [5]. In this paper we generalize some of the results to arbitrary β-shifts. We describe a method to compute, for any given permutation π, the smallest β such that π is realized by the β-shift. We also give a way to determine the length of the shortest forbidden (i.e., not realized) pattern of an arbitrary β-shift.     

A branching particle system approximation for nonlinear stochastic filtering

The optimal filter π = {π t,t ∈ [0,T ]} of a stochastic signal is approximated by a sequence {π n t } of measure-valued processes defined by branching particle systems in a random environment(given by the observation process).The location and weight of each particle are governed by stochastic differential equations driven by the observation process,which is common for all particles,as well as by an individual Brownian motion,which applies to this specific particle only.The branching mechanism of each particle depends on the observation process and the path of this particle itself during its short lifetime δ = n 2α,where n is the number of initial particles and α is a fixed parameter to be optimized.As n →∞,we prove the convergence of π n t to π t uniformly for t ∈ [0,T ].Compared with the available results in the literature,the main contribution of this article is that the approximation is free of any stochastic integral which makes the numerical implementation readily available.