Permutation classes and infinite antichains


The event is taking part on the Tuesday, Oct 16th 2018 at 15:30
Theme/s: Pure Maths
Location of Event: Alan Turing, Room 306
This event is a: Public Seminar

Abstract: Given some suitably defined permutation class (or family of permutation classes), notable questions one might like answers to include: How many permutations of length n are there? What is the growth rate of the class? Is it finitely based? What do the permutations ‘look’ like? Although rather more vague than the others, the last question in that list – asking for a structural characterization – can underpin the other three. Here are some recent examples: (1) the drive by multiple authors to enumerate the ‘2 × 4’ classes, (2) bounding the growth rate of Av(1324), and (3) in the study of grid classes, ‘geometric’ ones are (among other nice properties) finitely based.

Here’s another question: Does the class contain infinite antichains? Unless you’re similarly-minded to me, it’s quite likely that this question wasn’t high on your list. Nevertheless, in the last 10 years several authors (not including me) have established that the existence of one particular infinite antichain, the ‘increasing oscillating antichain’, has a profound impact on the theory of permutation classes: It tells us that ê ≈ 2.206 is the smallest growth rate where there are uncountably many permutation classes, and below ê it helps to determine what the possible growth rates are; it also guarantees that any real number about ë ≈ 2.357 is the growth rate of some permutation class. (In fact, the underpinning ‘oscillation’
structure has been known to mathematical biologists at least since 1991 under the term ‘Gollan permutation’, as the unique (up to symmetry) hardest permutation to sort by reversals.)

With the aid of a variant of permutation containment called ‘labelled containment’, in this talk I will survey instances where the existence of — or (more often) lack of — infinite antichains in a permutation class interacts with these other questions. I will report on recent joint work with David Bevan and Nik Ruškuc in the study of monotone grid classes, where a result on classifying the infinite antichains also tells us that every ‘unicyclic’ monotone grid class must be finitely based.

Report an error on this page

External Speakers

Dr Robert Brignall, (Open University)