deletion_breakable (865B)
1 # Deletion breakable 2 3 Discussed in [maehlman2024monadically] and at [stacs_2024_szymon] 4 5 A [graph_class] C is deletion breakable if for every radius r, there is a k and an unbounded function U satsifying the following: 6 7 - for every [graph] G in the [graph_class], for every subset W of the vertices of G 8 - there are two subsets A and B of W that are "large", i.e., have size at least U(|W|) 9 - there is a subset of vertices S of size at most k (the [separator]) 10 - such that the [distance] from A to B is at least r in G when S is removed 11 12 Special case: [infinity_deletion_breakable] 13 14 Example: on [grid]: for every set W of vertices, there is an r-[independent_set] (you can take the empty set of vertices as a separator) 15 16 A [graph_class] is deletion breakable iff it is [nowhere_dense] 17 18 Next: notion of [flip], and [infinity_flip_breakable] 19 20 Up: [stacs_2024_szymon]