Categorical Mapper and Reeb approximation
Let G be a finite simple graph, with arbitrary real vertex heights h. Its realization
carries the affine height f = plHeight G h. Horizontal edges, repeated vertex heights and
disconnected inputs are allowed. Let U_i = (a_i,b_i) be a finite family of bounded open
intervals covering the values attained by f. Intervals outside that range may be discarded;
intervals meeting only an edge interior are retained.
For every nonempty simplex σ of the cover nerve, categorical Mapper stores the path
components of f⁻¹(U_σ), where U_σ is the full intersection of the intervals indexed by σ.
Its maps are induced by the inclusions belonging to faces. categoricalMapperData formalizes
this diagram. coverIntersectionInterval presents each intersection as an open
interval, and finite_graphPL_categoricalMapperData proves that every graph-PL component
value of this diagram is finite. It preserves distinct components of an intersection, even when ordinary
Mapper records only a single edge over the same pair of component vertices.
For a test interval I, select precisely the simplices for which U_σ ∩ I is nonempty.
The functor usually denoted P_K C_K takes their component diagram's colimit. The chosen
colimit model categoricalMapperAssembly is the path-component set of
categoricalMapperIsColimit proves its universal property, and
categoricalMapperCocone_map identifies its interval maps with the maps induced by inclusion
of selected simplices.
The assembly is an interval cosheaf. For the gluing proof, a fixed cover interval meets an
interval cover in a connected chain; local compatible functions therefore agree on each
original cover component. The endpoints of the bounded cover form a finite critical-value
witness. Finiteness of the graph-PL pullback components then gives a constructible cosheaf.
These facts supply the hypotheses of the existing finite reconstruction equivalence, whose
inverse D yields the real graph graphPLMapperReconstruction.
Error and convergence
Define the retained resolution by
clippedCoverResolution separately records the maximum diameter of U_i ∩ range(f).
Each retained interval contributes its full ambient width to the bound above. For constant input, clipping an
interval to the attained singleton would give zero width although the assembled cosheaf has
values away from that height. The clipped-resolution fixture proves zero, while the
constant-input fixture proves strictly positive geometric
error by ruling out a small positive shift through an empty target fiber.
coverComponentsRetainedIso proves that discarding exactly the
empty pullbacks preserves the assembly.
geometricInterleavingDistance_mapperReeb_le_retained proves
Here 𝓡(f) is GraphPL.graphPLReebGraph, the Reeb quotient equipped with its finite
real-graph property. The proof constructs both natural comparison maps on input
points, verifies their interleaving composites, and transports the result through the
reconstruction and quotient component isomorphisms. The version
geometricInterleavingDistance_mapperReeb_le uses all cover members' widths.
tendsto_geometricInterleavingDistance_mapperReeb gives convergence to zero when cover
resolutions tend to zero; the _retained version needs only retained resolutions to vanish. The finite index type may vary along the family.
exists_graphPLMapperCover_resolution_le constructs a finite uniform cover for any
positive prescribed resolution; finite vertex heights provide range bounds.
exists_graphPLMapperReconstruction_error_le exports the resulting geometric estimate.
The nonconstant single-edge example exposes a family with vanishing full resolutions, its
geometric error bounds and convergence.
Constructible ℝ-spaces
Let A be a constructible ℝ-space in universe zero, an object of ConstructibleSpaceCat, with
structure map f = overBaseMap A.obj. No Hausdorff property is assumed. Let ι be a finite
label type, possibly empty, and U_i = (a_i, b_i); repeated labels, empty intervals and empty
pullbacks are allowed. The path-component cosheaf of A is constructible
(de Silva–Munch–Patel, Proposition 3.16), so every value π₀ f⁻¹(I) is finite
(finite_intervalComponents_constructibleSpace). This discharges the finiteness hypothesis of
categoricalMapperReconstruction and gives constructibleMapperReconstruction A a b, which is
the reconstruction D P_K C_K of coverComponents f U for every proof of that hypothesis
(constructibleMapperReconstruction_eq); constructibleMapperReconstructionIso is its
reconstruction counit. Callers supply no finiteness assumption.
The target is the actual Reeb quotient quotientRGraphFunctor.obj A. The comparison
constructibleCosheafComparisonIso (de Silva–Munch–Patel, Theorem 3.17) identifies its
interval components with those of A. Together with the counit and the equality of geometric
and cosheaf interleaving distances, this gives
(geometricInterleavingDistance_constructibleMapperReeb_eq) with no coverage assumption. If
every attained height lies in some U_i, the existing bound for coverComponents and the
removal isomorphism coverComponentsRetainedIso give the error bounds
geometricInterleavingDistance_constructibleMapperReeb_le_retained by the retained resolution
retainedCoverResolution f a b and geometricInterleavingDistance_constructibleMapperReeb_le by
the full resolution coverResolution a b; retainedCoverResolution_le_coverResolution compares
the two. Both resolutions use full ambient widths, with value 0 for an empty label type; the
retained resolution deletes exactly the members with empty pullback and is not the diameter
clipped to the attained range. Along any filter of finite covers, whose label types may vary,
each covering the attained heights, vanishing full or retained resolution gives vanishing
geometric error (tendsto_geometricInterleavingDistance_constructibleMapperReeb and its
_retained form), by squeezing nonnegative extended distances.
For finite graph-PL input, graphPLSpace G h has structure map plHeight G h and Reeb quotient
graphPLReebGraph G h definitionally (overBaseMap_graphPLSpace,
quotientRGraphFunctor_obj_graphPLSpace), and its reconstruction is definitionally
graphPLMapperReconstruction G h a b (constructibleMapperReconstruction_graphPLSpace). The
graph-PL identity, bounds and convergence statements above are recovered verbatim from the
constructible ones; the examples check these specializations.
The constructible examples cover a nonconstant edge through graphPLSpace, with convergent
reconstructions; the non-Hausdorff indiscrete two-point space at constant height, where a far
member with empty pullback keeps the full resolution at least 95 while the retained
resolution and the geometric error are at most 2, and shrinking covers give convergence; the
empty space with empty labels and with a removed wide member, both with error 0; and the
coverage boundary: empty labels cannot cover nonempty input, and on the indiscrete space their
reconstruction is at geometric distance ⊤ from the Reeb quotient although the full resolution
is 0.
Two inputs
Let h, g : V → ℝ be vertex heights on one finite simple graph G, and let (a, b) and
(a', b') be finite bounded-interval covers of the attained ranges of plHeight G h and
plHeight G g, with resolutions res and res'. Write M_h, M_g for the two
reconstructions and 𝓡(h), 𝓡(g) for the Reeb quotients. At the cosheaf level, for
continuous f, g : C(X, ℝ) with |f x - g x| ≤ ε and covers whose members have diameters at
most r and r', the triangle inequality for the interleaving distance and the one-input bound
give
and r + ‖f - g‖∞ + r' with the uniform extended distance
(interleavingDistance_coverComponents_le_add, _edist).
For graph-PL input, the geometric triangle inequality with
geometricInterleavingDistance_mapperReeb_le and the vertex-height bound
geometricInterleavingDistance_graphPLReebGraph_le_edist give
(geometricInterleavingDistance_mapperReeb_le_add_edist), with forms for a vertex budget ε,
for retained resolutions, and for one cover (2 res + edist h g). The same triangle inequality
in the other direction gives the two-sided comparison
d_geo(𝓡(h), 𝓡(g)) ≤ d_geo(M_h, M_g) + res + res' and
d_geo(M_h, M_g) ≤ d_geo(𝓡(h), 𝓡(g)) + res + res'
(geometricInterleavingDistance_graphPLReebGraph_le_mapperReeb_add and
geometricInterleavingDistance_mapperReeb_le_graphPLReebGraph_add). With the extremal
lower bounds of the Reeb distance, for nonempty V,
|max h - max g| ≤ d_geo(M_h, M_g) + res + res', and the same for min.
Along families of covers (κ t, a t, b t) and (κ' t, a' t, b' t) that cover the
attained ranges at every t and have both resolutions tending to 0,
tendsto_geometricInterleavingDistance_mapperReeb_pair shows that d_geo(M_h^t, M_g^t) tends to
d_geo(𝓡(h), 𝓡(g)), by squeezing between d_geo(𝓡) - (res_t + res'_t) and
d_geo(𝓡) + res_t + res'_t in ℝ≥0∞; the retained form needs only retained resolutions to
vanish. exists_graphPLMapperReconstruction_pair_le gives, for every r > 0, finite covers with
d_geo(M_h, M_g) ≤ edist h g + 2 r.
Coverage of each height's attained range is required by the ingredients: the empty cover of a
nonempty graph reconstructs the empty graph, which is at distance ⊤ from the Reeb quotient
although its resolution is 0. None of the bounds is claimed to be sharp. With equal heights
and one cover the distance is 0 while the bound is 2 res. Reconstructions
over different graphs or edge sets are not compared. The two-input bounds are compositions of the
one-input approximation with the triangle inequality and are attributed to neither source paper;
the perturbation step is de Silva–Munch–Patel, Theorem 4.6(i).
For vertical translation the distance is exact at every finite cover. Translating the height to
f + c and every member to U i + c gives an assembled precosheaf naturally isomorphic to
translatePre c (coverComponents f U) (coverComponentsTranslateIso), so the two assemblies are
at distance at most |c|. For a finite bounded-interval cover (a, b) with an active member,
that is a member with nonempty inverse image, the distance is exactly |c|
(interleavingDistance_coverComponents_add_const): for c > 0 and ε < c, the interval
(a i₀, a i₀ + (c - ε)/2) at the least left endpoint a i₀ of an active member has a nonempty
assembled value for f, while every original member meeting translate c (thicken ε I) has
left endpoint strictly below a i₀ and is therefore inactive. Hence, for graph-PL input,
(geometricInterleavingDistance_graphPLMapperReconstruction_add_const, and _of_covers when the
cover covers the attained range of h on a nonempty vertex type). No coverage, resolution bound
or boundedness is assumed. The active member cannot be dropped: two graph objects with empty
total spaces are at distance 0 (RGraph.geometricInterleavingDistance_eq_zero_of_isEmpty), so
over empty covers of a nonempty graph the reconstructions of h and h + 1 are at distance 0
while the Reeb quotients are at distance 1 and both resolutions are 0, so the comparison
d_geo(𝓡(h), 𝓡(g)) ≤ d_geo(M_h, M_g) + res + res' also needs coverage. Translation of graph
objects, RGraph.translateRGraph c, preserves the geometric interleaving distance and moves every
graph object with nonempty total space by exactly |c| (see
reeb-rgraph-translation.md); the reconstruction of h + c over the
translated cover is not identified with the translate of the reconstruction of h. Translating
the cover by c preserves its resolution (coverResolution_add_const). Translating the height
without the cover, or the cover without the height, is covered only by the perturbation bounds
above.
Scope and computation
The interval-indexed categorical bound follows the objects and conclusion of Munch–Wang, Convergence between Categorical Representations of Reeb Space and Mapper, arXiv v2, Theorem 4.1, Lemma 7.1 and Corollary 8.1. The formalization begins with finite graph-PL input in universe zero and uses the library's existing quotient and finite reconstruction. Its interval arguments use the one-dimensional intersection property of real intervals. The constructible-input results extend this interval-basis proof to constructible ℝ-spaces in universe zero, using the constructibility of the path-component cosheaf and de Silva–Munch–Patel, Theorem 3.17, for the actual Reeb quotient; they are not the full higher-dimensional source theorem. No higher-dimensional Reeb-space theorem or automatic identification with the ordinary Mapper simple graph is asserted. Positive-error finite-cover existence for arbitrary constructible input is not claimed.
The component functors, colimits and reconstructed graph are abstract mathematical objects. Classical finite-witness selection is permitted. This result provides neither an executable component enumeration procedure nor a complexity bound. An executable algorithm would require a separate specification and a correctness bridge to these objects.
The examples cover a horizontal edge, repeated heights on a disconnected graph, a retained edge-interior hit with no retained vertex, an empty pullback, the constant-input width boundary, and the four-cycle's two categorical intersection components over one ordinary Mapper edge. A finer three-member cover has a reconstructed graph with two components over its central test interval, established through the reconstruction isomorphism. A coarse assembly may merge those components; the categorical input count alone does not prove that the reconstructed graph preserves the loop. See the source register and DMP15-v1 for source and rights scope.