校园门户 校园邮箱 English
世界杯介绍师资队伍学科建设科学研究本科生教育研究生教育学生工作招生工作合作交流党建与思政人才招聘
  世界杯买球
 世界杯买球 
 学术会议 
 学术访问 
快速通道
 
相关链接
 
重师主页 科研系统 图书馆
教务系统 财务系统 OA系统
世界杯买球
当前位置: 首页 >> 合作交流 >> 学术交流 >> 世界杯买球 >> 正文
世界杯买球——Sergey Kitaev教授(英国思克莱德大学)
2022-10-25 16:06     (点击: )


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

主讲人:Sergey Kitaev 教授

邀请人:陈宗青 讲师

时间:20221026日   16:00

地点:腾讯会议(ID682 249 898

主办单位:2022卡塔尔世界杯买球·(中国)官方网站


报告摘要

图的词表示是图的一种线性表示,用词中的交错点对与图的边的对应关系建立的图与词之间的映射。并非所有的图都存在词表示,存在词表示的图被称为是可词表示的。判别图的词表示性是一个 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. AAdv in Appl. Math., European J. Combin.等杂志。先后主持冰岛和英国国家基金委项目,并多次被邀请在重要组合数学会议上做大会报告。

 

关闭窗口

2022卡塔尔世界杯官方投注平台  地址:重庆市沙坪坝区大学城中路37号 汇贤楼
电话:023-65362798  邮编:401331