On November 19, 2020, Yijia Chen (陈翌佳) from Fudan University spoke at the Virtual Discrete Math Colloquium on the shrub-depth of graph classes. The title of his talk is “Graphs of bounded shrub-depth, through a logic lens“.

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

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