日時: 毎週金曜日 15:00 ~
Date: Fridays 15:00~
開催場所: 東北大学理学研究科合同A棟 801号室 (場合によりZoom等で実施)
Venue: Tohoku university, Science department, Complex A, 801 (and online via zoom)
過去のセミナー情報については，こちらよりご覧ください
For information of past seminars: here
研究活動の記録については，こちらよりご覧ください
For information of research activities: here
今後のセミナー情報(Future schedule)
Title: Forbidden Induced Subgraphs and the Los Tarski Theorem
Venue: Complex A 801 and online(zoom)
Time: 15:00-
Abstract: Let C be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Los-Tarski Theorem from classical model theory implies that
(*) C is definable in first-order logic (FO) if and only if C has a finite set of forbidden induced subgraphs.
In this talk I will discuss some applications of (*) and its limitations. Among others:
- Any class of graphs of bounded tree-depth can be characterized by a finite set of forbidden subgraphs. Our proof differs from the original proof of [Ding, 1992] by circumventing the machinery of well-quasi ordering.
- The forbidden subgraphs can be arbitrarily complex (e.g., not computable) compared to the FO-sentence defining the class C.
This is joint work with Joerg Flum.