A notion of continuity in discrete spaces and applications

Valerio Capraro


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.


A-homotopy theory; ℓp-distortion; Digital Jordan curve theorem

Full Text:



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

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM


Cited-By (articles included in Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Discrete homology theory for metric spaces
Hélène Barcelo, Valerio Capraro, Jacob A. White
Bulletin of the London Mathematical Society  vol: 46  issue: 5  first page: 889  year: 2014  
doi: 10.1112/blms/bdu043

Esta revista se publica bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Universitat Politècnica de València

e-ISSN: 1989-4147   https://doi.org/10.4995/agt