学术报告通知
题目：
Human-verifiable proofs in the theory of word-representable graphs
报告人：
Sergey Kitaev (University of Strathclyde)
时间：
4月2日 下午3：00
地点：
博B108
摘要：
A graph is word-representable if it can be encoded by a word so that adjacency corresponds to alternation of letters; equivalently, such graphs admit semi-transitive orientations. While word-representability can be certified efficiently, proving that a graph is not word-representable is often difficult, as it may require ruling out all possible orientations. In this talk, we present recently developed methods for the automated search of human-verifiable proofs of non-word-representability. These methods produce short, checkable proofs using publicly available software, and we illustrate their effectiveness on the Shrikhande and Clebsch graphs.
报告人简介：
Sergey Kitaev，英国思克莱德大学教授，现任《Journal of Combinatorial Theory, Series A》、《Proceedings of the Edinburgh Mathematical Society》编委。他在哥德堡大学获得数学博士学位，师从Einar Steingrimsson。Kitaev教授的研究兴趣涉及组合学和图论的各个方面，已在《Journal of Combinatorial Theory, Series A》等期刊发表140余篇论文，并著有专著《Patterns in Permutations and Words》、《Words and Graphs》。
目的地搜索