Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



An algorithmic approach to the construction
of homomorphisms induced by maps in homology

Authors: Madjid Allili and Tomasz Kaczynski
Journal: Trans. Amer. Math. Soc. 352 (2000), 2261-2281
MSC (1991): Primary 55-04; Secondary 54C60, 54H20, 05B25
Published electronically: November 18, 1999
MathSciNet review: 1694277
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. E. Begle, The Vietoris mapping theorem for bicompact spaces, Ann. Math., 51 (1950), 534-543. MR 11:677b
  • 3. C. A. Delfinado, H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Computer Aided Geometric Design, 12 (1995), 771-784. MR 96h:55004
  • 4. 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. CMP 97:06
  • 5. T. K. Dey, H. Edelsbrunner, S. Guha, Computational Topology, Advances in discrete and computational geometry (South Hadley, MA, 1996), 109-143. CMP 99:05
  • 6. D. Dold, Lectures on algebraic topology, Springer-Verlag, Berlin-Heidelberg-New York, (1972). MR 96c:55001
  • 7. R. Ehrenborg, G. Hetyei, Generalizations of Baxter's Theorem and Cubical Homology, J. Combinatorial Theory, Series A, 69 (1995), 233-287. MR 96k:05041
  • 8. L. Górniewicz, Homological methods in fixed point theory of multi-valued map, Dissertationes Math. (Rozprawy Mat.) 129 (1976), 1-71. MR 52:15438
  • 9. C. S. Iliopoulos, Worst case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and Hermite and Smith normal forms of an integer matrix, SIAM J. Computing 18 (1989), 658-669. MR 91a:20065
  • 10. T. Kaczynski, M. Mrozek, Conley index for discrete multi-valued dynamical systems, Topology Appl. 65 (1995), 83-96. MR 97d:54066
  • 11. -, Stable index pairs for discrete dynamical systems, Canad. Math. Bull. 40 (1997), 448-455. MR 99g:54038
  • 12. T. Kaczynski, M. Mrozek, M. \'{S}lusarek, Homology computation by reduction of chain complexes, Comput. Math. Appl. 33 (1998), 59-70. MR 99a:18001
  • 13. T. Kaczynski, H. Karloff, K. Mischaikow, M. Mrozek, Introduction to Algebraic Topology: A Computational Perspective, book in progress.
  • 14. A. Lecki, Z. Szafraniec, An algebraic method for calculating the topological degree, Banach Center Publ. Vol. 35, Warsaw 1996, 73-83. MR 98b:55002
  • 15. W. S. Massey, A basic course in algebraic topology, Springer-Verlag, New York (1991). MR 92c:55001
  • 16. K. Mischaikow, Conley Index Theory, Dynamical Systems: Montecatini Terme 1994, eds. L. Arnold and C. Jones, Lecture Notes in Math. No. 1609, Springer 1995. MR 97a:58109
  • 17. K. Mischaikow, M. Mrozek, A. Szymczak, J. Reiss, From time series to symbolic dynamics: An algebraic topological approach, preliminary version.
  • 18. K. Mischaikow, M. Mrozek, Chaos in the Lorenz equations: a computer assisted proof, Bull. Amer. Math. Soc. (N.S.) 32 (1995), 66-72. MR 95e:58121
  • 19. K. Mischaikow, M. Mrozek, A. Szymczak, Chaos in the Lorenz equations: a computer assisted proof, Part III: the classical case. Preprint.
  • 20. M. Mrozek, Topological invariants, multivalued maps and computer assisted proofs in dynamics, Computers and Mathematics 32 (1996), 83-104. MR 97h:58144
  • 21. J. R. Munkers, Elements of algebraic topology, Addison-Wesley (1984). MR 85m:55001
  • 22. H. W. Siegberg, G. Skordev, Fixed point index and chain approximations, Pacific Journal of Mathematics 102, No. 2 (1982), 455-486. MR 84d:55003
  • 23. A. Szymczak, A combinatorial procedure for finding isolating neighbourhoods and index pairs, Proc. of the Royal Soc. of Edinburgh 127 A (1997), 1075-1088. MR 98i:58151
  • 24. P. Zgliczynski, Fixed points for iterations of maps, topological horseshoe and chaos, Top. Meth. in Nonlin. Anal. 8 (1996), 169-177. MR 98m:58106
  • 25. -, Computer assisted proofs of chaos in the Rössler equations and the Hénon map, Nonlinearity 10 (1997), 243-252. MR 98g:58120

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 55-04, 54C60, 54H20, 05B25

Retrieve articles in all journals with MSC (1991): 55-04, 54C60, 54H20, 05B25

Additional Information

Madjid Allili
Affiliation: Center for Dynamical Systems and Nonlinear Studies, School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332-0160

Tomasz Kaczynski
Affiliation: Département de Mathématiques et d’Informatique, Université de Sherbrooke, Sherbrooke, Québec J1K 2R1, Canada

Keywords: Algorithm, homology, representable map, Vietoris map
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.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society