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

Prelegent(ci)

Wojciech Przybyszewski

Afiliacja

MIM UW

Termin

20 kwietnia 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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

---