报告题目：SEMI-TRANSITIVE GRAPHS
报告人：Sergey Kitaev 教授 英国思克莱德大学
报告时间：7月15日（周五）下午16：00-17：00
报告方式：腾讯会议ID：607 726 370 密码：22715
报告摘要：An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v_0 -> v_1 -> … -> v_k either there is no edge between v_0 and v_k, or v_i -> v_j is an edge for all 0 <= i < j <=k. Semi-transitive graphs generalize several important classes of graphs (such as 3-colorable, subcubic, circle and comparability graphs) and they are precisely the class of word-representable graphs studied extensively in the literature. Not all graphs are semi-transitive, and recognizing semi-transitivity is an NP-complete problem. In this talk, I will go over some basics of the theory of semi-transitive graphs, and will introduce several open problems/research directions.
报告人简介：Sergey Kitaev，英国思克莱德大学理学院副院长、教授。2003年博士毕业于瑞典哥德堡大学。主要研究组合计数问题，完成《Patterns in permutations and words》《Words and graphs》两本著作，文章157篇，发表在J. Combin. Theory Ser. A，Adv in Appl. Math., European J. Combin.等杂志。先后主持冰岛和英国国家基金委项目，并多次被邀请在重要组合数学会议上做大会报告。
