Trace cocharacters and the Kronecker products of Schur functions

It follows from the theory of trace identities developed by Procesi and Razmyslov that the trace cocharacters arising from the trace identities of the algebra M_r(F) of r×r matrices over a field F of characteristic zero are given by TC_r,n=∑_λΛr(n)χ^λχ^λ where χ^λχ^λ denotes the Kronecker product of the irreducible characters of the symmetric group associated with the partition λ with itself and Λ_r(n) denotes the set of partitions of n with r or fewer parts, i.e. the set of partitions λ=(λ₁λ_k) with kr. We study the behavior of the sequence of trace cocharacters TC_r,n. In particular, we study the behavior of the coefficient of χ^(ν,n−m) in TC_r,n as a function of n where ν=(ν₁ν_k) is some fixed partition of m and n−mν_k. Our main result shows that such coefficients always grow as a polynomial in n of degree r−1.     

Large-Scale Regularities of Lattice Embeddings of Posets

Let N denote the set of natural numbers and let P =(N ^k , ) be a countably infinite poset on the k-dimensional lattice N ^k . Given x N ^k , we write max(x) (min(x)) for the maximum (minimum) coordinate of x. Let be the directed-incomparability graph of P which is defined to be the graph with vertex set equal to N ^k and edge set equal to the set of all (x, y) such that max(x) max(y) and x and y not comparable in P. For any subset D N ^k , we let P _D and _D denote the restrictions of P and to D. Points x N ^k with min(x) = 0 will be called boundary points. We define a geometrically natural notion of when a point is interior to P or relative to the lattice N ^k , and an analogous notion of monotone interior with respect to or _D . We wish to identify situations where most of these interior points are exposed to the boundary of the lattice or, in the case of monotone interior points, not concealed very much from the boundary. All of these ideas restrict to finite sublattices F ^k and/or infinite sublattices E ^k of N ^k . Our main result shows that for any poset P and any arbitarily large integer M > 0, there is an F E with F = M where, relative to the sublattices F ^k E ^k , the ideal situation of total exposure of interior points and very little concealment of monotone interior points must occur. Precisely, we prove that for any P =(N ^k , ) and any integer M > 0, there is an infinite E N and a finite D F ^k with F E and F = M such that (1) every interior vertex of P _{E k} or _{E k} is exposed and (2) there is a fixed set C E, C k ^k , such that every monotone-interior point of _D belonging to F ^k has its monotone concealment in the set C. In addition, we show that if P ¹ =(N ^k , ₁),..., P ^r =(N ^k , _r ) is any sequence of posets, then we can find E,D, and F so that the properties (1) and (2) described above hold simultaneously for each P ⁱ . We note that the main point of (2) is that the bound k ^k depends only on the dimension of the lattice and not on the poset P. Statement (1) is derived from classical Ramsey theory while (2) is derived from a recent powerful extension of Ramsey theory due to H. Friedman and shown by Friedman to be independent of ZFC, the usual axioms of set theory. The fact that our result is proved as a corollary to a combinatorial theorem that is known to be independent of the usual axioms of mathematics does not, of course, mean that it cannot be proved using ZFC (we just couldn"t find such a proof). This puts our geometrically natural combinatorial result in a somewhat unusual position with regard to the axioms of mathematics.     

A combinatorial rule for the schur function expansion of the Plethysm S(1a,b)[Pk]

We present a simple combinatorial rule to expand the plethysm P_n[S(1^a,b)](x) of a power summetric function P_n(x) and a Schur function of hook shapeS(1^a,b)(x), as a sum of Schur functions. The key ingredient of our proof is a correspondence between the circle diagrams, introduced by Chen, Garsia and Remmel [6] in their SXP algorithm to compute the Schur function expansion of P_n[S_λ], and certain special rim hook and transposed special rim hook tabloids which is of interest in its own right. As an application of our rule, we drive explicit formulas for the coefficient of any Schur function of hook shape in the Schur function expansion of a plethysm of any two Schur functions of hook shape.     

Symmetric Functions and Generating Functions for Descents and Major Indices in Compositions

In [18], Mendes and Remmel showed how Gessel’s generating function for the distributions of the number of descents, the major index, and the number of inversions of permutations in the symmetric group could be derived by applying a ring homomorphism defined on the ring of symmetric functions to a simple symmetric function identity. We show how similar methods may be used to prove analogues of that generating function for compositions.     

The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

Permutations and words counted by consecutive patterns

Generating functions which count occurrences of consecutive sequences in a permutation or a word which matches a given pattern are studied by exploiting the combinatorics associated with symmetric functions. Our theorems take the generating function for the number of permutations which do not contain a certain pattern and give generating functions refining permutations by the both the total number of pattern matches and the number of non-overlapping pattern matches. Our methods allow us to give new proofs of several previously recorded results on this topic as well as to prove new extensions and new q-analogues of such results.     

Rook-by-rook rook theory: Bijective proofs of rook and hit equivalences

Suppose μ and ν are integer partitions of n, and N>n. It is well known that the Ferrers boards associated to μ and ν are rook-equivalent iff the multisets [μ_i+i:1iN] and [ν_i+i:1iN] are equal. We use the Garsia–Milne involution principle to produce a bijective proof of this theorem in which non-attacking rook placements for μ are explicitly matched with corresponding placements for ν. One byproduct is a direct combinatorial proof that the matrix of Stirling numbers of the first kind is the inverse of the matrix of Stirling numbers of the second kind. We also prove q-analogues and p,q-analogues of these results. We also use the Garsia–Milne involution principle to show that for any two rook boards B and B^′, if B and B^′ are bijectively rook-equivalent, then B and B^′ are bijectively hit-equivalent.     

The spread of a partial order

The deficiency of a partial order is the number of incomparable pairs. Another measure, the spread of a partial order is defined and its relation to the deficiency is established. In certain cases which arise naturally in the analysis of various sorting and selection algorithms where the partial order is only implicitly defined, the spread of the partial order is easier to estimate directly and provides a convenient way to estimate the deficiency.Partially supported by NSF Grant DCR-85-05053.Partially supported by NSF Grant DMS-85-05004.