逸仙逻辑讲坛第八期｜陈翌佳：Łoś and Tarski meet Lovász

第八期 逸仙逻辑讲坛

题目：Łoś and Tarski meet Lovász — Forbidden Induced Subgraphs and Preservation Theorem

主讲人：陈翌佳  上海交通大学教授

主持人：王   玮  太阳集团tcy8722教授

时   间：5月20日（周六）下午15:00

地   点：锡昌堂322室

主办方：太阳集团tcy8722逻辑与认知研究所

 主讲人简介

        陈翌佳，上海交通大学计算机科学与工程系教授。他在上海交通大学获得计算机科学博士学位，在弗赖堡大学获得数学博士学位。他主要从事计算机科学中的逻辑、计算复杂性和算法图论的工作。他在《Logic Methods in Computer Science》和《Theory of Computing Systems》的编委会任职。

 讲座摘要 

     A classical result of Lovasz states that a graph G contains a vertex cover of size at most k if and only if G does not contain some graphs H_1, \ldots, H_\ell as induced subgraphs, where H_1, \ldots, H_\ell are completely determined by k. In fact, this result can be recast as a special case of the Los-Tarski Theorem from classical model theory. In this talk I will discuss a few more such results from structural graph theory which can be shown by pure logic means. In addition, I will explain the limitation of such logic machinery. As a byproduct, we offer some explanations why computing forbidden induced subgraphs is very hard.