Combinatorial distance between simplicial complexes

Question

Let $K_1$ and $K_2$ be two simplicial complexes. I am seeking a measure of the distance between $K_1$ and $K_2$ when viewed as combinatorial objects. What I have in mind is something like this.

Remove simplices (of various dimensions) from $K_1$ such that, at each stage, the remaining object is a simplicial complex. Then add simplices, again always remaining a simplicial complex, until a complex isomorphic to $K_2$ is obtained. The fewest number of simplices added or removed in order to "renovate" $K_1$ to $K_2$ is some measure of their distance. Perhaps, in order to accommodate the different dimensions, a simplex of dimension $d$ should have weight $d+1$ in the count. Let us call this the renovation distance between $K_1$ and $K_2$.

For example, below, removal of two triangles from $K_1$, and adding a triangle and a segment, reaches $K_2$ (with the isomorphism mapping indicated by the vertex labels) (Example corrected 5Apr13 by Vidit Nanda comment):
     
So here the renovation distance is at most $11$ (and I don't see a more efficient path). Likely it is not computationally easy to compute this renovation distance. (Update 5Apr13: Vidit Nanda observes that a special case is subgraph isomorphism, an NP-complete problem.)

My definition is not well-grounded in any theory. Have there been definitions of distances between simplicial complexes that capture a similar intuitive notion? I'd appreciate pointers to relevant literature. Thanks!

Answer 1

This got too long for a comment, so I am placing it here.

I don't think there is a theory already out there, but that should not be too surprising. After all, the "combinatorial distance" between a simplicial complex and its barycentric subdivision (which, from a topological perspective, is basically the same thing) could be enormous. So, such a distance separates simplicial complexes that most topologists might consider equivalent. That being said, this sounds kind of neat so maybe we can come up with something here.

I'll denote by $|\sigma|$ the weight being assigned to each simplex $\sigma$, which in your current definition appears to be the cardinality. All simplicial complexes here will be assumed to be finite and non-empty. What should one hope for from a renovation distance $r$ between simplicial complexes?

Axiom 1: The distance $r(K,K')$ between a simplicial complex $K$ and a subcomplex $K' \subset K$ should equal $\sum_{\sigma \in K \setminus K'}|\sigma|$.

Axiom 2: Given two simplicial complexes $L$ and $K$ so that the set of subcomplexes of $K$ isomorphic to $L$ is non-empty, $r(K,L)$ should be the smallest possible $r(K,K')$ as $K'$ ranges over subcomplexes of $K$ isomorphic to $L$.

If one believes these axioms, then there are at least two constructions (dual to each other) which will produce such a distance. The basic inspiration comes from category theory: just consider the limit and the colimit of the disconnected diagram in the category of simplicial complexes with injective simplicial maps as the morphisms.

The Limit Given simplicial complexes $K$ and $L$, consider the set of all triples $(M,i,j)$ where $M$ is a simplicial complex and $i:M \to K$ and $j:M \to L$ are injective simplicial maps. To each such triple, we may assign the distance $d(M,i,j) = r(K,i(M)) + r(L,j(M))$. The smallest such $d$ achieved over all such triples does the trick. Since we have assumed non-emptiness, at least the one-vertex complex injects into both $K$ and $L$.

The Colimit Given simplicial complexes $K$ and $L$, consider the set of all triples $(M,i,j)$ where $M$ is a simplicial complex and $i:K \to M$ and $j:L \to M$ are injective simplicial maps. To each such triple, we may assign the distance $d(M,i,j) = r(M,i(K)) + r(M,j(L))$. The smallest such $d$ over all such triples does the trick. Since both $K$ and $L$ include into the disjoint union, there is at least one such triple.

Maybe the best answer is some mixture of these two. In any case, you are quite right about the complexity being high: anything one comes up with is harder than the NP-complete subgraph isomorphism problem.

Answer 2

This is a homotopy-theoretical version of your idea.

Metric Structures for CW Complexes

By Nicholas Scoville

Topology Proceedings, Volume 44 (2014) 117-131

Answer 3

Am I missing something? You need to remove what you need to remove, and to add what you need to add.

Thus the first stage: remove one of the highest dimensional simplices from the first complex which does not belong to the second complex. Do it again and again until there is nothing more to do.

The second and last stage: add one of the lowest dimension simplices which is missing in your construction but is present in the second complex. Do it again and again until there is nothing more to do.

That's it. If the weight of each simplex is simply $1$ then the distance between two simplicial combinatorial complexes is equal to the cardinality of the symmetric difference of the given two complexes (as was already mentioned).

Sorry if I am crudely off.