离散数学研究所系列学术报告
来源:系统管理员 发布时间:2025-05-19
报告题目1:Naturally labelled posets and a hierarchy related to interval orders
报告人:Sergey Kitaev教授,英国思克莱德大学
报告时间:2025年5月26日(周一)9:00-11:00
报告地点:20-200
报告摘要:A partially ordered set (poset) (P,<_P) is naturally labelled by numbers in {1,2,...,n} if x <_P y implies x<y. Naturally labelled posets are in one-to-one correspondence with certain lower triangular binary matrices called poset matrices. By restricting naturally labelled posets–such as considering (2+2)-free, k-free, (3+1)-free, N-free, and similar classes of posets–we obtain combinatorial objects that fit nicely into a hierarchy related to interval orders. This hierarchy includes, for example, Fishburn matrices, factorial posets, ascent sequences, pattern-avoiding permutations, and many other structures. In particular, it turns out that (2+2,3)-free naturally labelled posets are in one-to-one correspondence with permutations avoiding the vincular pattern 12-34. In my presentation, I will introduce these objects and discuss the hierarchy, along with open (embedding) problems. This is joint work with David Bevan and Gi-Sang Cheon.
报告题目2:Singleton mesh patterns in multidimensional permutations
报告人:Sergey Kitaev教授,英国思克莱德大学
报告时间:2025年5月27日(周二)9:00-11:00
报告地点:20-200
报告摘要:Permutation patterns is a popular area of research introduced in 1968, but with roots going to the 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 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.
报告题目3:What Makes a Bijection “Good”? A Case Study on Pattern-Avoiding Permutations
报告人:Sergey Kitaev教授,英国思克莱德大学
报告时间:2025年5月27日(周二)14:00-16:00
报告地点:20-212
报告摘要:A bijection is a one-to-one correspondence between two sets. Often, there is more than one way to construct a bijection between equinumerous sets - and if the sets are not very small and we do not require the bijections to be intelligible, there can be many. But what makes a bijection good? Should it be easy to describe? Or should it reveal deeper structural similarities between the sets? While the answer “it depends” is valid, much more can be said under certain assumptions in specific contexts. In this talk, I will explore this idea through a remarkable story in the theory of permutation patterns.
报告人简介:Sergey Kitaev,英国思克莱德大学理学院副院长、数学与统计学系教授。2003年博士毕业于瑞典哥德堡大学。主要研究组合数学、图论、代数、离散数学和形式语言理论等,完成《Patterns in permutations and words》和《Words and graphs》两本著作,多篇论文发表在J. Combin. Theory Ser. A,Adv in Appl. Math.,European J. Combin.等组合数学权威杂志上。目前担任Journal of Combinatorial Theory, Series A (JCTA)和Proceedings of the Edinburgh Mathematical Society (PEMS)杂志编委。