Combinatorial distance between simplicial complexes

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!

• I wonder how this compares to Gromov-Hausdorff distance with respect to a standard metric on simplicial complexes. Commented Apr 5, 2013 at 2:31
• What about the cardinality of the symmetric difference between the complexes viewed as abstract simplicial complexes? Commented Apr 5, 2013 at 3:23
• Joseph, I am now confused about the calculation in your example. What happened to the 2-simplex $cef$ which is present in $K_2$ but not in $K_1$, but did not contribute to the distance? Commented Apr 5, 2013 at 20:24
• @Vidit: Thank you for correcting that "typo," if I may so characterize my error! :-) Now repaired in the figure. Commented Apr 5, 2013 at 23:59
• Joseph: You may want to look first at the 1-dimensional case. The problem you are dealing with is, then, harder than the graph isomorphism problem. I do not know much about the latter, but it is possible that people in computational complexity looked at this generalization. After all, you can encode a graph in its incidence matrix, taken modulo relabeling of the indices, i.e. modulo permutation group acting on matrices by conjugation. Commented Apr 6, 2013 at 19:49

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.

• @Vidit: I appreciate your attention to this question, and your nice ideas. This notion of an intermediate $M$ to which $K$ and $L$ map accords with my intuition. Now that I realize how difficult is my question, I'll accept yours as "the" answer, with the understanding that you by no means intended it as the final word on the topic. Thanks! Commented Apr 7, 2013 at 14:04

This is a homotopy-theoretical version of your idea.

Metric Structures for CW Complexes

By Nicholas Scoville

Topology Proceedings, Volume 44 (2014) 117-131

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.

• I think you are crudely off. I am not familiar with simplicial complexes, but I have looked at Boolean minimization in geometric terms, and Joseph's problem strikes me as having some similarity to that. It seems that determining such an edit distance could be NP hard. Gerhard "Could Also Be Crudely Off" Paseman, 2013.04.05 Commented Apr 6, 2013 at 2:29
• Wlodzimiers, the vertex labels in the drawing are not part of the input data. Basically, you have no idea when one simplex that you would like to remove from $K_1$ is actually isomorphic to another simplex from $K_2$ or not without already knowing the space of all partial simplicial maps $K_1 \to K_2$. To convince yourself that the problem is indeed computationally hard, start with Joseph's picture but remove all the vertex labelings! Commented Apr 6, 2013 at 3:19