A notion of continuity in discrete spaces and applications

Valerio Capraro

doi:10.4995/agt.2013.1618

Authors

Valerio Capraro University of Neuchatel

DOI:

https://doi.org/10.4995/agt.2013.1618

Keywords:

A-homotopy theory, â„“p-distortion, Digital Jordan curve theorem

Abstract

We propose a notion of continuous path for locally finite metric spaces, taking inspiration from the recent development of A-theory for locally finite connected graphs. We use this notion of continuity to derive an analogue in Z2 of the Jordan curve theorem and to extend to a quite large class of locally finite metric spaces (containing all finite metric spaces) an inequality for the â„“p-distortion of a metric space that has been recently proved by Pierre-Nicolas Jolissaint and Alain Valette for finite connected graphs.

Downloads

Download data is not yet available.

References

R. Ayala, E. Domínguez, A. R. Francés and A. Quintero, Determining the components of the complement of a digital (n âˆ’ 1)-manifold in Zn, Discrete Geometry for Computer Imagery; Lecture Notes on Computer Science, vol. 11 76/1996 (1996), 163–176.

R. Atkin, An algebra of patterns on a complex, I, Intern. J. Man-Machine Studies 6 (1974), 285–307. http://dx.doi.org/10.1016/S0020-7373(74)80024-6

R. Atkin, An algebra of patterns on a complex, II, Intern. J. Man-Machine Studies 8 (1976), 448–483. http://dx.doi.org/10.1016/S0020-7373(76)80015-6

H. Barcelo, X. Kramer, R. Laubenbacher and C. Weaver, Foundations of a connectivity theory dor simplicial complexes, Adv. in Appl. Math. 26 (2001), 97–128. http://dx.doi.org/10.1006/aama.2000.0710

H. Barcelo and Laubenbacher R. Perspectives in A-homotopy theory and its applications, Discrete Mathematics 298 (2005), 39–61. http://dx.doi.org/10.1016/j.disc.2004.03.016

E. Babson, H. Barcelo, M. de Longueville and R. Laubenbacher, Homotopy theory of graphs, J. Alg. Comb. 24 (2006), 31–44. http://dx.doi.org/10.1007/s10801-006-9100-0

E. Bouassida, The Jordan curve theorem in the Khalimsky plane, Appl. Gen. Top. 9, no. 2 (2008), 253–262.

R. I. Grigorchuk and P. W. Nowak, Diameters, distorsion and eigenvalues, European Journal of Combinatorics, to appear (arXiv:1005.2560v3).

P. N. Jolissaint and A. Valette, â„“p-distortion and p-spectral gap of finite regular graphs, preprint (arXiv:1110.0909).

E. Khalimsky, R. Kopperman and P. R. Meyer, Computer graphics and connected topologies on finite ordered sets, Topology Appl. 36 (1990), 1–17. http://dx.doi.org/10.1016/0166-8641(90)90031-V

O. Kiselman, Digital Jordan curve theorems, Lecture Notes in Computer Science 1953 (2000), 46–56. http://dx.doi.org/10.1007/3-540-44438-6_5

X. Kramer and R. Laubenbacher, Combinatorial homotopy of simplicial complexes and complex information networks, in: D.Cox, B.Sturmfels (Eds.), Applications of Computational Algebraic Geometry, vol. 53, Proceedings of the Symposium in Applied Mathematics, American Mathematical Society, Providence, RI, 1998.

N. Linial, E. London and Yu. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), 215–245. http://dx.doi.org/10.1007/BF01200757

N. Linial and A. Magen, Least-distortion Euclidean embeddings of graphs and some of its algorithmic applications, J. Combin. Theory Ser. B 79, no. 2 (2000), 157–171. http://dx.doi.org/10.1006/jctb.2000.1953

E. Melin, Digital Geometry and Khalimsky spaces, PhD thesis (http://uu.diva-portal.org/smash/get/diva2:171330/FULLTEXT01).

J. Slapal, A digital analogue of the Jordan curve theorem, Journal Discrete Applied Mathematics - The 2001 International Workshop on Combinatorial Image Analysis (IW-CIA) 2001, vol. 139, Issue 1-3, (2004).

J. Slapal, Digital Jordan curves, Topology Appl. 153 (2006), 3255–3264. http://dx.doi.org/10.1016/j.topol.2005.10.011

G. Yu, The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space, Invent. Math. 139, no. 1 (2000) 201–240. http://dx.doi.org/10.1007/s002229900032