Let S denote the set of all finite permutations, considered as rearrangements of {1,...,n}, n=1,2,3,... Pattern involvement is a partial order on S, and it arises naturally in the analysis of sorting mechanisms, such as stacks and queues, and also from a model-theoretic viewpoint, when permutations are considered as relational structures with two linear orders. Of particular interest are downward closed sets under this ordering, usually called pattern classes. Such classes can be defined by specifying minimal forbidden permutations; we write Av(pi_1,pi_2,...) to denote the pattern class consisting of all permutations avoiding pi_1,pi_2,... Thus, for instance: - Av(21) consists of all increasing permutations 12...n, n in N; - Av(321) consists of all permutations with no descending subsequences of length 3; - Av(231) consists of all permutations that can be sorted by a stack. In this talk I will discuss the subclasses contained in Av(321) and Av(231). I will set the scene by outlining some superficial similarities: e.g. they are both enumerated by the Catalan numbers. Then I will point out some radical differences: e.g. Av(231) is well quasi ordered (it has no infinite antichains), while Av(321) is not. Most of the talk will be devoted to an explication of some less obvious, but deeper, similarities between the subclasses, to do with their enumeration sequences. The notion of well quasi order and encodings by regular languages play a major background role in this development. The new results concerning the subclasses of Av(321) are a joint work with M. Albert, R. Brignall and V. Vatter.
On classes of permutations avoiding 231 or 321
Feb. 13, 2018 2pm (MATH 220)
Nik Ruskuc (St Andrews)
X
A subdirect product of algebras A_1,...,A_n of the same type is any subalgebra C of their direct product A_1 x... x A_n which projects onto each A_i. In my ongoing work with Peter Mayr, we are considering the conditions under which such a subdirect product is: (a) finitely generated; (b) finitely presented. In this lecture I will give an introduction into this problem, by comparing subdirect products with what known for direct products. I will then present a construction of fiber products which completely characterises subdirect products of two factors in congruence permutable varieties (Fleischer's Lemma), and revisit the basic questions in this context. I will conclude with a summary of our main results.
Finiteness properties of subdirect products Sponsored by the Meyer Fund
Number Theory Lab Meeting