Lovász meets Łoś and Tarski

Speaker(s)

Yijia Chen

Affiliation

Shanghai Jiao Tong University

Language of the talk

English

Date

Feb. 25, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Lovász meets Łoś and Tarski

Seminar

Seminar Automata Theory

---

A classical result of Lovász 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 and independent of G. In fact, this
result can be recast as a special case of the Łoś-Tarski Theorem from
classical model theory. That is, for a class C of finite and infinite
graphs that is closed under induced subgraphs,

(*) 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 induced subgraphs can be arbitrarily complex compared
to the FO-sentence defining the class C.

This is joint work with Jörg Flum.

---