Generalized Jones traces and Kazhdan-Lusztig bases

We develop some applications of certain algebraic and combinatorial conditions on the elements of Coxeter groups, such as elementary proofs of the positivity of certain structure constants for the associated Kazhdan-Lusztig basis. We also explore some consequences of the existence of a Jones-type trace on the Hecke algebra of a Coxeter group, such as simple procedures for computing leading terms of certain Kazhdan-Lusztig polynomials.     

On the topology of components of some Springer fibers and their relation to Kazhdan-Lusztig theory

We describe the irreducible components of Springer fibers for hook and two-row nilpotent elements of as iterated bundles of flag manifolds and Grassmannians. We then relate the topology (in particular, the intersection homology Poincaré polynomials) of the pairwise intersections of these components with the inner products of the Kazhdan-Lusztig basis elements of irreducible representations of the rational Iwahori-Hecke algebra of type A corresponding to the hook and two-row Young shapes.     

Restricted 123-avoiding Baxter permutations and the Padovan numbers

Baxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.     

Relations between the Clausen and Kazhdan-Lusztig representations of the symmetric group

We use Kazhdan-Lusztig polynomials and subspaces of the polynomial ring C[x_1,1,…,x_n,n] to give a new construction of the Kazhdan-Lusztig representations of S_n. This construction produces exactly the same modules as those which Clausen constructed using a different basis in [M. Clausen, Multivariate polynomials, standard tableaux, and representations of symmetric groups, J. Symbolic Comput. (11), 5-6 (1991) 483-522. Invariant-theoretic algorithms in geometry (Minneapolis, MN, 1987)], and does not employ the Kazhdan-Lusztig preorders. We show that the two resulting matrix representations are related by a unitriangular transition matrix. This provides a C[x_1,1,…,x_n,n]-analog of results due to Garsia and McLarnan, and McDonough and Pallikaros, who related the Kazhdan-Lusztig representations to Young’s natural representations.     

Permutation Diagrams, Fixed Points and Kazhdan-Lusztig R-Polynomials

In this paper, we give an algorithm for computing the Kazhdan-Lusztig R-polynomials in the symmetric group. The algorithm is described in terms of permutation diagrams. In particular we focus on how the computation of the polynomial is affected by certain fixed points. As a consequence of our methods, we obtain explicit formulas for the R-polynomials associated with some general classes of intervals, generalizing results of Brenti and Pagliacci. Received May 13, 2005     

Signed permutations and the four color theorem

Let σ₁,σ₂ be two permutations in the symmetric group S_n. Among the many sequences of elementary transpositions τ₁,…,τ_r transforming σ₁ into σ₂=τ_rτ₁σ₁, some of them may be signable, a property introduced in this paper. We show that the four color theorem in graph theory is equivalent to the statement that, for any n≥2 and any σ₁,σ₂S_n, there exists at least one signable sequence of elementary transpositions from σ₁ to σ₂. This algebraic reformulation rests on a former geometric one in terms of signed diagonal flips, together with a codification of the triangulations of a convex polygon on n+2 vertices by permutations in S_n.     

Temperley-Lieb Immanants

We use the Temperley-Lieb algebra to define a family of totally nonnegative polynomials of the form . The cone generated by these polynomials contains all totally nonnegative polynomials of the form , where, are matrix minors. We also give new conditions on the sets I,...,K′ which characterize differences of products of minors which are totally nonnegative. Received September 30, 2004     

Restricted even permutations and Chebyshev polynomials

We study generating functions for the number of even (odd) permutations on n letters avoiding 132 and an arbitrary permutation τ on k letters, or containing τ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.     

Quantum Schur superalgebras and Kazhdan-Lusztig combinatorics

We introduce the notion of quantum Schur (or q-Schur) superalgebras. These algebras share certain nice properties with q-Schur algebras such as the base change property, the existence of canonical Z[v,v⁻¹]-bases, the duality relation with Manin’s quantum matrix superalgebra A(m|n), and the bridging role between quantum enveloping superalgebras of gl(m|n) and the Hecke algebras of type A. We also construct a cellular -basis and determine its associated cells, called supercells, in terms of a Robinson-Schensted-Knuth supercorrespondence. In this way, we classify all irreducible representations over via supercell modules.     

Dyck paths and restricted permutations

This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and S_n(321) and S_n(231), respectively. We also discuss permutations in S_n avoiding two patterns, one of length 3 and the other of length k. These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers.     

Restricted colored permutations and Chebyshev polynomials

Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schröder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation.     

Partial vexillarity and bigrassmannian permutations

We define two closely related notions of degree for permutation patterns of type 2143. These give rise to classes of “m-vexillary elements” in the symmetric group. Using partitions, the Ehresmann–Bruhat partial order, and sets constructed from permutation inversions, we characterize the m-vexillary elements. We relate the maximal bigrassmannian permutations in the (Ehresmann–Bruhat) order ideal generated by any given m-vexillary element w to the maximal rectangles contained in the shape of w.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

The Jordan canonical form for a class of zero-one matrices

Let f:N→N be a function. Let A_n=(a_ij) be the n×n matrix defined by a_ij=1 if i=f(j) for some i and j and a_ij=0 otherwise. We describe the Jordan canonical form of the matrix A_n in terms of the directed graph for which A_n is the adjacency matrix. We discuss several examples including a connection with the Collatz 3n+1 conjecture.     

Equidimensionality of convolution morphisms and applications to saturation problems

Fix a split connected reductive group G over a field k, and a positive integer r. For any r-tuple of dominant coweights μi of G, we consider the restriction mμ_• of the r-fold convolution morphism of Mirkovic-Vilonen to the twisted product of affine Schubert varieties corresponding to μ_•. We show that if all the coweights μi are minuscule, then the fibers of mμ_• are equidimensional varieties, with dimension the largest allowed by the semi-smallness of mμ_•. We derive various consequences: the equivalence of the non-vanishing of Hecke and representation ring structure constants, and a saturation property for these structure constants, when the coweights μi are sums of minuscule coweights. This complements the saturation results of Knutson-Tao and Kapovich-Leeb-Millson. We give a new proof of the P-R-V conjecture in the “sums of minuscules” setting. Finally, we generalize and reprove a result of Spaltenstein pertaining to equidimensionality of certain partial Springer resolutions of the nilpotent cone for GLn.     

The number of harmonic frames of prime order

Harmonic frames of prime order are investigated. The primary focus is the enumeration of inequivalent harmonic frames, with the exact number given by a recursive formula. The key to this result is a one-to-one correspondence developed between inequivalent harmonic frames and the orbits of a particular set. Secondarily, the symmetry group of prime order harmonic frames is shown to contain a subgroup consisting of a diagonal matrix as well as a permutation matrix, each of which is dependent on the particular harmonic frame in question.     

On constructing new expansions of functions using linear operators

Let T,U be two linear operators mapped onto the function f such that U(T(f))=f, but T(U(f))≠f. In this paper, we first obtain the expansion of functions T(U(f)) and U(T(f)) in a general case. Then, we introduce four special examples of the derived expansions. First example is a combination of the Fourier trigonometric expansion with the Taylor expansion and the second example is a mixed combination of orthogonal polynomial expansions with respect to the defined linear operators T and U. In the third example, we apply the basic expansion U(T(f))=f(x) to explicitly compute some inverse integral transforms, particularly the inverse Laplace transform. And in the last example, a mixed combination of Taylor expansions is presented. A separate section is also allocated to discuss the convergence of the basic expansions T(U(f)) and U(T(f)).     

On the sum of Laplacian eigenvalues of graphs

Let k be a natural number and let G be a graph with at least k vertices. Brouwer conjectured that the sum of the k largest Laplacian eigenvalues of G is at most , where e(G) is the number of edges of G. We prove this conjecture for k=2. We also show that if G is a tree, then the sum of the k largest Laplacian eigenvalues of G is at most e(G)+2k-1.