讨论类型：数学前沿论坛

主办：天津师范大学yh86银河国际官方网站

报告时间：2025年3月20日(周四)下午2点

报告地点：博理楼B区108

报告题目：Universal Cycles and Universal Words

报告人：Sergey Kitaev(思克莱德大学)

报告摘要:

   A universal word for a finite alphabet A and a positive integer n is a word over A such thatevery possible word of length n appears exactly once as a consecutive subword.For example,theword w=00110 is a universal word for the binary alphabet A={0,1}and n=2,since each of thewords 00,01,11,and 10 can be found exactly once in w.If we are allowed to read the wordcyclically,and it retains the same properties as a universal word,we obtain a universal cycle.Forexample,00110011 is a universal cycle for the alphabet A={0,1}and n=2.

   Universal cycles and words exist for any A and n,and this result dates back to at least C.P.Brown's1869 book on Sanskrit prosody.Interestingly,the concept of universal cycles/words has beenextended to other combinatorial structures (that can be encoded by words),such as permutations.

   In this presentation,I will introduce the necessary tools to prove the existence of universal cycles forwords,commonly known as de Bruijn sequences in the literature.I will also discuss how this resultcan be extended to the case of permutations.

   No prior knowledge is required.