## Permutation patterns, day 2

In Russell Square, just opposite De Morgan House, is the T. S. Eliot yew tree, planted by the Indian High Commissioner in 1996.

Yew trees appear in several places in Eliot’s work. But the one I find most evocative occurs in Section IV of “Burnt Norton“, the first of the Four Quartets:

Will …
Chill
Fingers of yew be curled
Down on us?

I think of the spreading yew trees of English churchyards, reaching out to cast their shade over the graves of parishioners over many centuries.

But the yew in Russell Square does not spread; its shape is more like a poplar:

Maybe we just have to wait a few centuries …

Meanwhile, at the conference:

Michael Albert pointed out to me that the question I asked in yesterday’s post, concerning permutation pattern classes defined by shapes of Young diagrams, has been answered in his paper Young classes of permutations in 2012. In fact there is even more egg on my face, since I am an honorary editor-in-chief of the journal, the Australasian Journal of Combinatorics, and indeed I was when the paper was published. Oh dear. I had better read the journal more carefully!

There have been some more splendid talks. You will not be surprised to learn that Bruce Sagan gave a lovely plenary talk, about the connection between permutation pattern classes and quasisymmetric functions: from a permutation pattern class he constructs a quasi-symmetric function. [A symmetric function is a formal power series in infinitely many variables with the property that, if we take any monomial in it and apply a bijective function to the variables occurring in it, the resulting monomial also occurs with the same coefficient: now a quasi-symmetric function is defined in the same way, but where the requirement is only for order-preserving injections, assuming that the variables are indexed by the natural numbers.] There are analogues of Schur functions, and interesting questions are: for which permutation classes is the corresponding function symmetric, or Schur positive (all coefficients in the Schur basis are non-negative), or multiplicity free (all coefficients 0 or 1)? Plenty of room in this playground, as he pointed out. He was followed by Yuval Roichman, who developed some of this further, though had to skip a discussion of characters because of lack of time.

A very nice talk by Erik Slivken kicked the day off. He looks at the shape of a random permutation chosen from a permutation pattern class. For classes defined by excluding permutations of order 3, the structure is remarkably tight, and he established a connection between the asymptotic shape and Brownian excursions. Not so surprising if you remember the connection between these classes and Dyck paths, but there is considerable subtlety. The Brownian excursion is not quite the limit of the typical Dyck path, although it turns out to be closely connected.

Factoid of the day: Let H be the infinite matrix with the natural numbers under the main diagonal (that is, (n+1,n) entry n) and zero elsewhere. Then the exponential of H is Pascal’s triangle, left-justified. This was attributed to Call and Vellman in 1993: is it really no older than that? Anders Claesson gave extensions in the incidence algebras of the posets of words, permutations and subsets (the form I gave is in the incidence algebra of a chain), where the analogue of binomial coefficients count occurrences of the smaller structure inside the larger one. Robin Chapman generalised further with a categorical interpretation: each of these classes is a presheaf over the category whose objects are the sets {1,…,n} and whose morphisms are increasing maps; then identities in the categorial algebra of this category immediately give similar identities in these presheaves.

Oddity of the week: the conference programme has been printed without any minus signs. (Think positively!) Off-putting at first, but when you realise that any space in a formula should be filled with a minus sign you can just write them in.