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.

Posted in events | Tagged , , , , | 1 Comment

Don’t mind Cameron

I’ve used a line from Richard Brautigan’s novel The Hawkline Monster: A Gothic Western as a tagline for many years now.

I haven’t re-read the book for a while, but on my recommendation, Scott Harper read it, and sent me an email with the title of this post as subject line, with this quote from the book:

“Don’t mind Cameron,” Greer said. “He just likes to count things. You’ll get used to it.”

Posted in Uncategorized | Tagged , | Leave a comment

Hermann Zapf

I learned from today’s Guardian that the type designer Hermann Zapf died last week at the age of 96.

The journalist focussed his article on Zapf’s revolutionary Dingbats font, but for me and other TeX users, his great contribution was the Palatino font, which we can easily use in LaTeX with the mathpazo package. This contains mathematical symbols matched to the text font, including elegant blackboard bold letters. I always use this font in Beamer slides now.

I don’t know how close his connection with Don Knuth and the TeX project was. I am sure I have seen him described in something by Knuth as a “grand wizard of fonts”.

So here, in his memory, is the story of the quick brown fox and the lazy dog in Palatino.

Posted in typography | Tagged , , , | Leave a comment

Cayley digraphs and fractals

I have been thinking recently about the generation graph of a finite group: this is the graph whose vertices are the group elements, two vertices joined by an edge if together they generate the group. Of course the graph is not very interesting unless the group can actually be generated by two elements …

Talking to the summer research students today, an interesting thought struck me. Let G be a group which can be generated by two elements. Then there is a natural connection between the generation graph for G and the Cayley digraphs for G with out-degree 2:

A pair x,y of group elements form an edge in the generation graph if and only if the Cayley digraph Cay(G,{x,y}) is connected.

Does this remind you of anything? In the words of Wikipedia,

A point is in the Mandelbrot set exactly when the corresponding Julia set is connected.

So the relation between edges of the generation graph and divalent Cayley digraphs is “the same” as the relationship between the Mandelbrot set and Julia sets.

Is there any more to it?

Incidentally, as you would expect, the Wikipedia article has some nice pictures!

Posted in exposition | Tagged , , , , | Leave a comment

Jack Edmonds’ London lectures

Course material associated with Jack Edmonds’ lectures can be found here.

There is an announcement here. For the first course, 16-19 June at Queen Mary, University of London, see Alex Fink’s web page here, and for the LTCC intensive, 22-23 June at UCL, see the LTCC page here.

Posted in events | Tagged , , , , , | 2 Comments

Dodgy data

At the beginning of the year, my h-index on Google Scholar was 45.

This is not going to be a rant about the vacuity of the h-index, or only indirectly. I don’t spend time working this out; Google Scholar does it for you, so it is right up there at the top of the front page.

Last month it was up to 47. Out of curiosity, I checked my papers with citations in the middle 40s, and indeed, several of them had had a few recent citations.

Today I looked again, and the number was up to 49. But a brief check showed that this was entirely bogus. Somewhere along the line, Google Scholar had dumped a whole lot of papers with authors sharing my surname and initial into my list. I went through deleting them (a somewhat tedious business) until I got bored; this brought the h-index back down to 47.

But on the way through, I was disturbed by the dodginess of the data, even in supposedly genuine citations. Various papers have been split into multiple copies (probably because of small errors by the authors citing them); sometimes having a paper in a journal gets me credited as an author of the entire journal issue; and as to the citations themselves, they are as unreliable as you might expect.

Probably this process can be controlled. If you are about to apply for a job or promotion, how nice it would be if you could artificially inflate your h-index. I know that, at least in the recent past, hiring committees in some subjects (not mathematics, as far as I am aware) are influenced by h-index. But perhaps they have moved on to altmetrics now, and the problem has gone away.

Posted in Uncategorized | Tagged , | Leave a comment


A beautiful formula

This month, a beautiful formula on an old door panel in Prague. (It may not be very legible in this low-resolution copy.) The formula is for l(Sn), the length of the longest chain of subgroups in the symmetric group Sn. The formula is, you increase n by 50%, rounding up if necessary; subtract the number of ones in the base 2 representation of n, and subtract another 1. Beautiful, because unexpected (I would not have anticipated a general formula for this number) and surprising (the occurrence of the base 2 representation of n hints at the method of constructing such chains, by writing n in base 2 and descending to a direct product of symmetric groups of 2-power degree).

I found this in the early 1980s; Ron Solomon and Alex Turull found it independently, and we joined forces to publish it.

A generalisation to semigroups is discussed here.

Posted in exposition | Tagged , | 1 Comment