Reeb Graphs: Approximation and Persistence

Given a continuous function f:X→? on a topological space X, its level set f ^?1(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph, which can facilitate its broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called vertical homology group, as well as between cycles in M and in a Rips complex constructed from P, we compute the H ₁-homology of the Reeb graph from P. It takes O(nlogn) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm for computing the rank of H ₁(M) from point data. The best-known previous algorithm for this problem takes O(n ³) time for point data. The second aspect concerns the definition and computation of the persistent Reeb graph homology for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H ₁-homology for the Reeb graphs in $O(n n_{e}^{3})$ time, where n is the size of the 2-skeleton and n _e is the number of edges in K.     

Trivial Cycles in Graphs Embedded in 3-Manifolds

A cycle C of a graph embedded in a 3-manifold M is said tobe trivial in if it bounds a disk with interior disjoint from. Let e be an edge of with ends on C. We shall study the relationbetween triviality of cycles in and that of – e and/e. Let C₁ be one of the two cycles in C e containing e. Themain theorem says that if C is trivial in – e and C₁/eis trivial in /e, then either C or C₁ is trivial in . Some applicationsto cycle trivial graphs will be given in Section 2.     

Graphs of Stable Maps from 3-Manifolds to 3-space

We associate a graph with weights in its vertices and edges to any stable map from a 3-manifold to ${\mathbb{R}^3}$ . These graphs are ${\mathcal{A}}$ -invariants from a global viewpoint. We study their properties and give a sufficient and necessary condition for a graph to be the graph of a stable map from a 3-sphere with handles to ${\mathbb{R}^3}$ . We also obtain a sufficient condition in the general case of a closed stably paralellizable 3-manifold in terms of its Heegaard genus.     

Enumeration of Non-Orientable 3-Manifolds Using Face-Pairing Graphs and Union-Find

Drawing together techniques from combinatorics and computer science, we improve the census algorithm for enumerating closed minimal P² 3-manifold triangulations. In particular, new constraints are proven for face-pairing graphs, and pruning techniques are improved using a modification of the union-find algorithm. Using these results we catalogue all 136 closed non-orientable P² 3-manifolds that can be formed from at most 10 tetrahedra.     

Extremal Problems on Components and Loops in Graphs

The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that Ω(G) ≤-4 are shown to be disconnected, and if Ω(G) ≥-2, then the graph is potentially connected. It is also shown that if the realization is a connected graph and Ω(G) =-2, then certainly the graph should be a tree.Similarly, it is shown that if the realization is a connected graph G and Ω(G) ≥ 0, then certainly the graph should be cyclic. Also, when Ω(G) ≤-4, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then Ω(G) ≥ 0. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs.We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence.     

Loops, Reflection Structures and Graphs with Parallelism

The correspondence between right loops (P, +) with the property “(*) ?a, b ∈ P : a ? (a ? b) ? b” and reflection structures described in [4] is extended to the class of graphs with parallelism (P, ε, ∥). In this connection K-loops correspond with trapezium graphs, i.e. complete graphs with parallelism satisfying two axioms (T1), (T2) (cf. §3 ). Moreover (P, ε, ∥ +) is a structure loop (i.e. for each a ∈ P the map a ⁺ : P → P; x → a + x is an automorphism of the graph with parallelism (P, ε, ∥)) if and only if (P, +) is a K-loop or equivalently if (P, ε, ∥) is a trapezium graph.     

On 2-Systoles of Hyperbolic 3-Manifolds

We investigate the geometry of π ₁-injective surfaces in closed hyperbolic 3-manifolds. First we prove that for any ${\epsilon > 0}$ , if the manifold M has sufficiently large systole sys₁(M), the genus of any such surface in M is bounded below by ${{\rm exp}((\frac{1}{2} - \epsilon){\rm sys}_1(M))}$ . Using this result we show, in particular, that for congruence covers M _i → M of a compact arithmetic hyperbolic 3-manifold we have: (a) the minimal genus of π ₁-injective surfaces satisfies ${{\rm log} \, {\rm sysg}(M_i) \gtrsim \frac{1}{3} {\rm log} \, {\rm vol}(M_i) ; (b)}$ there exist such sequences with the ratio Heegard ${{\rm genus}(M_i)/{\rm sysg}(M_i) \gtrsim {\rm vol}(M_i)^{1/2}}$ ; and (c) under some additional assumptions π ₁(M _i ) is k-free with ${{\rm log} \, k \gtrsim \frac{1}{3}{\rm sys}_1(M_i)}$ . The latter resolves a special case of a conjecture of Gromov.     

Gluing Affine 2-Manifolds with Polygons

Affine structures on surfaces are constructed by gluing polygons. The geometry of the affine surface depends on the shape of the polygon(s) and the particular gluing transformations used. The affine version of the Poincaré fundamental polygon theorem expresses the fundamental group and holonomy of the surface in terms of the gluing data. The theorem may be used to construct all complete affine structures on the 2-torus. The space of inequivalent holonomy representations of such structures is homeomorphic to R2.     

Dolbeault Cohomology for G2-Manifolds

Cocalibrated G₂-manifolds are seven-dimensional Riemannian manifolds with a distinguished 3-form which is coclosed. For such a manifold M, S. Salamon in Riemannian Geometry and Holonomy Groups (Longman, 1989) defined a differential complex related with the G₂-structure of M.In this paper we study the cohomology of this complex;it is treated as an analogue of a Dolbeault cohomologyof complex manifolds. For compact G₂-manifoldswhose holonomy group is a subgroup of G₂ special propertiesare proved. The cohomology of any cocalibrated G₂-nilmanifold \K is also studied.     

Polar Graphs and Corresponding Involution Sets, Loops and Steiner Triple Systems

A 1-factorization (or parallelism) of the complete graph with loops is called polar if each 1-factor (parallel class) contains exactly one loop and for any three distinct vertices x₁, x₂, x₃, if {x₁} and {x₂, x₃} belong to a 1-factor then the same holds for any permutation of the set {1, 2, 3}. To a polar graph there corresponds a polar involution set , an idempotent totally symmetric quasigroup (P, *), a commutative, weak inverse property loop (P, + ) of exponent 3 and a Steiner triple system . We have: satisfies the trapezium axiom is self-distributive ⇔ (P, + ) is a Moufang loop is an affine triple system; and: satisfies the quadrangle axiom is a group is an affine space.     

The Genus of a Digital Image Boundary Is Determined by Its Foreground,Background, and Reeb Graphs

We prove that the genus of the boundary of a digital image is precisely half of the sum of the cycle ranks of three particular graphs: the "foreground graph" and "background graph," which capture topological information about the digital image and its complement, respectively, and the Reeb graph, relative to the natural height function, associated with the digital image's boundary. We prove several additional results, including a characterization of when the cycle rank of the Reeb graph fails to equal the genus of the digital image's boundary (which can happen by virtue of the failure of the natural height function on the boundary of the digital image to be a Morse function).     

Tubular Neighbourhoods of 2-Flats in 4-Manifolds of Nonpositive Curvature

We show that every orientable ²-vector bundle over the 2-torus arises as a tubular neighbourhood of a 2-flat in a closed 4-manifold of nonpositive sectional curvature and rank one.