A notion of 2-dimensional tree

Question

Summary: This post has got rather long after the discussion. The main still open Questions are 5 & 6 below. There is work in progress, and I'll post an update at some point.

A tree is a connected 1-complex $X$ every two points $x,y$ of which can be separated by a point $z\neq x,y$. (We could let $X$ be a more general topological space here.)

Going one dimension up, call a connected 2-complex (or topological space) $X$ a 2-tree, if for every $x,y\in X$, there is a homeomorph of a forest in $X - \{x,y\}$ separating $x$ from $y$. (A forest is a disjoint union of trees.)

Question 1: Has this notion been studied?

Question 2: Is it true that a 2-complex $X$ is a 2-tree iff it contains no homeomorph of a closed surface? (The forward implication is obvious.)

Some examples of 2-trees: standard trees, graphs, $\mathbb{R}^2$, and most interestingly, cartesian products $\mathbb{R} \times T$, where $T$ is any tree (to see this, embed $\mathbb{R} \times T$ in $\mathbb{R}^3$, and cut it with a plane separating $x$ from $y$).

Examples of non-2-trees: closed surfaces, $\mathbb{R}^3$, standard Cayley complex of $\mathbb{Z}^3$ (to see the latter, notice that it contains copies of $\mathbb{S}^2$).

Remark: The definition can be applied recursively, to define $n$-trees for every $n\in \mathbb{N}$.

Update 1: The answer to Question 2 is negative, as Geva Yashfe points out in the comments.

As Sam Nead points out below, the variant of the definition with “forest” replaced by “tree” seems more sensible. Now a graph is a 2-tree iff it is a tree. Defining a 0-tree to be a point, the recursive definition now starts with 1-trees being the usual trees.

The main question now is: Question 3: Is every CW-complex (or other nice space, see e.g. Ian Agol’s answer) which is an $n$-tree contractible? Simply-connected?

Update 2 The answer to Question 3 is negative: as Geva Yashfe points out, an annulus is a 2-tree.

A remaining question is:

Question 4: Is every $(n-1)$-connected CW-complex which is an $n$-tree contractible?

But here is another variant of the recurersive definition of n-tree that perhaps makes Q3 interesting again:

Definition 3:

• a point is a strong 0-tree;

• A space X is a strong n-tree, if for every two disjoint strong $(n-1)$-trees $T$, $T'$ in X, there is a strong $(n-1)$-tree $S$, disjoint from $T$, $T'$, that separates them.

Question 5: Is every strong $n$-tree contractible?

Going through the above examples and non-examples with 2-trees replaced by strong 2-trees is interesting.

My motivation goes back to a theorem of Manning, saying that a graph is quasi-isometric to a tree if (and only if) every two points $x$, $y$ are separated by a ball of uniformly bounded radius around any midpoint from $x$ to $y$. This could be reformulated as saying that $X$ is a quasi-1-tree iff every two disjoint strong quasi-0-trees in $X$ can be separated by a third strong quasi-0-tree disjoint from both. I'm looking for the right definition that will generalise this to higher dimensions. Thus I propose:

Question 6: Let $X$ be a geodesic metric space in which every two disjoint strong quasi-$(n-1)$-trees can be separated by a third strong quasi-$(n-1)$-tree disjoint from both. Then $X$ is a strong quasi-$n$-tree.

By strong quasi-$n$-tree here I mean a space quasi-isometric to a strong $n$-tree, and the constants are some function of the dimension and the constants used in dimension $n-1$.

Answer 1

There is a notion of a CAT(0) square complex (or more generally cube complex). This has the desired property: hyperplanes will be trees, and any two points are separated by a hyperplane.

More generally there’s a concept of a special cube complex, which Dani Wise has promoted as a higher-dimensional version of graphs in From Riches to Raags: 3-Manifolds, Right-Angled Artin Groups, and Cubical Geometry (see quote below). CAT(0) cube complexes are just the simply connected special cube complexes (like trees are simply-connected graphs). This is probably also much more restrictive than your condition. However, a theorem of Sageev, in Ends of group pairs and non-positively curved cube complexes, implies that a space with sufficiently many hyperplanes (such as 2-complexes in which every pair of points is separated by a properly embedded tree) may be “cubulated” (embedded into a CAT(0) cube complex), so in some sense these might be the right category to consider.

Special cube complexes are introduced as cube complexes whose immersed hyperplanes behave in an organized way and avoid various forms of self-intersetions. CAT(0) cube complexes are high-dimensional generalizations of trees, and likewise, from a certain viewpoint, special cube complexes play a role as high-dimensional “generalized graphs”. In particular they allow us to build (finite) covering spaces quite freely, and admit natural ….

Answer 2

Edit 2: My answer points out one problem and proposes a solution. However Geva Yashfe (comments below) points out a further problem. I've added a yet further example, and I conclude that much stronger combinatorial control seems to be needed.

---

Original: Note that a point is a tree, and a pair of points is a forest. Thus with the given definition the circle $S^1$ is a two-tree. (In fact, any finite graph is a two-tree with the given definition.) Thus all surfaces are three-trees, and more generally all $n$-manifolds are $(n+1)$-trees.

The examples given in the original post strongly suggest that this is not the desired outcome. Perhaps the following definition is closer to what you want.

1. The zero-tree is the one-point space.
2. A connected topological space $X$ is an $(n+1)$-tree if for any pair of distinct points $x, y \in X$ there is an $n$-tree $Y \subset X - \{x, y\}$ separating $x$ from $y$.

I think that life is nicer if we also add the assumption that $n$-trees are homeomorphic images of CW-complexes. With this additional assumption I believe we can prove the following.

Lemma: Suppose that $X$ is an $n$-tree. Then $X$ is simply connected.

---

Edit 1: As Geva points out, the annulus is an easy counterexample to my claimed “Lemma”. This is because properly embedded intervals separate points in any connected surface with boundary. Their technique generalises - if $M$ is a connected $n$-manifold with boundary then properly embedded $n$-disks separate points in $M$. As a concrete example, consider $M = S^2 \times [0,1]$.

Thus there is no way to strengthen the OP hypotheses without making them very combinatorial... If you are willing to do that, then Ian’s answer seems like a very natural direction.

Answer 3

In this answer a weak $2$-tree is a simplicial complex in which any two points can be separated by a forest. It is clear that a strong $2$-tree is also a weak $2$-tree. By passing to subdivisions, we may assume that any (specific) given subpolyhedron of a simplicial complex is a subcomplex, and we will do this implicitly when discussing trees in $2$-trees.

Define the face-edge graph $G$ of a $2$-dimensional simplicial complex $X$ to be the following graph: its vertices are the $2$- and $1$- dimensional faces of $X$ (so just triangles and edges). There is an edge in $G$ between a $2$-face $\sigma$ and a $1$-face $\tau$ if $\tau\subset\sigma$.

A free face in a simplicial complex $X$ is a face $\tau$ which is properly contained in precisely one face $\sigma$ (which must then be of dimension exactly $1+\dim\tau$). If $\sigma$ has a free face $\tau$ of codimension $1$, an elementary collapse can be performed which deletes both $\tau$ and $\sigma$: it is convenient to think of this as a strong deformation retract of $X$ onto the complement of $\sigma$. A complex which, by a sequence of elementary collapses, can be turned into a vertex is called collapsible. If some subdivision is collapsible the complex is called geometrically collapsible. It makes sense to speak of collapsing a complex onto a subcomplex, or geometrically collapsing a complex $X$ onto a subpolyhedron $Y$, and we will denote the situation that $X$ (geometrically) collapses onto $Y$ by $X \searrow Y$. (These notions are more or less standard in PL topology / combinatorial topology.) We may subdivide our complexes as much as convenient, although we won't really need to subdivide much. I won't keep track of when a certain sequence of collapses requires / does not require subdivisions.

Given a collapse $X\searrow Y$ we can realize each elementary collapse as a PL map in a more-or-less obvious way. Composing these we obtain a $\pi:X\rightarrow Y$ which I will call the ``collapse map'' below. This may not be unique -- there are probably several reasonable ways to define the map for each elementary collapse -- but it is a strong deformation retract with the property that if $\dim X = 2$ and the collapsed faces are all $2$-dimensional then the preimage of any point is a tree.

Claim: Let $X$ be a weak $2$-tree. If $\sigma\in X$ is a $2$-face, its component in $G$ is either infinite or contains a free edge of $X$.

Proof: Suppose the component of $\sigma$ in $G$ is finite and denote by $Y$ the union of all $1$- and $2$- faces in this component (including their vertices). Let $x,y$ be two points in the interior of $\sigma$. Let $F\subset X$ be a forest separating $x$ from $y$. Then $F^{\prime}=F\cap Y$ is a forest which separates $x$ from $y$ within $Y$. If a leaf of $F^{\prime}$ is not on a free edge, there is a path ``around'' this leaf, and it is redundant: The leaf and its unique edge can be deleted from $F^{\prime}$, and the resulting forest still separates $x$ from $y$ within $Y$. Deleting all redundant leaves iteratively in this way until none remain, we end up with a nontrivial forest, and each of its leaves is in a free edge of $Y$. ${\scriptstyle \blacksquare}$

Claim: A subcomplex of a weak $2$-tree is a weak $2$-tree.

Proof: Just intersect any forest which separates two given points with the subcomplex. It still intersects all paths between the points, and hence separates. ${\scriptstyle \blacksquare}$

Claim: A finite weak $2$-tree collapses onto a $1$-dimensional subcomplex.

Proof: Iteratively collapse all $2$-faces with a free edge. By the previous two claims, at each step we still have a finite weak $2$-tree, and there is still a free edge. ${\scriptstyle \blacksquare}$

Claim: A finite strong $2$-tree is collapsible.

Proof: Let $X$ be a finite strong $2$-tree. Collapse it onto a $1$-dimensional subcomplex $Y$ (a graph), and let $\pi:X\rightarrow Y$ be a corresponding PL retract satisfying that the preimage of any point is a tree. Assume there is a nontrivial loop, and let $x,y$ be two points on this loop. Their $\pi$-preimages are disjoint trees $T_{1},T_{2}$, which can be separated by a tree $T\subset X$. But then $\pi\left(T\right)$ is a connected set which separates $x$ from $y$, a contradiction. ${\scriptstyle \blacksquare}$

---

For lack of time to think and write in detail, I decided to include some ideas without proof. I would have preferred not to put something so "unripe" here, hopefully it is useful.

I think we can prove the following claim by induction on the number of faces (the induction step involves examining an elementary collapse performed in reverse).

Claim(?): A collapsible $2$-dimensional complex is a strong $2$-tree.

I will leave this for another time or for another person. I think it's easy if true (and probably true) but I did not check carefully, there could be some weird edge-case.

It is interesting is to ask what happens in the case of an infinite complex such as a triangulation of $\mathbb{R}^{2}$. This is probably necessary if we want to work with quasi-isometry... I suggest calling an infinite complex $X$ collapsible if there is an infinite chain $U_{1}\supseteq U_{2}\supseteq U_{3}\supseteq\ldots$ of open neighborhoods of the set of all ends of $X$ such that $X\setminus U_{i}$ is compact and collapsible for each $i$ and $\bigcap_{i}U_{i}=\emptyset$.

I think I have a proof that any (possibly infinite) strong $2$-tree is contractible using this notion. It should be possible to strengthen it to get "honest" collapsibility, if the definition is weakend slightly. At each step the complex may only be collapsible onto a graph; but these graphs should themselves collapse onto vertices in some later stage $X\setminus U_j$. (Perhaps I will update this answer with it on some other evening). I have not seen definitions for infinite collapsibility of this form before, perhaps they are new.

There is a decent chance these ideas extend to the higher dimensional notions.

Answer 4

See k-d trees, which are commonly used for cartesian region queries.

https://en.wikipedia.org/wiki/K-d_tree

Obviously, this isn't a mathematical construct, but an algorithmic one, but it is based on the same sort of recursive partitioning of space in k dimensions.

This is a member of a larger class of binary space-partitioning trees, largely differing by how the choice of intermediate partition point $z $ is chosen. K-d trees go back to 1975, so any related algorithms/data structures papers on these topics could have some relevance, depending on what you're looking to show.