An algorithmic approach to the construction of homomorphisms induced by maps in homology
HTML articles powered by AMS MathViewer
- by Madjid Allili and Tomasz Kaczynski PDF
- Trans. Amer. Math. Soc. 352 (2000), 2261-2281 Request permission
Abstract:
This paper is devoted to giving the theoretical background for an algorithm for computing homomorphisms induced by maps in homology. The principal idea is to insert the graph of a given continuous map $f$ into a graph of a multi-valued representable map $F$. The multi-valued representable maps have well developed continuity properties and admit a finite coding that permits treating them by combinatorial methods. We provide the construction of the homomorphism $F_*$ induced by $F$ such that $F_* = f_*$. The presented construction does not require subsequent barycentric subdivisions and simplicial approximations of $f$. The main motivation for this paper comes from the project of computing the Conley Index for discrete dynamical systems.References
- M. Allili, Une approche algorithmique pour le calcul de l’homologie de fonctions continues, Ph.D. thesis, Département de mathématique et d’informatique, Université de Sherbrooke, January 1999.
- Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
- Cecil Jose A. Delfinado and Herbert Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the $3$-sphere, Comput. Aided Geom. Design 12 (1995), no. 7, 771–784. Grid generation, finite elements, and geometric design. MR 1365107, DOI 10.1016/0167-8396(95)00016-Y
- T. K. Dey, S. Guha, Algorithms for manifolds and simplicial complexes in Euclidean 3-space, In Proc. 28th ACM Sympos. Theory Comput. (1996), 398–407.
- T. K. Dey, H. Edelsbrunner, S. Guha, Computational Topology, Advances in discrete and computational geometry (South Hadley, MA, 1996), 109–143.
- Albrecht Dold, Lectures on algebraic topology, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the 1972 edition. MR 1335915, DOI 10.1007/978-3-642-67821-9
- Richard Ehrenborg and Gábor Hetyei, Generalizations of Baxter’s theorem and cubical homology, J. Combin. Theory Ser. A 69 (1995), no. 2, 233–287. MR 1313897, DOI 10.1016/0097-3165(95)90053-5
- Lech Górniewicz, Homological methods in fixed-point theory of multi-valued maps, Dissertationes Math. (Rozprawy Mat.) 129 (1976), 71. MR 394637
- Costas S. Iliopoulos, Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM J. Comput. 18 (1989), no. 4, 658–669. MR 1004789, DOI 10.1137/0218045
- T. Kaczynski and M. Mrozek, Conley index for discrete multi-valued dynamical systems, Topology Appl. 65 (1995), no. 1, 83–96. MR 1354383, DOI 10.1016/0166-8641(94)00088-K
- Tomasz Kaczynski and Marian Mrozek, Stable index pairs for discrete dynamical systems, Canad. Math. Bull. 40 (1997), no. 4, 448–455. MR 1611339, DOI 10.4153/CMB-1997-053-2
- T. Kaczyński, M. Mrozek, and M. Ślusarek, Homology computation by reduction of chain complexes, Comput. Math. Appl. 35 (1998), no. 4, 59–70. MR 1604791, DOI 10.1016/S0898-1221(97)00289-7
- T. Kaczynski, H. Karloff, K. Mischaikow, M. Mrozek, Introduction to Algebraic Topology: A Computational Perspective, book in progress.
- Andrzej Łęcki and Zbigniew Szafraniec, An algebraic method for calculating the topological degree, Topology in nonlinear analysis (Warsaw, 1994) Banach Center Publ., vol. 35, Polish Acad. Sci. Inst. Math., Warsaw, 1996, pp. 73–83. MR 1448427
- William S. Massey, A basic course in algebraic topology, Graduate Texts in Mathematics, vol. 127, Springer-Verlag, New York, 1991. MR 1095046
- Konstantin Mischaikow, Conley index theory, Dynamical systems (Montecatini Terme, 1994) Lecture Notes in Math., vol. 1609, Springer, Berlin, 1995, pp. 119–207. MR 1374109, DOI 10.1007/BFb0095240
- K. Mischaikow, M. Mrozek, A. Szymczak, J. Reiss, From time series to symbolic dynamics: An algebraic topological approach, preliminary version.
- Konstantin Mischaikow and Marian Mrozek, Chaos in the Lorenz equations: a computer-assisted proof, Bull. Amer. Math. Soc. (N.S.) 32 (1995), no. 1, 66–72. MR 1276767, DOI 10.1090/S0273-0979-1995-00558-6
- K. Mischaikow, M. Mrozek, A. Szymczak, Chaos in the Lorenz equations: a computer assisted proof, Part III: the classical case. Preprint.
- M. Mrozek, Topological invariants, multivalued maps and computer assisted proofs in dynamics, Comput. Math. Appl. 32 (1996), no. 4, 83–104. MR 1403460, DOI 10.1016/0898-1221(96)00127-7
- James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
- H. W. Siegberg and G. Skordev, Fixed point index and chain approximations, Pacific J. Math. 102 (1982), no. 2, 455–486. MR 686564
- Andrzej Szymczak, A combinatorial procedure for finding isolating neighbourhoods and index pairs, Proc. Roy. Soc. Edinburgh Sect. A 127 (1997), no. 5, 1075–1088. MR 1475647, DOI 10.1017/S0308210500026901
- Piotr Zgliczyński, Fixed point index for iterations of maps, topological horseshoe and chaos, Topol. Methods Nonlinear Anal. 8 (1996), no. 1, 169–177. MR 1485762, DOI 10.12775/TMNA.1996.026
- Piotr Zgliczyński, Computer assisted proof of chaos in the Rössler equations and in the Hénon map, Nonlinearity 10 (1997), no. 1, 243–252. MR 1430751, DOI 10.1088/0951-7715/10/1/016
Additional Information
- Madjid Allili
- Affiliation: Center for Dynamical Systems and Nonlinear Studies, School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332-0160
- Email: allili@math.gatech.edu
- Tomasz Kaczynski
- Affiliation: Département de Mathématiques et d’Informatique, Université de Sherbrooke, Sherbrooke, Québec J1K 2R1, Canada
- Email: kaczyn@dmi.usherb.ca
- Received by editor(s): June 2, 1997
- Received by editor(s) in revised form: January 14, 1998
- Published electronically: November 18, 1999
- Additional Notes: The second author was supported by grants from NSERC of Canada and FCAR of Quebec.
- © Copyright 2000 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 352 (2000), 2261-2281
- MSC (1991): Primary 55-04; Secondary 54C60, 54H20, 05B25
- DOI: https://doi.org/10.1090/S0002-9947-99-02527-1
- MathSciNet review: 1694277