wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

infinity_deletion_breakable (530B)

      1 # Infinity deletion breakable
      2 
      3 Discussed in [maehlman2024monadically] and at [stacs_2024_szymon]
      4 
      5 Like [deletion_breakable] but only for r=infinity
      6 
      7 Example: on [tree]: k=1, U(n) = n/3
      8 - for every set W there is a vertex which is a "balanced separator" of W, i.e., removing the vertex, each connected component contains at most 1/3rd of the vertices of W
      9 - [treewidth]: similar, separators of size t+1 for t the treewidth (still U(n) = n/3)
     10 
     11 A [graph_class] C is infinity deletion breakable iff C is [treelike]
     12 
     13 Up: [graph_class]