Graphs of bounded shrub-depth, through a logic lens

Seminar
Speaker
Yijia Chen (Fudan University)
Date
17/01/2021 - 15:30 - 14:00Add to Calendar 2021-01-17 14:00:00 2021-01-17 15:30:00 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 the Łoś-Tarski Theorem in model theory, are applicable to graphs of bounded shrub-depth. This is joint work with Jörg Flum. Zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Zoom
Abstract

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 the Łoś-Tarski Theorem in model theory, are applicable to graphs of bounded shrub-depth.

This is joint work with Jörg Flum.

Last Updated Date : 12/01/2021