应学校邀请，英国思克莱德大学终身教授、思克莱德大学理学院科研副院长Sergey Kitaev来我校访问，并为我校师生作精彩报告，欢迎全校师生参加。

报告时间：2025年3月31日 9:00

报告地点：一校区电机楼30019会议室

报告题目：Automatically Generated Proofs for the Non-Existence of Certain Timetabling Solutions 

Abstract: 

Consider a scenario with n recurring tasks and requirements on the alternation of certain pairs of tasks, which captures typical situations in periodic timetabling where there are recurring precedence constraints. For example, the following five tasks may be involved in the operation of a given machine: 1) Initialize controller, 2) Drain excess fluid, 3) Obtain permission from supervisor, 4) Ignite motor, 5) Check oil level. Tasks 1 & 2, 2 & 3, 3 & 4, 4 & 5, and 5 & 1 are expected to alternate in all repetitions of the events. One possible task execution sequence that obeys these recurrence constraints is 3 → 1 → 2 → 5 → 1 → 4 → 3 → 5 → 4 → 2.

Another relevant scenario is the construction of a conveyor by placing several copies of n types of robots in a line and respecting a given set of requirements. In this case, apart from the first cycle, robot i cannot do its job before robot j has completed its task, and vice versa, for certain pairs (i,j), where 1≤i<j≤n.

Finally, another relevant scenario is the security patrol problem. Here, a security guard patrols a network of connected locations, with constraints determining the order in which some of the locations must be visited and preventing locations from being revisited before other parts of the network have been patrolled. Problems like these are of great importance in a range of applications, including manufacturing, rostering, surveillance, and defense. Finding ways to precisely characterize the key constraints and eliminate unnecessary searches amongst partial solutions that do not satisfy them would have a significant impact.

All of these scenarios can be abstracted by the notion of a word-representable graph, which can be represented in a certain way using alternations of letters in words. These graphs generalize several important and well-studied classes of graphs, and they can be characterized by semi-transitive orientations. Recognizing word-representability is an NP-complete problem, and the bottleneck in the theory of word-representable graphs lies in convincing someone that a graph is non-word-representable, keeping in mind that references to (even publicly available and user-friendly) software are not always welcome.

专家简介：

Sergey Kitaev是英国思克莱德大学教授，思克莱德大学理学院副院长，国际权威期刊《组合理论杂志A辑》和《爱丁堡数学会会刊》编委。

作为国际组合数学领域的领军学者，Kitaev 教授开创了单词可表示图理论的研究方向，并建立了广义排列模式的研究体系。他的研究成果被来自全球69个国家的696位学者引用，谷歌学术（Google Scholar）的总引用次数高达2628次。Kitaev 教授也是多个重要学术会议的创始人，曾担任第26届英国组合数学大会主席和第10届排列模式国际会议主席，并主导制定了该领域的研究议程。作为跨学科应用的先驱，他的理论成果在机器人调度、生物信息学、算法分析等多个领域得到应用，并与神经科学、理论物理等学科开展了交叉研究。

Kitaev 教授是国际数学评论权威平台《数学评论》的特聘审稿人，韩国成均馆大学组合数学系列会议的常任学术委员，以及法国国家科研署（ANR）、以色列科学基金会等12个国家科研项目的评审专家。他参与了2025年英国格拉斯哥组合数学研究生大会的主旨报告和2024年中国西安图论与组合数学国际研讨会的特邀报告，并在日本大学、加州大学圣地亚哥分校、圣安德鲁斯大学等15所世界知名高校进行过专题讲学。

Kitaev 教授获得了英国Leverhulme信托基金的研究奖金、冰岛科学基金会的卓越计划资助，以及西班牙马德里大学“阿贝尔杰出讲席教授”荣誉。