Yijia Chen (陈翌佳), Graphs of bounded shrub-depth, through a logic lens

Shrub-depth is a graph invariant often considered as an extension
of tree-depth to dense graphs. In this talk I will explain our recent
proofs of two results about graphs of bounded shrub-depth.

  1. Every graph property definable in monadic-second order logic,
    e.g., 3-colorability, can be evaluated by Boolean circuits of constant
    depth and polynomial size, whose depth only depends on the
    shrub-depth of input graphs.
  2. Graphs of bounded shrub-depth can be characterized by
    a finite set of forbidden induced subgraphs [Ganian et al. 2015].

Central to the first result is the definability in first-order logic of
tree-models for graphs of bounded shrub-depth. For the second
result, we observe that shrub-depth can be easily generalized
to infinite graphs, and thus some classical tools, i.e., Craig’s
Interpolation and Łoś-Tarski Theorem, in model theory are
applicable to graphs of bounded shrub-depth.

This is joint work with Jörg Flum.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.