# Definability of neighborhoods in graphs of bounded twin-width and its consequences

- Speaker(s)
**Wojciech Przybyszewski**- Affiliation
- MIM UW
- Date
- April 20, 2022, 2:15 p.m.
- Room
- room 5050
- Seminar
- Seminar Automata Theory

During the talk, we will study set systems formed by neighborhoods in graphs of bounded twin-width. In particular, we will show how, for a given graph from a class of graphs of bounded twin-width, to efficiently encode the neighborhood of a vertex in a given set of vertices A of the graph. For the encoding we will use only a constant number of vertices from A. The obtained encoding can be decoded using FO formulas. This will prove that the edge relation in graphs of bounded twin-width, seen as first-order structures, admits a definable distal cell decomposition, which is a notion from model theory. From this fact we will derive that we can apply to such classes strong combinatorial tools based on the Distal cutting lemma and the Distal regularity lemma (a stronger version of Szemerédi regularity lemma).