Flip-separability

Prelegent(ci)

Wojciech Przybyszewski

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

14 maja 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Flip-separability

Seminarium

Seminarium „Teoria automatów”

---

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.

---