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.