Speaker：Sergey Kitaev（University of Strathclyde，UK）

Time：2023-3-28, 10:00

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

Abstract:

A universal word  for a finite alphabet A and some positive integer n is a word over A such that every word of length n appears exactly once as a (consecutive) subword. It is well known and is easy to prove that universal words exist for any A and n. The notion of a universal word was extended to other combinatorial structures (admitting encoding by words).

Universal partial words are words that in addition to the letters from A may contain an arbitrary number of a special “joker” symbol, which can be substituted by any letter from A. The study of universal partial words was initiated by Chen, Kitaev, Mutze and Sun.

In my talk, I will discuss a number of existence and non-existence results related to universal partial words, and will discuss ways to shorten universal cycles and universal words for permutations.