Permutation patterns, day 1

Today is the first day of Permutation Patterns 15, at the London Mathematical Society headquarters in De Morgan House.

Registration began at 8.30. I don’t like using the Underground at that time of day if it can be avoided; but London is a walkable city. I set off at 7.30. Through the East End and into the City, gently up Ludgate Hill, where St Paul preached (according to legend) and Christopher Wren’s cathedral dominates (or at least, it did until the poisonous mushrooms of Paternoster Square and – even worse – One New Change sprang up); across the valley of the Fleet, past Gresham House (no connection with Gresham College apart from having the same founder, Sir Thomas Gresham), to the area that is trying to re-brand itself as Midtown (well, Holborn is three stops from Bank and three from Bond Street), and up to Russell Square.


On the way, I bought a Big Issue, which had a feature on Jordan Ellenberg, defending the thesis that mathematics has an impact on many unexpected things in life, and answering readers’ questions. Also passed Penderel’s Oak, the place where Anatoly Vershik explained to me his invariant measure concentrated on the generic triangle-free graph.

The subject of the conference, Permutation Patterns, is small enough and far enough from the mainstream that the organisers start the program with a nice little five-page survey giving the basic definitions and language, and references to the books by Miklós Bóna and Sergey Kitaev. This has the added advantage that people (especially incomers like me) don’t have to waste time going over the basics – except that I need to spend a bit of time on this because I will be putting a different slant on them.

Among many nice talks, let me mention the talk by Marie-Louise Bruner. It is conjectured that, for fixed n, the number of permutations whose largest increasing subsequence has k terms is log-concave as a function of k. She and Miklós Bóna have conjectured that the same is true if we restrict out attention to involutions (permutations whose square is the identity). The second conjecture implies the first, and she gave us the proof. The key idea is the Robinson–Schensted correspondence, a bijection between permutations of {1,…,n} and pairs of standard Young tableaux of the same shape with n cells. (I will describe this in detail one day, I promise …) This correspondence has the properties

  • the length of the longest increasing subsequence of the permutation is equal to the length of the first row of the corresponding Young diagram (the shape of the two tableaux);
  • if a permutation π corresponds to a pair (S,T) of tableaux, then the inverse of π corresponds to (T,S); so in particular, involutions correspond to single tableaux.

I won’t give the argument in detail, but it is a clean derivation from these two facts.

Now this result specialises to any subclass of permutations which can be recognised by a condition on the corresponding shapes. For example, 321-avoiding permutations correspond to (at most) two-rowed diagrams, so the proof can be restricted to this class. Indeed, they have a proof of the conjectures for this class.

So there is a nice general question here. Which permutation pattern classes are defined by choosing a subset of the possible Young diagrams and taking all the permutations corresponding to two tableaux of one of these shapes?

Finally, factoid of the day. The left-to-right maxima of a permutation are the positions where the value of the permutation is greater than any previous values. Call two permutations equivalent if the positions and values of the left-to-right maxima agree. How many equivalence classes? The answer is given by the Catalan numbers. This is because we can take a canonical equivalence class representative by putting the undetermined elements in increasing order; the canonical permutation contains no occurrence of 321, and any 321-avoiding permutation arises in this way. It is well known (in this community) that the 321-avoiding permutations are enumerated by the Catalan numbers.

This last fact I’m sure has many proofs, and I am also sure that what follows isn’t new, but I like it. We use the fact that the Catalan numbers count standard Young tableaux with two rows of length n. (This is a translation of the fact that they solve the ballot problem, or count Dyck paths from (0,0) to (2n,0).) Also, the dual of a fact I mentioned above, a permutation is 321-avoiding if and only if the corresponding shape (under the Robinson–Schensted correspondence) has (at most) two rows.

So we have to show that pairs of SYT with two-rowed diagram having n cells are equinumerous with SYT with diagram a 2×n rectangle.

Let (S,T) be such a pair of SYT. In T, replace entry x with 2n+1−x, and then reverse the order of rows and columns; then this shape fits onto the end of S to produce a 2×n SYT. The procedure can be reversed; given a 2×n tableau, the entries up to n form the tableau S, and the remaining entries with the transformations above applied form the tableau T.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events and tagged , , , , . Bookmark the permalink.

One Response to Permutation patterns, day 1

  1. I tried to post the other day but somehow it didn’t work. You might find interesting our interpretation of the left to right maxima and pattern avoidance using finite semigroups

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s