Lovász meets Łoś and Tarski

Prelegent(ci)

Yijia Chen

Afiliacja

Shanghai Jiao Tong University

Język referatu

angielski

Termin

25 lutego 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Lovász meets Łoś and Tarski

Seminarium

Seminarium „Teoria automatów”

---

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.

---