Increasing subsequences, matrix loci, and Viennot shadows

Abstract: Let

m a t h b f x_{n i m e s n}

be an

n i m e s n

matrix of variables and let

m a t h b b F [m a t h b f x_{n i m e s n}]

be the polynomial ring in these variables over a field

m a t h b b F

. We study the ideal

I_{n} s u b s e t e q m a t h b b F [m a t h b f x_{n i m e s n}]

generated by all row and column variable sums and all products of two variables drawn from the same row or column. We show that the quotient

m a t h b b F [m a t h b f x_{n i m e s n}] / I_{n}

admits a standard monomial basis determined by Viennot's shadow line avatar of the Schensted correspondence. As a corollary, the Hilbert series of

m a t h b b F [m a t h b f x_{n i m e s n}] / I_{n}

is the generating function of permutations in

m a t h f r a k S_{n}

by the length of their longest increasing subsequence. Along the way, we describe a `shadow junta' basis of the vector space of

k

-local permutation statistics. We also calculate the structure of

m a t h b b F [m a t h b f x_{n i m e s n}] / I_{n}

as a graded

m a t h f r a k S_{n} i m e s m a t h f r a k S_{n}

-module.

This page was built for publication: Increasing subsequences, matrix loci, and Viennot shadows