Canonical sequence conjecture for tangle-distinguishing tree-decompositions

Let GG be a graph, and let nn denote the relevant maximum tangle order. A canonical sequence of tree-decompositions is a sequence (Ti,Vi)(T_i,\mathcal{V}_i) for 1in1\leq i\leq n, where each (Ti,Vi)(T_i,\mathcal{V}_i) is a tree-decomposition of GG, and where refinement and torsos are understood in the usual sense. A part is inessential at stage ii if it does not contain an (i+1)(i+1)-tangle.

Canonical sequence conjecture. For every graph GG there exists a canonical sequence of tree-decompositions (Ti,Vi)(T_i,\mathcal{V}_i) for 1in1 \leq i \leq n of GG such that:

  • (Ti,Vi)(T_i,\mathcal{V}_i) distinguishes every ii-tangle in GG for each ii;
  • (Tn,Vn)(T_n,\mathcal{V}_n) distinguishes the set of maximal tangles in GG;
  • (Ti+1,Vi+1)(T_{i+1},\mathcal{V}_{i+1}) refines (Ti,Vi)(T_i,\mathcal{V}_i) for each ii;
  • the torso of every inessential part in (Ti,Vi)(T_i,\mathcal{V}_i) has branch-width <i<i.

This is presented as the strongest form of a positive answer to the preceding question about bounding the branch-width of inessential parts. The preceding theorem establishes the existence of a canonical nested set distinguishing all tangles, but the claimed simultaneous sequence, refinement property, and branch-width bound remain conjectural.

Sources & referencesView supporting material

Primary source

Joshua Erde, “Refining a Tree-Decomposition which Distinguishes Tangles”, arXiv:1512.02499 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.