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.
- 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.
- 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.