Combinatorics and Discrete Mathematics Seminar: Labeled well-quasi-order for permutation classes

Speaker: Robert Brignall (The Open University)

Title: Labeled well-quasi-order for permutation classes

Abstract:

In the study of (finite) combinatorial structures equipped with a quasi ordering (for example, graphs with the induced subgraph ordering), the notion that a class of structures is “well-quasi-ordered” (wqo) equates to the absence of an infinite antichain in the class. Put another way, in a wqo class every infinite set of objects contains a pair, one of which precedes the other in the ordering. The combinatorial structure of choice for this talk is the permutation, equipped with the containment (=induced substructure) ordering.

The notion of labeled well-quasi-order (commonly abbreviated to lwqo) is a significant strengthening of wqo, and dates back at least to Kruskal’s tree theorem in 1960, although it has received little attention in the realm of permutations before now. As the name suggests, it concerns combinatorial structures whose ground sets (for example, the vertices of a graph or the entries of a permutation) have been labeled by some ordered set L of labels, and considers the question of wqo on these labeled structures (under a refined ordering).

In this talk, I will describe a recent programme to initiate the study of lwqo in the context of permutation classes. As well as being able to strengthen many earlier results about wqo to lwqo, it turns out that much more can be said about permutation classes that are lwqo over those that are simply wqo. Of particular note is that a permutation class is lwqo if and only if the corresponding class of permutation graphs is lwqo: the analogous statement for wqo remains open.

This is based on joint work with Vince Vatter.