Realizations of simple graphs
Consulted manifestations, attribution and rights: ReebOrdering-aa7d10f, mathlib-0df444a.
The realization
For V : Type u and G : SimpleGraph V the cells are
Cells G = V ⊕ Σ _ : G.Dart, unitInterval
one point for each vertex and one copy of the unit interval for each dart, that is, for each
oriented edge. The vertex summand carries the discrete topology ⊥, whatever topology V may
have, and the edge summand the sigma (disjoint-union) topology of copies of the unit interval;
each vertex cell is open (isOpen_vertexCell). The relation CellRel G has exactly two
generators,
CellRel.symm d t : (d, t) ~ (d.symm, σ t)
CellRel.start d : (d, 0) ~ d.fst
orientation reversal and attachment of the start of a dart. Realization G := Quot (CellRel G)
carries the quotient topology, with quotient map quotMk. Two cells have the same image exactly
when the equivalence relation generated by CellRel G relates them (quotMk_eq_quotMk_iff, with
Relation.EqvGen). The realization is neither given the discrete topology nor replaced by a
quotient by components.
vertex G v and edgePoint G d t are the images of the cells. Reversal gives
edgePoint G d.symm (σ t) = edgePoint G d t (edgePoint_symm); the start equation is
edgePoint G d 0 = vertex G d.fst (edgePoint_zero), and the end equation
edgePoint G d 1 = vertex G d.snd (edgePoint_one) follows from the two. Every point is a vertex
or an edge point (ind), so functions and continuous maps out of the realization are determined
by their values on vertices and edge points (function_ext, hom_ext). function_ext is not
named funext, so opening the namespace does not shadow _root_.funext.
No finiteness, local finiteness, nonemptiness, decidable adjacency, separation or topology of the vertex type is assumed anywhere in the construction, the universal property, the maps or the component equivalence.
Universal property
Vertex data fv : V → Y and edge data fe : G.Dart → unitInterval → Y with
hsymm : ∀ d t, fe d.symm (σ t) = fe d t
hstart : ∀ d, fe d 0 = fv d.fst
descend to lift G fv fe hsymm hstart : Realization G → Y, with lift_vertex and
lift_edgePoint by rfl. The lift is unique among all functions with these values
(lift_unique). It is continuous as soon as every fe d is (continuous_lift): continuity is
checked through the quotient map, on the discrete vertex summand and on each interval cell
separately; no topology on V is involved. For continuous edge data
fe : G.Dart → C(unitInterval, Y), continuousLift : C(Realization G, Y) is the bundled form,
with its evaluation lemmas, uniqueness among continuous maps (continuousLift_unique) and
existsUnique_continuousLift.
Distinct vertices stay distinct (vertex_injective). The proof is set-level: the lift to
Option V sending a vertex to itself, an endpoint of an edge to its vertex and an interior edge
point to none respects both generators. No continuous retraction to the vertices is asserted.
The realization is empty for an empty vertex type and nonempty for a nonempty one
(instIsEmptyRealization, instNonemptyRealization).
Paths
edgePath G d : Path (vertex G d.fst) (vertex G d.snd) is the edge map on [0, 1]
(edgePath_apply), and walkPath G p concatenates the edge paths of a walk p
(walkPath_nil, walkPath_cons). Hence reachable vertices have joined images
(joined_vertex_of_reachable). Every edge point is joined to the first endpoint of its dart
(joined_edgePoint_vertex), by the straight path from t to 0 in the unit interval followed
by the edge map. For any parameters s t : unitInterval, edgeSegment G d s t is the subpath
from edgePoint G d s to edgePoint G d t. Its value at r is the edge point at
Set.Icc.convexComb s t r (edgeSegment_apply); the endpoint laws are edgeSegment_zero and
edgeSegment_one. This provides paths along one dart and says nothing about decomposing arbitrary
paths into dart segments. The construction is Mathlib's Path.subpath applied to edgePath G d.
Maps induced by graph homomorphisms
For V : Type u, W : Type v and a graph homomorphism φ : G →g H,
realizationMap φ : C(Realization G, Realization H)
realizationMap φ (vertex G v) = vertex H (φ v)
realizationMap φ (edgePoint G d t) = edgePoint H (φ.mapDart d) t
both formulas by rfl. It is the bundled lift of these data; the two compatibilities hold because
φ.mapDart commutes with reversal and with the first endpoint. Identity and composition hold as
equalities of continuous maps (realizationMap_id, realizationMap_comp), with three
independent vertex universes for composition. A graph homomorphism preserves adjacency, so every
edge goes to an edge and no edge is collapsed to a vertex. Nonadjacent vertices and distinct edges
may be identified.
Path components
componentLabel G : Realization G → G.ConnectedComponent sends vertex G v to the component of
v and edgePoint G d t to the component of d.fst; the two generators are respected because
adjacent vertices lie in the same component. With the discrete topology chosen locally on the
component type the label is continuous, so it is constant along paths
(componentLabel_eq_of_joined, through TDA.Reeb.joined_eq_of_discrete). Hence two vertices
have joined images exactly when they are reachable (joined_vertex_iff), and every edge point
lies in the path component of a vertex (mk_edgePoint).
componentsEquiv G : ZerothHomotopy (Realization G) ≃ G.ConnectedComponent
componentsEquiv G (ZerothHomotopy.mk (vertex G v)) = G.connectedComponentMk v
componentsEquiv G (ZerothHomotopy.mk (edgePoint G d t)) = G.connectedComponentMk d.fst
(componentsEquiv G).symm (G.connectedComponentMk v) = ZerothHomotopy.mk (vertex G v)
The forward map is the label on path components, and the inverse sends a graph component to the
class of a representing vertex, well defined because walks give paths. All three formulas hold by
rfl, and both inverse laws are fields of the equivalence: the vertex case is rfl and the edge
case is mk_edgePoint.
Naturality. For every φ : G →g H and every path component c,
componentsEquiv H (TDA.Reeb.componentMap (realizationMap φ) c) = (componentsEquiv G c).map φ
(componentsEquiv_componentMap), where TDA.Reeb.componentMap is the library's map on
ZerothHomotopy induced by a continuous map (see reeb-components.md) and the right-hand map is
mathlib's SimpleGraph.ConnectedComponent.map. Both generator cases hold by rfl. The same
square is available as an equation of functions (componentsEquiv_comp_componentMap) and in the
inverse direction (componentMap_componentsEquiv_symm). The identity and composition laws of
componentMap give componentMap (realizationMap Hom.id) = id
(componentMap_realizationMap_id) and the composition law across three universes
(componentMap_realizationMap_comp). No category of graphs is built.
Connectedness. connected_iff_pathConnectedSpace : G.Connected ↔ PathConnectedSpace
(Realization G). Both sides include nonemptiness: mathlib's Connected carries
Nonempty V, and PathConnectedSpace is equivalent to a nonempty subsingleton ZerothHomotopy
(pathConnectedSpace_iff_zerothHomotopy). The proof transports both conditions along
componentsEquiv; an empty graph is neither connected nor has a path-connected realization. The
statement concerns path components, not connected components.
Library and mathlib declarations used
The production module uses the library declarations TDA.Reeb.componentMap,
TDA.Reeb.componentMap_id and TDA.Reeb.componentMap_comp (TDA.Reeb.Components) and
TDA.Reeb.joined_eq_of_discrete (TDA.Reeb.ComponentsDiscrete); the fixtures additionally use
only TDA.Reeb.componentMap. None is restated. Its main pinned mathlib ingredients are
SimpleGraph.ConnectedComponent with connectedComponentMk, lift, ind, exact, map and
connectedComponentMk_eq_of_adj, SimpleGraph.Hom.mapDart, SimpleGraph.connected_iff,
ZerothHomotopy with mk, lift, rec and sound, pathConnectedSpace_iff_zerothHomotopy,
isQuotientMap_quot_mk, continuous_sum_dom and continuous_sigma; the fixtures also use
SimpleGraph.ConnectedComponent.sound, SimpleGraph.pathGraph and SimpleGraph.reachable_bot.
Names and universes
The construction lives in namespace TDA.Reeb.GraphRealization (TDA/Reeb/GraphRealization.lean)
and the fixtures in TDA.Reeb.Examples.GraphRealization (TDA/Reeb/GraphRealizationExamples.lean);
no production module imports the fixtures. The vertex type has an arbitrary universe u, and
Cells G and Realization G live in Type u. realizationMap, its laws, the naturality square
and the corollaries allow independent universes for the vertex types of source, target and, for
composition, a third graph; the same-universe case is an instance. The graph is an explicit
argument of vertex, edgePoint, lift, continuousLift, componentsEquiv and the naturality
square componentsEquiv_componentMap; realizationMap φ infers it from φ. The only private
declaration is the straight path in the unit interval behind joined_edgePoint_vertex.
Fully qualified names are distinct from all other library names, but some short names are not.
Realization, instTopologicalSpaceRealization, quotMk, quotMk_surjective,
isQuotientMap_quotMk, continuous_quotMk, lift, lift_unique and hom_ext also occur in
TDA.Reeb.CylinderPresentation (reeb-constructible-space.md), lift, lift_unique, hom_ext
and ind in TDA.Reeb.ReebQuotient (reeb-quotient.md), and edgePoint and
continuous_edgePoint in TDA.Reeb.RGraph (reeb-rgraph.md). A file opening more than one of
these namespaces qualifies the overlapping names. Among the fixtures, fold, half,
pointGraph, swapHom, swap_naturality and swap_ne_id also occur in other fixture
namespaces.
Fixtures
TDA.Reeb.GraphRealizationExamples proves:
- Empty vertex type. For every
[IsEmpty V]in any universe, the realization, its path components and the graph components are empty, and both connectedness statements are false (empty_realization_isEmpty,empty_zerothHomotopy_isEmpty,empty_connectedComponent_isEmpty,empty_not_connected,empty_not_pathConnectedSpace). - One isolated vertex. The realization of
⊥ : SimpleGraph Unitis a point: it isUniqueand homeomorphic toUnit(pointUnique,pointHomeomorph). Both component types have exactly one element (pointComponentsUnique,point_card_connectedComponent,point_card_zerothHomotopy), and the graph is connected with path-connected realization (point_connected,point_pathConnectedSpace). - One edge on two vertices. For
⊤ : SimpleGraph Booland the dartd₀ : false → true,edgeHomeomorph : Realization ⊤ ≃ₜ unitIntervalsendsvertex false ↦ 0,vertex true ↦ 1,edgePoint d₀ t ↦ tandedgePoint d₀.symm t ↦ σ t, with inverseedgePoint d₀. The reversed dart at the reversed parameter is the same point (edge_reversed), and distinct parameters, interior ones included, give distinct points (edge_param_injective,edge_interior_ne). - Two disjoint edges. On
Bool × Boolwith edges(a, false) — (a, true), the path components are equivalent toBool(twoEdgesComponents,twoEdges_card), the vertex classesc₀andc₁are distinct (c₀_ne_c₁), and every class is one of them (twoEdges_classification). - A two-edge path folded onto one edge.
fold : pathGraph 3 →g ⊤sends0, 1, 2tofalse, true, false. It identifies the nonadjacent ends0and2(fold_identifies_ends) and, pointwise off the shared vertex, the distinct edges0 — 1and1 — 2(fold_identifies_edges, separated by a set-level height). It is a graph homomorphism, not an edge contraction. The generator formulas hold on all three vertices and on the darts0 → 1,2 → 1(imaged₀) and1 → 2(imaged₀.symm, with reversed edge coordinatefold_coord_d12). Naturality is evaluated at the interior point1/2of both orientations of the second edge (fold_naturality_d21,fold_naturality_d12). - A permutation of two components.
swapHomexchanges the two disjoint edges. Its induced map on path components sendsc₀ ↦ c₁andc₁ ↦ c₀and is not the identity (swap_c₀,swap_c₁,swap_ne_id). Atc₀both sides of the naturality square are the class of(true, false), which is not the class ofc₀(swap_naturality). - Infinite edgeless graphs. In an edgeless graph on any type, distinct vertices lie in
distinct path components (
bot_class_injective). Onℕthe vertex map and the class map are injective, there are infinitely many path components and the realization is not path connected (nat_vertex_injective,nat_class_injective,nat_zerothHomotopy_infinite,nat_not_pathConnectedSpace): no finiteness is assumed. Onℝthe realization is not path connected althoughℝis (real_class_injective,real_not_pathConnectedSpace): the topology of the vertex type is not used.
The fold lands in a connected graph, whose component type is a subsingleton, so its naturality
square holds whatever the component maps are and does not discriminate at the level of
components. Its discriminating content is in the generator and orientation formulas, which
distinguish the two darts of the target edge. The component-level negative control is the swap:
both of its classes are distinct, the induced map is not the identity, and the square at c₀ has
a value different from c₀'s own class.
Source correspondence
Construction source. The cells, the relation, the quotient, the lift and its continuity, the
edge and walk paths, the map of a graph homomorphism and the component label are adapted from
uda-lab/reeb-ordering,
ReebOrdering/GraphRealisation.lean
at commit aa7d10f4f7dc0474b76f17ea81afcab5a230d521 (blob
6b79160f368a9d6fd63f2d52f1db4d9c5697cfa8), Copyright 2026 Tomoki Uda, licensed under the
Apache License, Version 2.0.
The copyright line is that of the source repository's LICENSE; the source file has no in-file
notice, and the repository has no NOTICE file at that revision. The source is not imported and
is not a dependency.
Adapted declarations, with source names and lines:
| Library declaration | Source declaration | Lines |
|---|---|---|
Cells, instTopologicalSpaceCells |
Cells and its topology |
26–30 |
CellRel with symm, start |
RealisationRel |
32–36 |
Realization, instTopologicalSpaceRealization |
Realisation and its topology |
38–45 |
quotMk |
Realisation.mk |
47–48 |
vertex, edgePoint |
vertex, edgePoint |
50–54 |
edgePoint_symm, edgePoint_zero, edgePoint_one |
the same, private | 56–70 |
isQuotientMap_quotMk |
isQuotientMap_mk, private |
72–73 |
ind |
realisation_induction, private |
75–82 |
lift |
lift |
84–92 |
lift_vertex, lift_edgePoint, continuous_lift |
the same, private | 94–111 |
continuous_edgePoint |
the same, private | 155–158 |
edgePath, walkPath |
edgePath, walkPath |
160–171 |
realizationMap |
map |
173–188 |
realizationMap_vertex, realizationMap_edgePoint |
map_vertex, map_edgePoint, private |
190–195 |
componentLabel, componentLabel_eq_of_joined |
the label f and its continuity into the discrete component type in connected_of_pathConnectedSpace, private |
202–219 |
Changes: the names; public visibility of every adapted private lemma and of the component label;
vertex and edgePoint defined through quotMk; ind through surjectivity of quotMk;
realizationMap built from continuousLift, with independent vertex universes, where the source's
map requires both vertex types in one universe; and constancy of the label along paths through
TDA.Reeb.joined_eq_of_discrete, where the source uses constancy on a preconnected space.
New declarations: isOpen_vertexCell, quotMk_surjective, continuous_quotMk,
quotMk_eq_quotMk_iff, function_ext, hom_ext, lift_unique, continuousLift,
continuousLift_vertex, continuousLift_edgePoint, continuousLift_unique,
existsUnique_continuousLift, vertex_injective, instIsEmptyRealization,
instNonemptyRealization, edgePath_apply, edgeSegment, edgeSegment_apply, edgeSegment_zero,
edgeSegment_one, walkPath_nil, walkPath_cons,
joined_vertex_of_reachable, the private straight path pathToZero, joined_edgePoint_vertex,
realizationMap_id, realizationMap_comp, componentLabel_vertex, componentLabel_edgePoint,
joined_vertex_iff, mk_edgePoint, componentsEquiv with its three formulas,
componentsEquiv_componentMap, componentsEquiv_comp_componentMap,
componentMap_componentsEquiv_symm, componentMap_realizationMap_id,
componentMap_realizationMap_comp, connected_iff_pathConnectedSpace, and every fixture. The
source has the direction from a path-connected realization to a connected graph only as a private
lemma, and no bundled lift, lift uniqueness, vertex injectivity, component equivalence,
naturality, or identity and composition laws for its map.
de Silva, Munch and Patel. Categorified Reeb Graphs, Notation 2.7, describes a finite
ℝ-graph as the quotient of the disjoint union of vertex points Vᵢ × {aᵢ} and edge intervals
Eᵢ × [aᵢ, aᵢ₊₁] by the endpoint identifications. This is context for the cell construction: there
the vertex and edge sets are finite, edges are oriented by height and there is no reversal
relation. The realization of arbitrary simple graphs, its path-component equivalence and its
naturality are library constructions, not results of the paper. The library's realization of
height-indexed presentations, TDA.Reeb.CylinderPresentation.Realization, is a different
construction (reeb-constructible-space.md).
Mathlib and TauCeti. Pinned mathlib has the affine simplicial complex of a simple graph,
Geometry.SimplicialComplex.ofSimpleGraph in V →₀ 𝕜
(Mathlib/Analysis/Convex/SimplicialComplex/AffineIndependentUnion.lean, for [DecidableEq V],
[DecidableEq 𝕜] and a linearly ordered field 𝕜), with the vertices as 0-simplices at basis
vectors and the edges as 1-simplices; it has no quotient description, lift, induced maps or
path-component API. No file under Topology or AlgebraicTopology uses SimpleGraph. The
realization SSet.toTop is that of simplicial sets. TopCat.zerothHomotopyEquiv is not a
realization construction: it compares ZerothHomotopy X with the connected components π₀ of the
singular simplicial set of X. TauCeti, at revision 3b4a078d372e27f93b0c181e6b67df93797d1a02, has
a realization of abstract simplicial complexes under
TauCeti/AlgebraicTopology/SimplicialComplex/Realization/. Its SimpleGraph files lie under
TauCeti/Combinatorics/SimpleGraph/ and in
TauCeti/LinearAlgebra/RootSystem/FiniteType/SimpleGraph.lean, and no path under
TauCeti/Topology/ or TauCeti/AlgebraicTopology/ names SimpleGraph. This is a partial check,
not a content-level inspection of every file, so it does not establish that TauCeti has no
simple-graph realization. Nothing from TauCeti is used, and TauCeti is not a dependency.
Not claimed here: edge contraction; the fundamental group of a triangle or any other higher
homotopy; trees as simply connected realizations, which are in reeb-graph-cycle-obstruction.md
and reeb-graph-tree-contraction.md; realization of Hasse orders; piecewise-linear
heights and cell graphs of interval preimages, which are in reeb-graph-pl.md; comparisons with
multigraphs, cylinder presentations or simplicial sets; a product-of-quotient-maps lemma; a
continuous retraction of the realization to its vertices.
Sources: de Silva, Munch and Patel, Categorified Reeb Graphs, §2.3, Notation 2.7; pinned mathlib graph components, graph homomorphisms on darts and path components; subpaths supply the parameterized dart paths.