Topological description for graph minors

68 Views Asked by At

In the following content, graphs are considered inside $ZFC$ as the $1$-dimensional CW-complexes deduced from its cardinal-valued (multigraphs may have cardinals larger than $1$ as entries) adjacent "matrix" (which means no edges intersect at non-vertices although it may seem to), the size of which may also be infinite cardinals. In this sense, subgraphs precisely correspond to closed subcomplexes. For simplicity an answer about the finite case is welcome.

There are two main partial orders defined on graphs: Given two graphs $G$ and $H$, $H$ is a topological minor of $G$ iff $H$ is isomorphic to the subgraph of some finite-step subdivision-and-smoothing of $G$, and $H$ is a minor of $G$ iff $H$ is isomorphic to the subgraph of some finite-step edge-contraction of $G$ (here, a one-step edge-contraction is operated on a single edge connecting two different vertices). The former has a nice topological description - $H$ is a topological minor of G iff $H$ can be topologically embedded into $G$ (at least true for finite graphs) - while the latter, despite being manipulated in a topological manner, is seldom considered topologically. This qustion concentrates on a possible topological description of the latter and ask for verification.

Observe that a graph $G$ has a canonical CW-epimorphism to its finite contraction by mapping the closure of the contracted $1$-cells to the result $0$-cells. Moreover, this epimorphism is in fact a homotopy equivalence (each contraction is a topological quotient by a contractible subspace). So $H$ is a minor of $G$ only if $H$ can be topologically embedded into some graph $G'$ that admits a surjective homotopy equivalence from $G$. Does the inverse (the "if" direction) also hold true? The subtle point is that the "if" direction does not require the surjective homotopy equivalence to be a CW-morphism to involve no more information outside the $Top$ category.

1

There are 1 best solutions below

1
On BEST ANSWER

First of all, the case that $G$ is an infinite graph is false. Take for instance the following graph $G$ embedded in $\mathbb R^2$: $$G = (\mathbb R \times \mathbb \{0\}) \cup (\mathbb Z \times [0,1]) $$ There is a quotient map $f : G \to G'$ which maps the entire line $\mathbb R \times \mathbb \{0\}$ to a single point and is otherwise one-to-one. The graph $G'$ is a star graph of countably infinite valence, meaning it has one vertex of countably infinite valence, connected to countably infinite vertices of valence $1$. Both of $G$ and $G'$ are contractible, hence $f$ is a homotopy equivalence. Taking $H=G'$, it follows that $H$ can be topologically embedded into some graph $G'$ that admits a surjective homotopy equivalence from $G$. However, $H$ is not isomorphic to any subgraph of some finite-step edge-contraction of $G$, because in any finite-step edge contraction of $G$ every point has finite valence.


But the case where $G$ is a finite graph does seem to be true. The proof requires one to understand all possible surjective homotopy equivalences $f : G \to G'$. First, since $G$ is compact and $H$ is Hausdorff, the map $f$ is a quotient map. The map $f$ induces a decomposition of $G$, and lets consider $Q$ to be the collection of nontrivial decomposition elements, i.e. $$Q = \{f^{-1}(y) \mid y \in G', |f^{-1}(y)| > 1\} $$ Each element of $Q$ is an embedding of a finite tree into $G$, because otherwise $f$ would not be a homotopy equivalence. There are countably many components of $Q$, and those components are pairwise disjoint. Define $C(G) \subset G$ to be the union of all edges of $G$ that are contained in $Q$, so $C(G)$ is an actual subgraph, and each of its components is a tree. You can now collapse the edges of $C(G)$ one-at-a-time to get a quotient graph $G \mapsto G''$, but what happens here is that $G''$ is isomorphic to the graph $G'$. So now it is true: if a graph $H$ can be topologically embedded into $G'$, then it can be topologically embedded into $G''$ and so $H$ is a minor of $G$.