Loading Events

« All Events


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

November 19 Thursday @ 4:30 PM - 5:30 PM KST


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.


November 19 Thursday
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:




O-joung Kwon (권오정)
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.