commit 303c3bc4165c40a7bbf5642b97b138db2895050f
parent ac1dfb3f7bdca4b54afd7abc48d7928bce5d80fe
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 27 May 2025 16:57:42 +0200
commit with codex
Diffstat:
2 files changed, 1 insertion(+), 21 deletions(-)
diff --git a/deletion_breakable b/deletion_breakable
@@ -1,20 +0,0 @@
-# Deletion breakable
-
-Discussed in [maehlman2024monadically] and at [stacs_2024_szymon]
-
-A [graph_class] C is deletion breakable if for every radius r, there is a k and an unbounded function U satsifying the following:
-
-- for every [graph] G in the [graph_class], for every subset W of the vertices of G
-- there are two subsets A and B of W that are "large", i.e., have size at least U(|W|)
-- there is a subset of vertices S of size at most k (the [separator])
-- such that the [distance] from A to B is at least r in G when S is removed
-
-Special case: [infinity_deletion_breakable]
-
-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)
-
-A [graph_class] is deletion breakable iff it is [nowhere_dense]
-
-Next: notion of [flip], and [infinity_flip_breakable]
-
-Up: [stacs_2024_szymon]
diff --git a/logical_separability b/logical_separability
@@ -4,4 +4,4 @@
Up: [logic]
-See also: [craig_interpolation]
+See also: [craig_interpolation], [separability]