On the Reeb spaces of definable maps. (English) Zbl 1500.03014
This paper studies the Reeb space of a continuous map \(f:X \to Y\) definable in an o-minimal expansion of an ordered real closed field. The Reeb space of \(f\) denoted by \(\operatorname{Reeb}(f)\) is the topological space \(X/\sim\) equipped with the quotient topology, where the equivalence relation \(\sim\) is defined so that \(x \sim x'\) if and only if \(f(x)=f(x')\) and both \(x\) and \(x'\) are contained in the same definably connected component of \(f^{-1}(f(x))\).
The first contribution of this paper is the assertion that the Reeb space of \(f\) exists as a definably proper quotient of \(X\) when \(X\) is closed and bounded in its ambient space. Its proof is constructive, but its known complexity is at least doubly exponential. This paper does not provide a singly exponential algorithm for constructing the Reeb space, but alternatively gives the upper bounds of the sum of its Betti numbers \(b(\operatorname{Reeb}(f))\) of the Reeb space. The paper firstly introduces the negative result that \(b(\operatorname{Reeb}(f_n))\) is arbitrarily larger than \(b(X_n)\) for some sequences of maps \(( f _n: X _n \to Y_n)_{n>0}\). Its second result is a positive one. It gives a singly exponential upper bound on the sum of the Betti numbers of the Reeb space of a proper semi-algebraic map in terms of the number and degrees of the polynomials defining the map.
The first contribution of this paper is the assertion that the Reeb space of \(f\) exists as a definably proper quotient of \(X\) when \(X\) is closed and bounded in its ambient space. Its proof is constructive, but its known complexity is at least doubly exponential. This paper does not provide a singly exponential algorithm for constructing the Reeb space, but alternatively gives the upper bounds of the sum of its Betti numbers \(b(\operatorname{Reeb}(f))\) of the Reeb space. The paper firstly introduces the negative result that \(b(\operatorname{Reeb}(f_n))\) is arbitrarily larger than \(b(X_n)\) for some sequences of maps \(( f _n: X _n \to Y_n)_{n>0}\). Its second result is a positive one. It gives a singly exponential upper bound on the sum of the Betti numbers of the Reeb space of a proper semi-algebraic map in terms of the number and degrees of the polynomials defining the map.
Reviewer: Fujita Masato (Kure)
MSC:
| 03C64 | Model theory of ordered structures; o-minimality |
| 14P10 | Semialgebraic sets and related spaces |
References:
| [1] | Aguilar, M., Gitler, S., Prieto, C.: Algebraic Topology from a Homotopical Viewpoint. Universitext. Springer, New York (2002) · Zbl 1006.55001 |
| [2] | Basu, S., On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Discrete Comput. Geom., 22, 1, 1-18 (1999) · Zbl 0973.14033 · doi:10.1007/PL00009443 |
| [3] | Basu, S., A complexity theory of constructible functions and sheaves, Found. Comput. Math., 15, 1, 199-279 (2015) · Zbl 1349.68098 · doi:10.1007/s10208-014-9222-z |
| [4] | Basu, S., Pollack, R., Roy, M.-F.: Betti number bounds, applications and algorithms. In: Combinatorial and Computational Geometry. Math. Sci. Res. Inst. Publ., vol. 52, pp. 87-96. Cambridge University Press, Cambridge (2005) · Zbl 1097.68152 |
| [5] | Basu, S.; Pollack, R.; Roy, M-F, On the Betti numbers of sign conditions, Proc. Am. Math. Soc., 133, 4, 965-974 (2005) · Zbl 1080.14068 · doi:10.1090/S0002-9939-04-07629-4 |
| [6] | Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006) · Zbl 1102.14041 |
| [7] | Basu, S., Vorobjov, N.: On the number of homotopy types of fibres of a definable map. J. Lond. Math. Soc. 76(3), 757-776 (2007) · Zbl 1131.14060 |
| [8] | Bochnak, J., Coste, M., Roy, M.-F.: Géométrie Algébrique Réelle. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 12. Springer, Berlin (1987) · Zbl 0633.14016 |
| [9] | Burlet, O.; de Rham, G., Sur certaines applications génériques d’une variété close à \(3\) dimensions dans le plan, Enseign. Math., 20, 275-292 (1974) · Zbl 0299.58005 |
| [10] | Coste, M.: An Introduction to o-Minimal Geometry. Lecture notes (1999). https://perso.univ-rennes1.fr/michel.coste/polyens/OMIN.pdf |
| [11] | Dey, T.K., Mémoli, F., Wang, Y.: Topological analysis of nerves, Reeb spaces, mappers, and multiscale mappers. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol. 77, # 36. Leibniz-Zent. Inform., Wadern (2017) · Zbl 1436.55007 |
| [12] | van den Dries, L.: Remarks on Tarski’s problem concerning \(({\bf R},+,\cdot ,\exp )\). In: Logic Colloquium ’82 (Florence 1982). Stud. Logic Found. Math., vol. 112, pp. 97-121. North-Holland, Amsterdam (1984) · Zbl 0585.03006 |
| [13] | van den Dries, L.: Tame Topology and o-Minimal Structures. London Mathematical Society Lecture Note Series, vol. 248. Cambridge University Press, Cambridge (1998) · Zbl 0953.03045 |
| [14] | van den Dries, L., Miller, Ch.: Geometric categories and o-minimal structures. Duke Math. J. 84(2), 497-540 (1996) · Zbl 0889.03025 |
| [15] | van den Dries, L., Speissegger, P.: The real field with convergent generalized power series. Trans. Am. Math. Soc. 350(11), 4377-4421 (1998) · Zbl 0905.03022 |
| [16] | van den Dries, L., Speissegger, P.: The field of reals with multisummable series and the exponential function. Proc. Lond. Math. Soc. 81(3), 513-565 (2000) · Zbl 1062.03029 |
| [17] | Edelsbrunner, H.; Harer, JL, Computational Topology (2010), Providence: American Mathematical Society, Providence · Zbl 1193.55001 |
| [18] | Edelsbrunner, H., Harer, J., Patel, A.K.: Reeb spaces of piecewise linear mappings. In: 24th Annual Symposium on Computational Geometry (College Park 2008), pp. 242-250. ACM, New York (2008) · Zbl 1271.57059 |
| [19] | Gabrielov, A.; Vorobjov, N., Betti numbers of semialgebraic sets defined by quantifier-free formulae, Discrete Comput. Geom., 33, 3, 395-401 (2005) · Zbl 1073.14072 · doi:10.1007/s00454-004-1105-7 |
| [20] | Gabrielov, A.; Vorobjov, N., Approximation of definable sets by compact families, and upper bounds on homotopy and homology, J. Lond. Math. Soc., 80, 1, 35-54 (2009) · Zbl 1177.14097 · doi:10.1112/jlms/jdp006 |
| [21] | Gabrielov, A.; Vorobjov, N.; Zell, T., Betti numbers of semialgebraic and sub-Pfaffian sets, J. Lond. Math. Soc., 69, 1, 27-43 (2004) · Zbl 1087.14038 · doi:10.1112/S0024610703004939 |
| [22] | Godement, R.: Topologie Algébrique et Théorie des Faisceaux. Publ. Math. Univ. Strasbourg, vol. 13. Hermann, Paris (1958) · Zbl 0080.16201 |
| [23] | Hartshorne, R.: Algebraic Geometry. Graduate Texts in Mathematics, vol. 52. Springer, New York (1977) · Zbl 0367.14001 |
| [24] | Milnor, J., On the Betti numbers of real varieties, Proc. Am. Math. Soc., 15, 275-280 (1964) · Zbl 0123.38302 · doi:10.1090/S0002-9939-1964-0161339-9 |
| [25] | Mimura, M., Toda, H.: Topology of Lie Groups. I, II. Translations of Mathematical Monographs, vol. 91. American Mathematical Society, Providence (1991) · Zbl 0757.57001 |
| [26] | Munch, E., Wang, B.: Convergence between categorical representations of Reeb space and mapper (2015). arXiv:1512.04108 · Zbl 1388.68289 |
| [27] | Patel, A.: Reeb Spaces and the Robustness of Preimages. PhD thesis, Duke University (2010). https://dukespace.lib.duke.edu/dspace/handle/10161/2447 |
| [28] | Petrovskiĭ, I.G., Oleĭnik, O.A.: On the topology of real algebraic surfaces. Izvestiya Akad. Nauk SSSR. Ser. Mat. 13(5), 389-402 (1949). (in Russian) · Zbl 0035.10204 |
| [29] | Pillay, A.; Steinhorn, C., Definable sets in ordered structures. I, Trans. Am. Math. Soc., 295, 2, 565-592 (1986) · Zbl 0662.03023 · doi:10.1090/S0002-9947-1986-0833697-X |
| [30] | Pillay, A.; Steinhorn, C., Definable sets in ordered structures. III, Trans. Am. Math. Soc., 309, 2, 469-476 (1988) · Zbl 0707.03024 · doi:10.1090/S0002-9947-1988-0943306-9 |
| [31] | Reeb, G., Sur les points singuliers d’une forme de Pfaff complètement intégrable ou d’une fonction numérique, C. R. Acad. Sci. Paris, 222, 847-849 (1946) · Zbl 0063.06453 |
| [32] | Rolin, J-P; Speissegger, P.; Wilkie, AJ, Quasianalytic Denjoy-Carleman classes and o-minimality, J. Am. Math. Soc., 16, 4, 751-777 (2003) · Zbl 1095.26018 · doi:10.1090/S0894-0347-03-00427-2 |
| [33] | de Silva, V., Munch, E., Patel, A.: Categorified Reeb graphs. Discrete Comput. Geom. 55(4), 854-906 (2016) · Zbl 1350.68271 |
| [34] | Singh, G., Mémoli, F., Carlsson, G.: Topological methods for the analysis of high dimensional data sets and 3D object recognition. In: Eurographics Symposium on Point-Based Graphics (Prague 2007), pp. 99-100. The Eurographics Association, Aire-la-Ville (2007) |
| [35] | Thom, R.: Sur l’homologie des variétés algébriques réelles. In: Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pp. 255-265. Princeton University Press, Princeton (1965) · Zbl 0137.42503 |
| [36] | Wilkie, AJ, Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function, J. Am. Math. Soc., 9, 4, 1051-1094 (1996) · Zbl 0892.03013 · doi:10.1090/S0894-0347-96-00216-0 |
| [37] | Wilkie, AJ, A theorem of the complement and some new o-minimal structures, Sel. Math., 5, 4, 397-421 (1999) · Zbl 0948.03037 · doi:10.1007/s000290050052 |
| [38] | Wilkie, AJ, o-minimal structures, Astérisque, 326, 131-142 (2009) · Zbl 1197.03043 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
