报告名称：Human verifiable proofs in the theory of word-representable graphs

主讲人：Sergey Kitaev 教授

邀请人：陈宗青 讲师

时间：2022年10月26日   16:00

地点：腾讯会议（ID：682 249 898）

主办单位：十大网投正规信誉官网

报告摘要

图的词表示是图的一种线性表示，用词中的交错点对与图的边的对应关系建立的图与词之间的映射。并非所有的图都存在词表示，存在词表示的图被称为是可词表示的。判别图的词表示性是一个 NP 完全问题，在文献中出现了各种特定图或图族的词表示性证明，而且这些证明都是基于图的半传递定向刻画的。但对于随机选择的图，人们应该证明它们是否是半传递的？即使计算机会打印出所有2^#edges个定向并指出每个方向是否是半传递的，这样的证明基本上是人类无法检查的。

在本报告中，我们设计了用于自动搜索图形非词可表示性的人类可验证的证明方法。作为概念验证，我们提供了由我们公开的软件自动生成的非单词可表示性的“简短”证明，即 Shrikhande 图在 16 个顶点和 48 个边（9条判定条件）和 16 个顶点和 40 条边上的 Clebsch 图（33条判定条件）。

专家简介

Sergey Kitaev，英国思克莱德大学理学院副院长、教授。2003年博士毕业于瑞典哥德堡大学。主要研究组合计数问题，完成《Patterns in permutations and words》《Words and graphs》两本著作，文章157篇，发表在J. Combin. Theory Ser. A，Adv in Appl. Math., European J. Combin.等杂志。先后主持冰岛和英国国家基金委项目，并多次被邀请在重要组合数学会议上做大会报告。