Finite ℝ-graphs: maps, critical refinements and the Reeb quotient
Setting
Levels are S : CriticalValues n with a 0 < ⋯ < a n and gaps K e = (a e, a (e+1)) (see
reeb-constructible-cosheaf.md). Finite data D : FiniteReebData n consist of finite types
V i and E e and endpoint maps left e : E e → V e.castSucc and right e : E e → V e.succ.
A map D.Hom D' is a family of maps on vertex and edge sets commuting with both endpoint maps.
Empty sets, isolated vertices, parallel edges and noninjective endpoint maps are allowed, and
edges are not encoded by a relation on vertices, so parallel edges stay distinct.
The realization X = (ofFiniteData D).Realization S gives every piece the discrete topology
and is compact and Hausdorff (see reeb-constructible-space.md). Write h for its height.
Maps over a common level list
HeightMap S D D' is the type of all continuous maps g : X → X' with h' ∘ g = h. No
cellwise condition is imposed. The classification homEquiv S : D.Hom D' ≃ HeightMap S D D' has
the forward map realizeHom and both inverse laws.
- Vertex component.
gmaps the critical fiberh⁻¹{a i} ≅ V iintoh'⁻¹{a i} ≅ V' i; this isvertexFiberMap g i(apply_ofVertex). - Edge component. For
t ∈ K e, the regular fiber mapregularFiberMap g e t : E e → E' ereads the strip label ofg (y, t). On path components it does not depend ont, and sinceE' eis discrete the map itself does not (regularFiberMap_indep_of_discrete).edgeMapreads it at the chosen base pointbasePt S e, sog (y, t) = (edgeMap y, t)on the whole open strip (apply_ofStrip). - Incidence. On the closed segment
[a e, a (e+1)],t ↦ g (y, t)andt ↦ (edgeMap y, t)are continuous and agree on the dense open gap. The target is Hausdorff, so they agree at both ends (apply_ofCylinder). The ends are the vertex points ofleft yandleft (edgeMap y)(respectivelyright), andofVertexis injective, so both incidence squares hold (toHom). No injectivity ofleftorrightis used. - Inverse laws.
gand the realization oftoHom gagree on generators, so they are equal (hom_ext). Conversely, the data of a realized map are recovered from vertex points by injectivity ofofVertexand from strip points byregularFiberMap_realizeHom.
Graph objects
Finite data form a category (FiniteReebData.instCategory). The realization functor
realizationFunctor S : FiniteReebData n ⥤ Over (TopCat.of ℝ) takes values in the real slice,
where reeb-quotient-comparison.md defines the Reeb quotient endofunctor. Slice morphisms
between realizations are exactly height-preserving maps (overHomEquiv), so the functor is
fully faithful (realizationFullyFaithful).
A slice object A is a graph object, IsRGraph A, when A ≅ toOver T D for some m,
T : CriticalValues m and D : FiniteReebData m. Graph objects form the full subcategory
RGraphCat, so their morphisms are all height-preserving continuous maps. A presentation is
evidence for the property, not an object. The packaging lives in universe 0, the universe of the
real slice; the classification above holds in every universe.
Incidence quiver and incidence graph
For finite Reeb data D, IncidenceVertex D is the sigma type of all vertices over all
levels. It carries the incidence quiver (instQuiverIncidenceVertex), whose arrows are the
edges x : D.E e from left e x at level e.castSucc to right e x at level e.succ.
Thus parallel edges are distinct arrows, as witnessed by homCastSuccSuccEquiv and
arrowTotalEquiv, while isEmpty_hom_of_ne rules out arrows except between consecutive
levels.
The simple graph incidenceGraph D joins two vertices when an arrow exists in either
direction (incidenceGraph_adj_iff). It is functorial through incidenceGraphHom and
incidenceGraphIso, but forgets parallel edges. The map incidenceEdgeSet is onto the
simple-graph edge set and is injective exactly when no two edges share endpoints
(incidenceEdgeSet_injective_iff). Hence the simple-graph edge count is at most the total
number of edges (card_incidenceGraph_edgeSet_le), with equality in the injective case
(card_incidenceGraph_edgeSet_eq). Fixtures G1–G6 are in
TDA/Reeb/FiniteDataGraphExamples.lean; G2 exhibits two parallel edges giving one graph
edge, and G3 shows that the parallel and single-edge finite Reeb data have isomorphic
incidence graphs without being isomorphic as finite Reeb data.
Refinement
Let T : CriticalValues m with range S.value ⊆ range T.value. The refined data
refineData hST D take as vertex set at the T-level t j the fiber h⁻¹{t j}, and as edge set
of the T-gap j the fiber over its base point basePt T j. Both are finite (finite_fiber).
- Endpoints. A point
yof the base fiber ofjis a strip point of someS-gape(exists_strip_rep). SinceTrefinesS, the closedT-segment ofjlies in the closedS-segment ofe(Icc_subset_of_mem). Following the cylinder ofygives a continuousedgePoint yon theT-segment, independent of the chosen strip description (edgePoint_eq). Its two ends are the refinedleftandright. - Homeomorphism. The universal property gives
refineMapfrom the refined realization overT: vertex points go to themselves and(y, t)goes toedgePoint y t. It preserves height. It is injective, because points at aT-level are fiber points and distinct edges through a base fiber stay apart at heights that are notS-levels (edgePoint_inj). It is surjective, because a point whose height is not aT-level lies in aT-gap and on anS-strip whoseS-gap contains the base point of thatT-gap. The source is compact and the target Hausdorff, so it is a homeomorphism (refineHomeomorph), andrefineIsois the slice isomorphism. - Inserted levels. If
t j ∈ K e, the vertex set att jisE e(refineVEquiv). Both adjacentT-gaps have base points inK e(basePt_mem_K_of_succ,basePt_mem_K_of_castSucc), so their edge sets areE e(refineEEquiv), and both incidences are the identity (refine_right_eq,refine_left_eq). The endpoint maps into a level that is not anS-level are bijective (right_bijective,left_bijective): the inserted vertices have degree two. - Old levels. If
t j = a i, the vertex set isV i(refineVEquivOld). AT-gap based inK eends at an old level only ata (e+1)and starts at one only ata e(old_level_succ,old_level_castSucc); there the refined incidences areD.right eandD.left e(refine_right_old,refine_left_old). - Exterior levels and gaps outside
[a 0, a n]carry empty sets (isEmpty_refine_V,isEmpty_refine_E, fromisEmpty_fiber).
These identifications cover every vertex set, edge set and incidence of the refined data. Up to
them, inserting a regular level into K e replaces the edge set E e by a new vertex set and two
copies of E e with identity incidences, and exterior levels add empty pieces. The refined data
are built from fibers; no separate insertion constructor is used.
The graph-PL instance graphPLRefineIso in TDA.Mapper.GraphPLDataRefinement shows that graph-PL finite Reeb data over a refinement of a covering list are isomorphic to refineData of the coarser data; see docs/math/mapper.md.
Common refinement, coherence and presentation independence
The sorted union of two level lists refines both (exists_common_refinement), so any two graph
objects have presentations over one list (exists_common_presentation).
For iA : A ≅ toOver T DA and iB : B ≅ toOver T DB, the classification
homEquivOfIso iA iB : (A ⟶ B) ≃ (DA ⟶ DB) conjugates by the presentations and applies full
faithfulness (homEquivOfIso_apply). It preserves identities and composition
(homEquivOfIso_id, homEquivOfIso_comp). For two presentations of each object:
- over the same
T, the bijections are conjugate by the data isomorphismspresIso(homEquivOfIso_conj); - refining both presentations along
T ⊆ Ucommutes with the classification through the transferrefineHom(homEquivOfIso_refine); -
for presentations over
TandT'and any common refinementU,refineHom hTU (homEquivOfIso iA iB f) ≫ σ_B = σ_A ≫ refineHom hT'U (homEquivOfIso iA' iB' f)where
σ_Aandσ_Bare thepresIsoof the presentations transferred toU(homEquivOfIso_independent).
So the finite description of a morphism is independent of the presentations up to these
canonical data isomorphisms; mere equicardinality of the Hom sets is not what is stated. For
S ⊆ T ⊆ U, the two refinements of D over U are related by the explicit data isomorphism
refineCoherentIso, whose square with the refinement isomorphisms commutes
(refineCoherentIso_comm); it is the unique finite map with that property (refine_coherent).
refineHom, presIso and refineCoherentIso are obtained from full faithfulness rather than
combinatorially, and the lemmas above determine them.
The Reeb quotient
Every fiber of X is homeomorphic to a vertex set or an edge set, or is empty, so it is discrete
(discreteTopology_fiber). A path of constant height is a path in one discrete fiber and is
constant, so the Reeb relation of h is equality (reebRel_iff_eq). The identity of X
therefore descends through the universal property of the quotient to an inverse projInv of the
projection, and ReebQuotient.proj is a height-preserving homeomorphism (projHomeomorph,
height_projHomeomorph). Neither compactness nor injectivity of the height is used; the height
of a graph is usually not injective.
Naturality: for every height-preserving g between realizations over a common S,
projInv ∘ ReebQuotient.map g = g ∘ projInv (projInv_natural). The point
projNatTrans : 𝟭 ⟶ Q of the Reeb quotient endofunctor has an invertible component at every
realization (isIso_projNatTrans_app_toOver), hence at every graph object by transport along a
presenting isomorphism. Its restriction to graph objects is a natural isomorphism
(isIso_projNatTrans_rgraph, projNatIso).
Fibers of arbitrary presentations
For an arbitrary presentation P, fibers outside [a 0, a n] are empty (isEmpty_fiber, the
IsEmpty form of CylinderPresentation.height_preimage_eq_empty), and a point whose height is not
a level is an open-strip point (exists_strip_rep). Neither statement uses finiteness or
discreteness of the pieces.
Fixtures
TDA.Reeb.RGraphExamples works with realizations and slice morphisms:
- two parallel edges over
0 < 1and a single edge are not isomorphic graph objects; - exchanging the two parallel edges is an involutive non-identity automorphism of the data and of
the graph object, and it moves the regular point
(true, 1/2); - with two vertices per level and one edge attached to the vertices
false, every height-preserving self-map fixes the attached bottom vertex, and the realized collapse sends the isolated vertex onto it; - the 0–1–2 path and the 0–1–2–1 cycle over
0 < 1 < 2are not isomorphic; by construction the cycle has a noninjectiveleftat gap0, and it is its own Reeb quotient; - inserting the level
1/2into a single edge gives a one-point vertex set with bijective incoming and outgoing endpoint maps, and the refined graph object is isomorphic to the original; - refining
0 < 1to0 < 1 < 2adds an empty vertex set at2and an empty edge set over(1, 2); - for
n = 0, finite maps are functions on the single vertex set, so the slice endomorphisms of two points at one level are all functionsBool → Bool; - the realization of the empty data is empty, and any graph object with an empty carrier, in
particular the empty graph over any level list, is initial in
RGraphCat.
TDA.Reeb.FiniteDataGraphExamples records the incidence-quiver and incidence-graph fixtures
G1–G6, including the loss of parallel-edge multiplicity.
Source correspondence
de Silva, Munch and Patel, Categorified Reeb Graphs:
- §2.2, Remark 2.3: the critical set is not uniquely specified, since extra critical points can
be added by splitting the cylinders. For ℝ-graphs, the last sentence of Notation 2.7 retains the
finite description by splitting the edges at new vertices over the new critical points. Here,
for finite data, this is
refineDatawithrefineHomeomorphand the identifications of all vertex sets, edge sets and incidences. - §2.3, Notation 2.7: an ℝ-graph is specified by finite vertex sets
Vᵢ, finite edge setsEᵢover[aᵢ, aᵢ₊₁]and attaching mapsℓᵢ : Eᵢ → Vᵢ,rᵢ : Eᵢ → Vᵢ₊₁. These areFiniteReebDatawithleftandright. The category Reeb consists of the constructible ℝ-spaces with 0-dimensional pieces, with the morphisms of ℝ-Top. Here it isRGraphCat, the full subcategory of the real slice on objects isomorphic to realizations of finite data. - §2.3, Proposition 2.8: for ℝ-graphs with a common critical set, morphisms are precisely
vertex and edge maps satisfying both consistency conditions. Here this is
homEquiv, with both inverse laws, andrealizationFullyFaithful. The remark after it that a common critical set is no restriction, by taking the union of critical sets, isexists_common_refinementandexists_common_presentation;homEquivOfIso_independentstates that the resulting finite description does not depend on the presentations. - §2.4, Proposition 2.13: each ℝ-graph is naturally isomorphic to its Reeb graph, because its
levelsets are finite discrete and the canonical projection is a homeomorphism. Here this is
projHomeomorphand the natural isomorphismprojNatIsoonRGraphCat.
Not claimed here: a minimal or canonical critical set; a literal insertion constructor for
refinements; refinement of presentations with non-discrete pieces; a description of maps between
realizations over different level lists without passing to a common refinement; simple-graph,
tree, Hasse-diagram or ordering descriptions of graph objects; horizontal edges of
piecewise-linear inputs; the packaging in universes other than 0. The equivalence of graph
objects with constructible cosheaves is in reeb-rgraph-cosheaf-equivalence.md.
Source: de Silva, Munch and Patel, Categorified Reeb Graphs.