Logic seminar: Sandra Kiefer
| Dates: | 10 April 2024 |
|---|
| Times: | 15:15 - 16:30 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff, External researchers, Adults, Alumni, Current University students |
|---|
|
Title: Treelike decompositions for transductions of sparse graphs
Abstract:
Research on structural sparsity studies classes of graphs interpretable in sparse graphs using logics. The ultimate goal of this line of research is to lift algorithmic methods from the sparse setting to the more general one.
In this talk, I give an introduction to structural sparsity and present new decomposition theorems for graphs that can be transduced in first-order logic from classes of bounded expansion and from nowhere dense classes. In both cases, the decomposition takes the form of a single colored rooted tree of bounded depth where, in addition, there can be links between nodes that are not related in the tree. The constraint is that the structure formed by the tree and the links has to be sparse. The decomposition theorem for transductions of nowhere dense classes yields that they admit small low-shrubdepth covers. This solves an open problem posed by Gajarský et al. (ACM TOCL '20) and also by Bria?ski et al. (SIDMA '21).
Travel and Contact Information
Find event
Frank Adams 1 (and zoom, link in email)
Alan Turing Building
Manchester
