Presentation of tree decompositions (and related concepts) in terms of continuous maps? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T00:46:51Z http://mathoverflow.net/feeds/question/120520 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120520/presentation-of-tree-decompositions-and-related-concepts-in-terms-of-continuous Presentation of tree decompositions (and related concepts) in terms of continuous maps? Niel de Beaudrap 2013-02-01T13:30:02Z 2013-02-01T13:30:02Z <p>A <a href="http://en.wikipedia.org/wiki/Tree_decomposition" rel="nofollow"><strong>tree decomposition</strong></a> of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure:</p> <ol> <li><p>Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$;</p></li> <li><p>The union $\displaystyle\bigcup X_t$ over $t \in V(T)$ is the whole vertex set $V(G)$;</p></li> <li><p>For each $v \in V(G)$, the set $Y_v := \bigl\{ t \in V(T) \;\;\big|\;\; v \in X_t \bigr\}$ induces a connected subgraph of $T$;</p></li> <li><p>For each edge $uv \in E(G)$, there exists $t \in T$ such that ${u,v} \subseteq X_t\,$.</p></li> </ol> <p>This definition feels to me as though it is secretly involving a notion of continuity: not of a function between a graph $G$ and a tree $T$, but instead of a function $\tau$ that maps (non-empty) <em>sets</em> of vertices $X \subseteq V(G)$ to (non-empty) <em>sets</em> of vertices $Y \subseteq V(T)$, in which connectivity is preserved.</p> <p>This is not a notion of continuity precisely in terms of preserving open sets, but perhaps one can make this connection by coming up with a suitably clever notion of an "open set" in a graph, <em>e.g.</em> involving closed edges. The property which I'm singling out as being suggestive of continuity is in this case the preservation of connectivity of subsets.</p> <p>My question is: have people approached subjects such as tree-decompositions (or path decompositions, etc.) explicitly from a point of view of continuous functions before, and has it proven a useful way of presenting results? For instance, is there any reference which approaches the subject of tree-decompositions and tree-widths in this manner, or which discusses graph-theoretic structures in terms of such connectivity-preserving functions on vertex-sets?</p> <p>(I posted this question previously on <a href="http://math.stackexchange.com/q/286672/439" rel="nofollow">Math.SE</a>, without any answers.)</p>