Flip-separability

Speaker(s)

Wojciech Przybyszewski

Affiliation

University of Warsaw

Language of the talk

English

Date

May 14, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Flip-separability

Seminar

Seminar Automata Theory

---

Nešetřil and Ossona de Mendez proved that for every nowhere dense graph class C, integer r, and ε > 0 there is some integer k with the following property: For every n-vertex graph G in C there is a set S consisting of at most k vertices of G such that every ball of radius r in G - S contains at most ε · n vertices. We generalize this result to monadically dependent graph classes by replacing vertex deletions with flips. Specifically, we prove that for every such class C, integer r, and ε > 0 there is some integer k with the following property: For every n-vertex graph G in C there is a k-flip G' of G such that every ball of radius r in G' contains at most ε · n vertices. We call this property flip-separability. On the way to this result, we introduce a robust toolbox for working with various notions of local separations in monadically dependent classes.

This is joint work with Édouard Bonnet, Sam Braunfeld, Ioannis Eleftheriadis, Colin Geniet, Nikolas Mählmann, Michał Pilipczuk, and Szymon Toruńczyk.

---