()


@
Applied General Topology

c© Universidad Politécnica de Valencia

Volume 14, no. 1, 2013

pp. 61-72

A notion of continuity in discrete spaces and

applications

Valerio Capraro∗

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.

2010 MSC: Primary 52A01; Secondary 46L36.

Keywords: A-homotopy theory, ℓp-distortion, digital Jordan curve theorem.

1. Introduction, main results and motivations

The A-theory is a homotopy theory for locally finite connected graphs that
has been developed by Barcelo et alii in a recent series of three papers [4],[5],and
[6]. This theory is based on ideas that go back to the work of Atkin[2],[3] -
indeed, the letter A is in honour of Atkin - and that were already re-explored
in [12]. This theory is based on a notion of continuous path that makes sense
for all locally finite metric spaces1.

∗Supported by Swiss SNF Sinergia project CRSI22-130435.
1A metric space is called locally finite if every bounded set is finite.



62 V. Capraro

Definition 1.1. Let (X, d) be a locally finite metric space. Given x ∈ X,
denote by dN1(x) the smallest closed ball with the center x which contains at
least two points. A finite sequence of points in X, say x0, x1, . . . , xn−1, xn, is
called a continuous path if

xi ∈ dN1(xi−1) and xi−1 ∈ dN1(xi) for all i = 1 . . . n

A locally finite metric space is called path-connected if any pair of points can
be joined by a continuous path.

As we will show in the next sections, the main interest of this definition is
that it allows, on one hand, to bring down results from Topology of Manifolds
to locally finite spaces (as the Jordan curve theorem); on the other hand, it
allows to bring up results from Graph Theory to locally finite metric spaces (as
the P.N.Jolissaint-Valette inequality).

We now state our main results. For the exact definitions, we refer the reader
to the next sections.

Theorem 1.2. Let γ be a simple circuit in Z2. Then Z2 \ γ has two path
connected components, one finite and one infinite, and γ is the boundary of
each of them.

The reason behind the choice of this application is that the Jordan curve
theorem in Z2 is of interest in Digital Geometry, a branch of Theoretical Com-
puter Science that studies, roughly speaking, the geometry of the screen of a
computer. The basic idea is that the screen of a computer is modeled by the
grid Z2, whose points are pixels, and one has to turn on some pixels in order to
form an image. In this context, the importance of a Jordan curve theorem is
clear. For an introduction to Digital Geometry, see the beautiful introduction
and Sec. 1.2 of Melin’s Ph.D. thesis[15]; references on digital version of the
Jordan curve theorem include, for instance, [10],[16],[7] and references therein.
Our proposal of a Jordan curve theorem is different from those ones, since it
is based on a new definition of a simple curve and on a different notion of
connectivity. The same notion of connectivity has been considered in [11] and
[17], where also versions of the Jordan curve theorem have been presented. In
particular, in [11] a Jordan curve theorem has been proved for the so-called
strict curves. We will see that every strict curve is also simple and that there
are simple curves that are not strict (see Remark 2.2).

Our second main result is the following

Theorem 1.3. Let X be a locally finite metric space such that every path-
connected component Xi is finite. The ℓ

p-distortion of X has the following
lower bound

cp(X) ≥ sup
i

D(Xi)

2d(Xi)

(

|Xi|

|E(Xi)|λ
(p)
1

)
1

p

(1.1)

This inequality was recently proved for finite connected graphs by Pierre-
Nicolas Jolissaint and Alain Valette (see [9], Theorem 1). Here we propose a



A notion of continuity in discrete spaces and applications 63

generalization that holds for the class of locally finite spaces such that each
path-connected component is finite. Of course, this class contains all finite
connected graphs.

2. The Jordan curve theorem in Z2

The classical Jordan curve theorem states that a simple closed curve γ in
R

2 separates R2 in two path-connected components, one bounded and one
unbounded and γ is the boundary of each of these components. In this section
we want to prove an analogous result in Z2 with the Euclidean distance. One is
tempted to define a simple circuit in Z2 as a continuous circuit x0x1 . . . xn−1xn
such that the xi’s are pairwise distinct for i ∈ {0, 1, . . . , n − 1} and x0 = xn.
With this definition the Jordan curve theorem would be false: consider the
following continuous circuit:

(0, 0)(0, −1)(1, −1)(2, −1)(2, 0)(2, 1)(1, 1)(1, 2)(0, 2)(−1, 2)(−1, 1)(−1, 0)(0, 0).

This circuit is simple in the previous sense, but it separates the grid Z2 in
three path-connected components: in some sense, this circuit behaves like the
8-shape curve in R2, which is not simple. A discrete analogue of a simple circuit
is, in our opinion, something different.

First of all, we need to introduce some notation. Let (x, y) ∈ Z2,

• dB1(x, y) denotes the set {(x + 1, y), (x − 1, y), (x, y − 1), (x, y + 1)},
• dB2(x, y) denotes the set {(x−1, y−1), (x−1, y+1), (x+1, y+1), (x+
1, y − 1)}.

Definition 2.1. A simple circuit in Z2 is a continuous path x0x1 . . . xn−1xn
such that

• The xi’s are pairwise distinct for i ∈ {0, 1, . . . , n − 1} and x0 = xn.
• Whenever xi ∈ dB2(xj), for j > i, then j = i + 2 and

xi+1 ∈ dB1(xi) ∩ dB1(xj)

Remark 2.2. A Jordan curve theorem in Z2 with the same notion of connec-
tivity as ours has been proved in [11] for the so-called strict circuits. They are
circuits γ = x0x1 . . . xn−1xn such that |dB2(xi)| = 2, for all i. Consequently,
every strict circuit is also simple. The converse is not true, since the circuit

γ = (1, 0)(1, 1)(0, 1)(−1, 1)(−1, 0)(−1, −1)(0, −1)(1, −1)(1, 0)

is simple but not strict, since |dB2(1, 0)| = 3.

For simplicity, we divide the proof of the Jordan curve theorem in Z2 in two
parts: in Theorem 2.3, we prove that Z2\γ has two path-connected components,
one finite and one infinite; in Proposition 2.4, after defining a good notion of
boundary, we prove that γ is the boundary of each of these path-connected
components.



64 V. Capraro

Theorem 2.3. Let γ be a simple circuit in Z2 not containing squares2. Then
Z
2 \ γ has two path connected components, one finite and one infinite.

Proof. Embed canonically Z2 into R2 and construct the following subset γ̃ in
R

2:

• γ̃ contains all points contained by γ.
• If two points of γ are adjacent vertices of a square, then γ̃ contains the
segment connecting these two points.

It is easy to see that γ̃ can be realized as a closed curve in R2 which is simple in
the standard sense. Indeed it is made by sides of squares, without repetitions.
By the classical Jordan curve theorem, let Int(γ̃) and Ext(γ̃) be the two path
connected components of R2 \ γ̃. Define Int(γ) = Int(γ̃) ∩ Z2 and Ext(γ) =
Ext(γ̃) ∩ Z2 and let us prove that these are exactly the two path connected
components of Z2 \ γ. Of course, it is enough to show that both Int(γ) and
Ext(γ) are path-connected, since the sets Int(γ), Ext(γ), γ form a partition
of Z2. So, let us start proving that Int(γ) is path connected. Since Int(γ̃) is
bounded, we need first to prove that Int(γ) is not empty. Let (x0, y0) ∈ Int(γ̃).
By continuity, we may suppose that (x0, y0) is in the interior of some square
with vertices in Z2. Let (x1, y1), (x1 + 1, y1), (x1 + 1, y1 + 1), (x1, y1 + 1) be
such vertices. Observe that at least one of these points must belong outside of
γ, since γ does not contain squares. This point has to belong also in Int(γ̃),
since the segment line connecting this point to (x0, y0) does not intersect γ̃.
Therefore, we have found a point in Int(γ). Now we prove that Int(γ) is path-

connected. Let (w0, z0), (w1, z1) ∈ Int(γ) and let δ̃ be a continuous path in
Int(γ̃) connecting them. Let Ii, i = 0, . . . N, be a covering of the interval [0, 1],
made of intervals Ii = [ai, bi], such that

• a0 = 0 and bN = 1,
• ai < ai+1, for all i,
• ai = bi−1, for all i = 1, . . . N,
• For all i = 0 . . . , N, γ̃|Ii belongs to some closed squares with vertices
in Z2,

• For all i = 0, . . . , N both γ̃(ai) and γ̃(bi) belongs to the side of some
square with vertices in Z2.

It is easy to construct explicitly such a covering, making use of continuity of γ̃
and compactness of the interval [0, 1]. Now, lift δ̃ to a discrete path {(ck, dk)}
as follows:

• Of course, define (c0, d0) = δ̃(0) = (w0, z0),

• If δ̃( 1
N
) ∈ Z2, we have two sub-cases:

2A square in Z2 is just a set of four points of the shape (x0, y0), (x0 + 1, y0), (x0 +
1, y0 + 1), (x0, y0 + 1). This hypothesis has an explanation in terms of A-theory. In this
theory, squares are homotopic equivalent to one point and therefore they do not contribute
in disconnecting the grid Z2.



A notion of continuity in discrete spaces and applications 65

– If δ̃( 1
N
) is adjacent3 to (w0, z0), define (c1, d1) = δ̃(

1
N
),

– If If δ̃( 1
N
) is opposite to (w0, z0), first define (c2, d2) = δ̃(

1
N
) and

then observe that the two points of dB1(c0, d0) ∩ dB1(c2, d2) can-
not belong both to γ, since γ is simple. Let, (c1, d1) be the one
that does not belong to γ. To see that it is the right choice, it
suffices to observe that (c1, d1) /∈ Ext(γ̃). To see this, just observe
that the segment line connecting (c1, d1) to (c2, d2) does not in-
tersect γ̃ and therefore (c1, d1) /∈ Ext(γ̃).

Now suppose that δ̃( 1
N
) /∈ Z2. Since δ̃( 1

N
) ∈ Int(γ̃), in particular

δ̃( 1
N
) /∈ γ̃. It follows that there is at least one extremal vertex of

the (unique) side of Z2 containing δ̃( 1
N
) which does not belong to γ

(otherwise, by construction of γ̃, we would have δ̃( 1
N
) ∈ γ̃). This vertex,

now denoted by (c2, d2) has to belong to Int(γ), since the segment line

connecting (c2, d2) to δ̃(
1
N
) does not intersect γ̃. Now, if (c2, d2) is

adjacent to (c0, d0), we can just define (c1, d1) := (c2, d2); otherwise,
observe that one of the two points in dB1(c0, d0) ∩ dB1(c2, d2) has to
belong to Int(γ) and we can pick (c1, d1) to be one of them.

• And so on, for all i up to N.

In a similar way one shows that Ext(γ) is path-connected. �

Now, in order to have a complete analogue of the classical Jordan curve the-
orem we need to prove a discrete analogue of the fact that γ is the boundary
of each of the path-connected components of R2 \ γ. In order to do that, we
use a property that in the classical setting is implied by injectivity.

In order to describe this property, let γ be a simple circuit in R2 in classical
sense. Let Int(γ) be the bounded path-connected component of R2 \ γ. For
any point (x0, y0) ∈ Int(γ), define four points as follows

• (x+0 , y0) is the first point where the horizontal half-line x ≥ x0, y = y0,
intersects γ,

• (x−0 , y0) is the first point where the horizontal half-line x ≤ x0, y = y0,
intersects γ,

• (x0, y
+
0 ) is the first point where the vertical half-line x = x0, y ≥ y0,

intersects γ,
• (x0, y

−
0 ) is the first point where the vertical half-line x = x0, y ≤ y0,

intersects γ.

Making this procedure for each point belonging to the path-connected com-
ponent containing (x0, y0), we get the whole γ. Observe that this would have
been false if γ were not simple. Our definition of simplicity is exactly the one
that makes this procedure working in our discrete world of Z2. Indeed, if now

3Recall that we are working inside a square and therefore adjacent vertices are exactly
the extremal point of a side of the square and opposite vertices are the extremal points of a
diagonal of the square.



66 V. Capraro

γ is a simple circuit in Z2, the previous construction gives a set which is in
general smaller than γ, because of angles, but, if γ is simple, it can be com-
pleted without ambiguity. Formally, given a point (x0, y0) ∈ Int(γ), construct
four points as before and denote by A the set of points obtained by making this
procedure for all points belonging to the path-connected component containing
(x0, y0). Now, if (x1, y1), (x2, y2) ∈ A are opposite vertices of some square, our
hypothesis that γ is simple and does not contain squares, tells us that there
is a unique common adjacent point to both (x1, y1), (x2, y2) belonging to γ.

Denote by Int(γ) the set obtained adding to A all these angle points. By an

analogous construction starting from (x0, y0) ∈ Ext(γ), we may define Ext(γ).

The following proposition is now straightforward and concludes our proposal
of a discrete analogue of the Jordan curve theorem in Z2.

Proposition 2.4. Let γ be a simple circuit in Z2 that does not contain squares.
Then

Int(γ) = Ext(γ) = γ

Proof. Just observe that Int(γ) and Ext(γ) are respectively the boundary of
Int(γ̃) and Ext(γ̃), where γ̃ is constructed as in the proof of Theorem 2.3. �

3. P. N. Jolissaint-Valette’s inequality for finite metric spaces

The theory of (approximate) embedding of metric spaces in some other
well-understood metric space, as a Banach space or a Hilbert space, is now
a widely explored field of research, after the breakthrough papers of Linial-
London-Rabinovich[13] and Yu[18], that found relations among it, Theoretical
Computer Science and K-theory of C∗-algebras. One of the most basic notions
in this theory is the notion of ℓp-distortion, which measures how badly a metric
space can be embedded in an ℓp-space in a bi-lipschitz way.

For the convenience of the reader we recall that a bi-lipschitz embedding of
a metric space (X, d), in this context, is a mapping F : X → ℓp such that there
are constants C1, C2 such that for all x, y ∈ X one has

C1d(x, y) ≤ dp(F(x), F(y)) ≤ C2d(x, y)

where dp stands for the ℓ
p-distance. It is clear that F is injective and so we

can consider F −1 : F(X) → X. Therefore, the following notation makes sense,

||F ||Lip = sup
x 6=y

dp(F(x), F(y))

d(x, y)

and

||F −1||Lip = sup
x 6=y

d(x, y)

dp(F(x), F(y))

The product ||F ||Lip||F
−1||Lip is called distortion of F and denoted by Dist(F).



A notion of continuity in discrete spaces and applications 67

Definition 3.1. The ℓp-distortion of a metric space X is the following number

cp(X) = inf {Dist(F) : F is a bi-lipschitz embedding}(3.1)

In [9] (Theorem 1 and Proposition 3), Pierre-Nicolas Jolissaint and Alain
Valette proved that for finite graphs the following inequality holds:

cp(X) ≥
D(X)

2

(

|X|

|E|λ
(p)
1

)
1

p

(3.2)

where E denotes the edge set and

D(X) = max
α∈Sym(X)

min
x∈X

d(x, α(x))(3.3)

We want to extend this inequality to at least all finite metric spaces. Let
(X, d) be a locally finite metric space and let X1, . . . Xn be the partition of X in
path-connected components. The basic idea is clearly to apply P.N.Jolissaint-
Valette’s inequality on each of them, but unfortunately this application is not
straightforward, since a path-connected component might not look like a graph
(think, for instance, of the space [−n, n]2 \ {(0, 0)} ⊆ Z2 equipped with the
metric induced by the standard embedding into R2). So we have to be a bit
careful to apply P.N.Jolissaint-Valette’s argument.

Remark 3.2. Since the ℓp-distortion does not depend on rescaling the metric
and since we are going to work on each path-connected component separately,
we can suppose that each Xi is in normal form

4.

Since we are going to work on a fixed path-connected component, let us
simplify the notation assuming directly that X is finite path-connected metric
space in normal form. At the end of this section it will be easy to put together
all path-connected components.

Let x, y ∈ X, x 6= y and let x0x1 . . . xn−1xn be a continuous path joining
x and y of minimal length n. Denote by s the floor of d(x, y), i.e. s is the
greatest positive integer smaller than or equal d(x, y). Notice that s ≥ 1, since
X is in normal form. Denote by P(x, y) the set of coverings P = {p1, . . . , ps}
of the set {0, 1, . . . , n} such that5

• If a ∈ pi and b ∈ pi+1, then a ≤ b,
• the greatest element of pi is equal to the smallest element of pi+1.

We denote by p−i and p
+
i respectively the smallest and the greatest element of

pi.

4Let (X, d) be a locally finite path-connected metric space. Given x ∈ X, let Rx be
the radius of the smallest closed ball with the center x containing at least two points. It is
straightforward to prove that Rx does not depend on x and it is called step of the space.
We say that a locally finite path-connected metric space is in normal form if the metric is
normalized in such a way that the step is 1.

5Observe that each pi is a subset of {0, 1, . . . , n}.



68 V. Capraro

Now we introduce the following set

E(X) =
{

(e−, e+) ∈ X × X : ∃x, y ∈ X, p ∈ P(x, y) : e− = p−i , e
+ = p+i

}

(3.4)

Remark 3.3. If X = (V, E) is a finite connected graph equipped with the
shortest path metric, then E(X) = E. Indeed in this case s = n and so the
only coverings belonging to P(x, y) have the shape pi = {xi−1, xi}, where the
xi’s are taken along a shortest path joining x and y.

We define a metric analogue of the p-spectral gap: for 1 ≤ p < ∞, we set

λ
(p)
1 = inf

{
∑

e∈E(X) |f(e
+) − f(e−)|p

infα∈R
∑

x∈X
|f(x) − α|p

}

(3.5)

where the infimum is taken over all functions f ∈ ℓp(X) which are not
constant.

Lemma 3.4. Let (X, d) be a finite path-connected metric space in normal form.

(1) For any permutation α ∈ Sym(X) and F : X → ℓp(N), one has
∑

x∈X

||F(x) − F(α(x))||pp ≤ 2
p
∑

x∈X

||F(x)||pp

(2) For any bi-lipschitz embedding F : X → ℓp(N), there is another bi-
lipschitz embedding G : X → ℓp(N) such that ||F ||Lip||F

−1||Lip =
||G||Lip||G

−1||Lip and

∑

x∈X

||G(x)||pp ≤
1

λ
(p)
1

∑

e∈E(X)

||G(e+) − G(e−)||pp

Proof.

(1) This proof is absolutely the same as the proof of Lemma 1 in [9].
(2) Observe that the construction of G made in [8] is purely algebraic and

so we can apply it. The inequality just follows from our definition of

λ
(p)
1 .

�

Now we have to prove a version for metric spaces of a useful lemma already
proved by Linial and Magen for finite connected graph (see [14], Claim 3.2).
We need to introduce a number that measures how far is the metric space to
be a graph. We set

d(X) = max
e∈E(X)

d(e−, e+)(3.6)

We have told that d(X) measures how far X is far from being a graph.
Indeed, the following proposition holds:



A notion of continuity in discrete spaces and applications 69

Proposition 3.5. The followings are equivalent:

(1) d(X) = 1,
(2) The distance of any two points x, y ∈ X is exactly the length of the

shortest path connecting x, y

Proof. In one sense the thesis is trivial: if X is a finite graph, then E(X) = E
(by Remark 3.3) and d(X) = 1, since the space is supposed to be in nor-
mal form. Conversely, suppose that d(X) = 1, choose two distinct points
x, y ∈ X and let x0x1 . . . xn−1xn be a continuous path of minimal length
such that x0 = x and xn = y. Of, course s ≤ d(x, y) ≤ n. So, it suf-
fices to prove that s = n. In order to do that, suppose that s < n and
observe that every p ∈ P(x, y) would contain some pi containing at least
three points p−i = xi−1, xi, xi+1 = p

+
i (we suppose that they are exactly three,

since the general case is similar). Since X is in normal form, it follows that
d(xi−1, xi) = d(xi, xi+1) = 1. Now, suppose that d(X) = 1, it follows that also
d(xi−1, xi+1) = 1 and then the path x0 . . . xi−1xi+1 . . . xn is still a continuous
path connecting x with y, contradicting the minimality of the length of the
previous path. �

We are now able to prove the generalization of Linial-Magen’s lemma that
we need.

Lemma 3.6. Let (X, d) be a finite path-connected metric space in normal form
and f : X → R. Then

max
x 6=y

|f(x) − f(y)|

d(x, y)
≤ max

e∈E(X)
|f(e+) − f(e−)| ≤ d(X) max

x 6=y

|f(x) − f(y)|

d(x, y)
(3.7)

Proof. Let us prove only the first inequality, since the second will be trivial a
posteriori. Let x, y ∈ X where the maximum in the left hand side is attained
and let x0x1 . . . xn−1xn be a continuous path of minimal length connecting x
with y. Let p ∈ P(x, y) and let k be an integer such that

|f(p+
k
) − f(p−

k
)| ≥ |f(p+i ) − f(p

−
i )|

for all i. It follows

|f(p+
k
) − f(p−

k
)| =

s|f(p+
k
) − f(p−

k
)|

s
≥

∑s

i=1 |f(p
+
i
) − f(p−

i
)|

s
≥

Now we use the fact that the covering p is made exactly by s sets. It follows that
x and y belong to the union of the pi’s and we can use the triangle inequality
and obtain

≥
|f(x) − f(y)|

s
≥

|f(x) − f(y)|

d(x, y)

�

We are now ready to prove the main result of this section.



70 V. Capraro

Theorem 3.7. Let (X, d) be a finite path-connected metric space in normal
form. For all 1 ≤ p < ∞, one has

cp(X) ≥
D(X)

2d(X)

(

|X|

|E(X)|λ
(p)
1

)
1

p

(3.8)

where

D(X) = max
α∈Sym(X)

min
x∈X

d(x, α(x))(3.9)

Proof. Let G be a bi-lipschitz embedding which verifies the second condition
in Lemma 3.4 and let α be a permutation of X without fixed points. Let
ρ(α) = minx∈X d(x, α(x)). One has

1

||G−1||
p
Lip

= min
x 6=y

||G(x) − G(y)||pp
d(x, y)p

≤ min
x∈X

||G(x) − G(α(x))||pp
d(x, α(x))p

≤
1

ρ(α)p
min
x∈X

||G(x) − G(α(x))||pp

≤
1

ρ(α)p|X|

∑

x∈X

||G(x) − G(α(x))||pp

Now apply the first statement of Lemma 3.4:

≤
2p

ρ(α)p|X|

∑

x∈X

||G(x)||pp

Now apply the second statement of Lemma 3.4:

≤
2p

ρ(α)p|X|λ
(p)
1

∑

e∈E(X)

||G(e+) − G(e−)||pp ≤
2p|E(X)|

ρ(α)p|X|λ
(p)
1

max
e∈E(X)

||G(e+) − G(e−)||pp

Now apply Lemma 3.6:

≤
2pd(X)p|E(X)|||G||

p
Lip

ρ(α)p|X|λ
(p)
1

Now recall the definitions in Equation 3.1 and 3.9 and just re-arrange the terms
to get the desired inequality. �

Notice that d(X) ≥ 1 and so the inequality gets worse when the metric space
is not a graph.



A notion of continuity in discrete spaces and applications 71

Corollary 3.8. Let X be a metric space such that every path-connected com-
ponent Xi is finite. One has

cp(X) ≥ sup
i

D(Xi)

2d(Xi)

(

|Xi|

|E(Xi)|λ
(p)
1

)
1

p

(3.10)

Proof. Just observe that if Xi is a partition of X then cp(X) ≥ supi cp(Xi). �

Acknowledgements. We would like to thank Pierre-Nicolas Jolissaint for
useful comments on Sec. 3 and a referee for helpful comments to improve the
exposition of the paper.

References

[1] 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.

[2] R. Atkin, An algebra of patterns on a complex, I, Intern. J. Man-Machine Studies 6
(1974), 285–307.

[3] R. Atkin, An algebra of patterns on a complex, II, Intern. J. Man-Machine Studies 8
(1976), 448–483.

[4] 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.

[5] H. Barcelo and Laubenbacher R. Perspectives in A-homotopy theory and its applications,
Discrete Mathematics 298 (2005), 39–61.

[6] E. Babson, H. Barcelo, M. de Longueville and R. Laubenbacher, Homotopy theory of
graphs, J. Alg. Comb. 24 (2006), 31–44.

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

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

[9] P. N. Jolissaint and A. Valette, ℓp-distortion and p-spectral gap of finite regular graphs,
preprint (arXiv:1110.0909).

[10] E. Khalimsky, R. Kopperman and P. R. Meyer, Computer graphics and connected topolo-
gies on finite ordered sets, Topology Appl. 36 (1990), 1–17.

[11] O. Kiselman, Digital Jordan curve theorems, Lecture Notes in Computer Science 1953
(2000), 46–56.

[12] X. Kramer and R. Laubenbacher, Combinatorial homotopy of simplicial complexes and
complex information networks, in: D.Cox, B.Sturmfels (Eds.), Applications of Compu-
tational Algebraic Geometry, vol. 53, Proceedings of the Symposium in Applied Mathe-
matics, American Mathematical Society, Providence, RI, 1998.

[13] N. Linial, E. London and Yu. Rabinovich, The geometry of graphs and some of its
algorithmic applications, Combinatorica 15 (1995), 215–245.

[14] 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.

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



72 V. Capraro

[16] J. S̆lapal, 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).

[17] J. S̆lapal, Digital Jordan curves, Topology Appl. 153 (2006), 3255–3264.
[18] 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.

(Received March 2012 – Accepted October 2012)

V. Capraro (valerio.capraro@unine.ch)
University of Neuchatel, Switzerland.


	A notion of continuity in discrete spaces and[6pt] applications. By V. Capraro