Based in part on Jeff Erickson's nice invited talk on algorithms for finding small cycles in topological spaces at WADS, I just added a brief survey on Vietoris–Rips complexes to Wikipedia.

I'm a little worried that one point I included may violate Wikipedia's prohibition on original research, though: the Vietoris–Rips complex of any metric space X turns out to always equal the Čech complex of some set of balls in some larger space into which X can be embedded.

Specifically, if X is embedded in any injective metric space Y, then the Vietoris–Rips complex for distance δ in X is the same as the Čech complex for the balls of radius δ/2 centered at the points of X in Y: the Rips complex includes a simplex for any finite set of balls that intersect pairwise, the Čech complex includes a simplex for any finite set of balls with a common intersection, and an injective metric space is defined by the property that any set of balls that intersect pairwise has a common intersection. Since any metric space can be embedded in an injective space via the tight span, the result follows.

This seems obvious enough (and important enough) that I'd include it in a survey or research paper on a related subject without attempting to assign or take credit for it, but Wikipedia has different standards: everything must have a source. So, can anyone help me find a published paper that includes something resembling this statement? I suppose in the worst case that this blog post might suffice, but it's not a very good source by Wikipedian standards...

ETA: Carlsson says he doesn't know more than what's in his new paper (which mentions that the two complexes are the same for L∞ spaces), and he should know. And Jeff has put his talk slides up.




Comments:

None:
2007-09-02T03:27:16Z
Hmmm. An easy extension of the alpha-complex idea?
11011110:

11011110:
2007-09-02T05:23:46Z
Um, the Čech complex is, sort of. At least, both the Čech complex and the alpha-complex involve sorting tuples of points by circumradius, although the Čech complex allows all tuples, even those of more than (d+1) points while the alpha-complex restricts to tuples that come from the Delaunay triangulation, and the Čech complex is more usually thought of as fixed at some specific scale parameter while the alpha-complex is I think more thought of as a sequence graded by scale. I'm not sure what insight the alpha-complex has for Vietoris–Rips complexes, though.
None:
2007-09-02T20:15:17Z

I was a little confused about the point in your article regarding Cech complexes, because I understood your definition to refer to balls within M itself, which I would think would be a perfectly valid (if often uninteresting) definition; why then would the containing space matter? Shouldn't even the definition of a Cech complex of M refer to the metric space containing M, a Cech complex of M "relative to" M' containing M, or something?

-Ken Clarkson

11011110:
2007-09-02T20:31:55Z

Probably the wording could be made more clear. I don't know if there's a commonly used shorthand for "the Čech complex of the set of δ-balls centered at points of X in a space Y ⊃ X", though.

The point I was trying to make is, I think, the same one you're expressing: specifying M and δ alone is not enough to determine "the Čech complex" because for that complex it matters in what space M is embedded.

I think the actual definition of Čech complex is just that you start with a family of sets and form a simplex for every finite subfamily that has a common intersection. The balls aren't really part of the definition, they just come in as the most likely sets to use to relate Čech complexes to Vietoris–Rips complexes.