Building the hierarchy of graph classes

Thời gian: 09:00 đến 11:00 Ngày 31/05/2022

Địa điểm: Online

Báo cáo viên: Sang-il Oum (IBS Discrete Mathematics Group & KAIST)

Tóm tắt:

We will give a survey on the classification of graph classes in terms of the transductions in certain logic such as monadic second-order logic and first-order logic. We will discuss how a recent theorem of the speaker with O-joung Kwon, Rose McCarty, and Paul Wollan and an old theorem of the speaker with Bruno Courcelle solve cases of the problem of characterizing graph classes in terms of counting monadic second-order logic of the first kind.