Home » 2013 » November

Monthly Archives: November 2013

Everything you wanted to know about symmetric polynomials, part III

Let’s talk about Schur polynomials. These were defined as:

\displaystyle{ s_\lambda = \sum_{T \in SSYT(\lambda)} x^{w(T)}.  }

Here \lambda is a partition, T is a semistandard Young tableau of shape \lambda, and x^{w(T)} is the monomial x_1^{\mu_1} \cdots x_n^{\mu_n}, where \mu is the weight of T (so \mu_i is the number of i‘s in T.)

First things first: it’s not obvious from the definition that these are symmetric!

Claim. The Schur polynomials are symmetric polynomials.

Proof. It suffices to show that there as many tableaux of weight \mu as there are of weight s_i \cdot \mu, where s_i is the transposition that swaps i and i+1. We’ll exhibit a bijection between these two sets, SSYT(\lambda,\mu) and SSYT(\lambda,s_i\cdot\mu) directly, called the Bender-Knuth involution.

(Personal note: this was one of the first proofs I ever learned in algebraic combinatorics, and remains one of my favourites, for its elegant use of the defining properties of SSYTs.)

(more…)

Everything you wanted to know about symmetric polynomials, part II

Last post, I introduced the ring \Lambda of symmetric polynomials in infinitely-many variables. Its elements are infinite sums of monomials (of bounded degree), symmetric in all the variables. I also defined the five most common bases for it: the monomial, elementary, (complete) homogeneous, power and Schur polynomials, m,e,h,p,s for short. All of them are indexed by partitions \lambda, and in each case the basis element is homogeneous of (total) degree |\lambda|.

Now, I’m going to prove that each of these is a basis for \Lambda.

(more…)

Everything you wanted to know about symmetric polynomials, part I

A symmetric polynomial f(x_1, \ldots, x_n) is a polynomial which doesn’t change under permutations of the variables. So, f(x,y,z) = f(x,z,y) = f(y,z,x) and so on. Because of the simplicity of the definition (and the ubiquity of polynomials in math), symmetric polynomials show up in a variety of fields: algebraic geometry and combinatorics, Galois theory, birational geometry and intersection theory, linear algebra, and representation theory — to say the least.

Perhaps the most well-known are the elementary symmetric polynomials e_k:

\displaystyle{ e_k = \sum (\text{ all squarefree monomials of total degree k }) }

(more…)

The RSK Correspondence

This is another tableau combinatorics post. The Robinson-Schensted-Knuth correspondence, or RSK for short, is another important theorem and algorithm in tableau combinatorics; I’ll discuss it here, though I won’t try to motivate it. For now, it will be something of a curiosity. As always, my reference is Fulton’s book Young Tableaux.

(more…)

Knuth Equivalence and Tableau Products

I found (and still find) the ideas and algorithms around Young Tableaux to be fairly unintuitive: jeux de taquin (JDT), Knuth equivalence and rectification; the RSK correspondence; the Littlewood-Richardson rule(s); promotion and evacuation.

In this post, I want to state (without proof) the basic ideas and facts surrounding the first algorithm above, JDT, and its connection to Knuth equivalence. The reference I am using is Fulton’s Young Tableaux textbook, which covers almost all of the above-mentioned algorithms. For this post, I’m essentially restating section 3.1, and parts of sections 1 and 2.

Let’s begin.

(more…)

Hello, world

For now, the main purpose of this blog is for me to have somewhere to sound out my thoughts as I study for my prelim exam. Perhaps it’ll last longer than that. (Certainly, I’m the kind of mathematician who especially likes talking about math with others. I don’t know whether that will translate to the blogging medium.)