Speaker：Sergey Kitaev（University of Strathclyde，UK）

Time：2023-3-21, 14:30

Location：Conference Room 686 at the 6th floor of Shuli Building at Haiyun Campus

Abstract:

Permutation patterns is a popular area of research introduced in 1968, but with roots going to work of Leonhard Euler in 1749.

In this talk, I will present a brand-new notion of a singleton mesh pattern (SMP), which is a multidimensional mesh pattern of length 1. It turns out that avoidance of this pattern in arbitrary large multi-dimensional permutations can be characterised using an invariant of a pattern called its rank. This allows to determine avoidability for an SMP P efficiently, even though determining rank of P is an NP-complete problem. Moreover, using the notion of a minus-antipodal pattern, one can characterise SMPs which occur at most once in any d-dimensional permutation.

I will also discuss a number of enumerative results regarding the distributions of certain general projective, plus-antipodal, minus-antipodal and hyperplane SMPs.

This is joint work with Sergey Avgustinovich, Jeffrey Liese, Vladimir Potapov and Anna Taranenko.