I never promised to write something every day …
Anyway, the conference is now over. The LMS conference wi-fi was just not up to the demands of a conference big enough to fill the Hardy room, so lots of on-line things didn’t get done.
So, briefly, a few highlights.
On Wednesday, Vince Vatter gave an expository talk on Joseph Fox’s proof. I will try to describe the background.
One of the earliest concerns of researchers in permutation patterns was: how many permutations lie in a given downward-closed class? Such classes may be defined by excluded sub-patterns, by constructions from smaller classes, or as the output of some computational device. (One of the earliest results, by Don Knuth, was that permutations which can be generated by a stack with optional bypass are counted by the Catalan numbers.) One of the first big targets was the Stanley–Wilf conjecture, stating that the class defined by a single excluded pattern contains exponentially many permutations on n points: that is, if an is the number of such permutations, then (an)1/n tends to a finite limit c as n tends to infinity. Since 2002, this conjecture is the Marcus–Tardos theorem.
Attention then turned to the question: what are the possible growth constants c, if the forbidden pattern has length k? We don’t even know the complete answer for k = 4, as I reported here. But on the basis of very limited information, a couple of conjectures were made suggesting that there was an upper bound which was quadratic in k. This was refuted by Jacob Fox, who showed that there are patterns of length k for which the growth constant is fractional exponential in k and, moreover, that for large k almost every pattern has growth rate at least this large.
Vince gave an exposition of the proof, which involves a number of original ideas, including a very clever encoding of permutations as matrices, a notion of interval minor order, Cibulka’s theorem, and a random construction.
Mike Albert gave a talk with the subtitle “How I learned to stop worrying and love the machine”, on a very general approach to generating permutations by a “computational” device. Really it is a construction which takes a permutation pattern class and produces a larger one. In Knuth’s example mentioned above, a stack can by itself produce only the reversing permutation, but the addition of a bypass (so that we may move things directly from input to output) allows all 231-forbidding permuations as output. This gives a very interesting perspective on Wilf-equivalence (two permutation classes are Wilf-equivalent if their enumeration functions are equal) and explains the ubiquity of Catalan and Schröder numbers in counting permutation classes, for example.
The conference dinner on Thursday was held on a boat moored on the Thames near the Hungerford Bridge.
Factoid from the last day: From Cyril Banderier’s talk, I picked up the following. The number of permutations of {1,…,n} with k left-to-right maxima is equal to the number with k cycles (and so are counted by the Stirling numbers of the first kind). The simple bijection, due to Foata, I believe, from cycles to lr-maxima works like this. Take the permutation in cycle form. Start each cycle from its greatest element. Then order the cycles so that these greatest elements increase. Then simply delete the brackets and regard the sequence of numbers as a permutation. The largest points in the cycles are the lr-maxima. Conversely, given a permutation in passive form with the lr-maxima marked, cut before these and insert brackets )( at these points, with ( at the start and ) at the end.
Cyril explained that permutations with at most d non-lr-maxima are precisely those which can be produced from the identity with d “jumps”, where each jump takes one element and moves it any number of places to the right, moving the intervening elements back one place. This process is related to a model for gene mutation by transpositions.
Slides of the talks will be put on the conference web page. Mine are already posted in my own list of talks given.
So thanks to Robert Brignall and David Bevan for putting on a very nice conference, which just fitted into the Hardy Room at De Morgan House. Especially to Robert, who had to miss part of the conference because his son was born during the meeting!
Peter Cameron's Blog 