KIRSZBRAUN-TYPE THEOREMS FOR GRAPHS

NISHANT CHANDGOTIA, IGOR PAK, AND MARTIN TASSY

arXiv:1710.11007v3 [math.CO] 7 Oct 2018

Abstract. The classical Kirszbraun theorem says that all 1-Lipschitz functions f : A −→ Rn ,
A ⊂ Rn , with the Euclidean metric have a 1-Lipschitz extension to Rn . For metric spaces X, Y we
say that Y is X-Kirszbraun if all 1-Lipschitz functions f : A −→ Y , A ⊂ X, have a 1-Lipschitz
extension to X. We analyze the case when X and Y are graphs with the usual path metric. We
prove that Zd -Kirszbraun graphs are exactly graphs that satisfies a certain Helly’s property. We
also consider complexity aspects of these properties.

1. Introduction
Discretizing results in metric geometry is important for many applications, ranging from discrete
differential geometry to numerical methods. The discrete results are stronger as they typically
imply the continuous results in the limit. Unfortunately, more often than not, straightforward
discretizations fall apart; new tools and ideas are needed to even formulate these extensions; see
e.g. [BS08, Lin02] and [Pak09, §21–§24].
In this paper we introduce a new notion of G-Kirszbraun graphs, where G is vertex-transitive
graph. The idea is to discretize the classical Kirszbraun theorem in metric geometry [Kir34] (see
also [BL00, §1.2]). Our main goal is to explain the variational principle for the height functions
of tilings introduced by the third author in [Tas14] and further developed in [PST16, MT16] (see
Section 2); we also aim to lay a proper foundation for the future work.
Our second goal is to clarify the connection to the Helly theorem, a foundational result in convex
and discrete geometry [Hel23] (see also [DGK63, Mat02]). Graphs that satisfy the Helly’s property
has been intensely studied in recent years [BC08], and we establish a connection between two areas.
Roughly, we show that Zd -Kirszbraun graphs are somewhat rare, and are exactly the graphs that
satisfy the Helly’s property with certain parameters.

1.1. Main results. Let ℓ2 denote the usual Euclidean metric on Rn for all n. Given a metric
space X and a subset A, we write A ⊂ X to mean that the subset A is endowed with the restricted
metric from X. The Kirszbraun theorem says that for all A ⊂ (Rn , ℓ2 ), and all Lipschitz functions
f : A −→ (Rn , ℓ2 ), there is an extension to a Lipschitz function on Rn with the same Lipschitz
constant.
Recall now the Helly theorem: Suppose a collection of convex sets B1 , B2 , . . . , Bk satisfies the
property that every (n + 1)-subcollection has a nonempty intersection, then ∩Bi 6= ∅. Valentine
in [Val45] famously showed how the Helly theorem can be used to obtain the Kirszbraun theorem.
The connection between these two theorems is the key motivation behind this paper.
Given metric spaces X and Y , we say that Y is X-Kirszbraun if all A ⊂ X, every 1-Lipschitz
maps f : A −→ Y has a 1-Lipschitz extension from A to X. In this notation, the Kirszbraun
theorem says that (Rn , ℓ2 ) is (Rn , ℓ2 )-Kirszbraun.

2010 Mathematics Subject Classification. 05C60, 54C20.

Key words and phrases. Kirszbraun theorem, Helly theorem, graph homomorphism, Lipschitz map.
1
 Let m ∈ N and n ∈ N ∪ {∞}, n > m. Metric space X is said to have (n, m)-Helly’s property
if for every collection of closed balls B1 , B2 , . . . , Bn of radius ≥ 1 whenever every m-subcollection
has a nonempty intersection, we have ∩ni=1 Bi 6= ∅. Since balls in Rn with the Euclidean metric are
convex, the Helly theorem can be restated to say that (Rn , ℓ2 ) is (∞, n + 1)-Helly. Note that the
metric is important here, i.e. (Rn , ℓ∞ ) is (∞, 2)-Helly, see e.g. [DGK63, Pak09].
Given a graph H, we endow the set of vertices (also denoted by H) with the path metric. By Zd
we mean the Cayley graph of the group Zd with respect to standard generators. All graphs in this
paper are nonempty, connected and simple (no loops and multiple edges). The following is the
main result of this paper.
Theorem 1.1 (Main theorem). Graph H is Zd -Kirszbraun if and only if H is (2d, 2)-Helly.
Let Kn denote the complete graph on n-vertices. Clearly, Kn is G-Kirszbraun for all graphs G,
since all maps f : G −→ Kn are 1-Lipschitz. On the other hand, Z2 is not Z2 -Kirszbraun, see
Figure 1. This example can be modified to satisfy a certain extendability property, see §4.4.

b d' c'

c O a
a' b'

Figure 1. Here A = {a, b, c, d} ⊂ Z2 . Define f : a → a′ , b → b′ , c → c′ , d → d′ .

Then f : A → Z2 is 1-Lipschitz but not extendable to {O, a, b, c, d}.

1.2. Structure of the paper. We begin with a short non-technical Section 2 describing some
background results and ideas. In essence, it is a remark which is too long to be in the introduction.
It reflects the authors’ different points of view on the subject, which includes ergodic theory,
geometric combinatorics and discrete probability. While in principle this section it can be skipped,
we do recommend reading it as it motivates other parts of the paper.
We then proceed to prove Theorem 1.1 in Section 3. In Section 4, we present several extensions
and applications of the main theorem. These section is a mixed bag: we include a continuous
analogue of the main theorem (Theorem 4.1), the extension to larger integral Lipschitz constants
(Theorem 4.3), and the bipartite extension useful for domino tilings (Theorem 4.6). In a short
Section 5, we discuss computational aspects of the Zd -Kirszbraun property, motivated entirely by
applications to tilings. We conclude with final remarks and open problems in Section 6.

2. Motivation and background

A graph homomorphism from a graph G to a graph H is an adjacency preserving map between
the respective vertices. Let Hom(G, H) denote the set of all graph homomorphisms from G to H.
We refer to [HN04] for background on graph homomorphisms and connections to coloring and
complexity problems.
Our motivation comes from two very distinct sources:
2
 (1) Finding ‘fast’ algorithms to determine whether a given graph homomorphism on the bound-
ary of a box in Zd to H extends to the entire box.
(2) Finding a natural parametrization of the so-called ergodic Gibbs measures on space of graph
homomorphisms Hom(Zd , H) (see [She05, MT16]).
For (1), roughly, suppose we are given a certain simple set of tiles T, such as dominoes or
more generally bars {k × 1, 1 × ℓ}. It turns out, that T-tileability of a simply-connected region Γ
corresponds to existence of a graph homomorphism with given boundary conditions on ∂Γ. We refer
to [Pak03, Thu90] for the background, and to [PST16, Tas14] for further details. Our Theorem 5.2
is motivated by these problems.
For both these problems, the Zd -Kirszbraun property of the graph H (or a related graph) is
critical and motivates this line of research; the space of 1-Lipschitz maps is the same as the space of
graph homomorphisms if and only if H is reflexive, that is, every vertex has a self-loop. The study
of Kirszbraun-type theorems among metric spaces and its relationship to Helly-like properties is an
old one and goes back to the original paper by Kirszbraun [Kir34]. A short and readable proof is
given in [Fed69, p. 201]. This was later rediscovered in [Val45] where it was generalized to the cases
where the domain and the range are spheres in the Euclidean space or Hilbert spaces. The effort
of understanding which metric spaces satisfy Kirszbraun properties culminated in the theorem by
Lang and Schroeder [LS97] that identified the right curvature assumptions on the underlying spaces
for which the theorem holds.
In the metric graph theory, the research has focused largely on a certain universality property.
Formally, a graph is called Helly if it is (∞, 2)-Helly. An easy deduction, for instance following
the discussion in [DGK63, Page 153], shows that H is Helly if and only if for all graphs G, H is
G-Kirszbraun. Some nice characterizations of Helly graphs can be found in the survey [BC08, §3].
However, we are not aware of any other study of G-Kirszbraun graphs for fixed G.

3. Proof of the main theorem

3.1. Geodesic extensions. Let dH denote the path metric on the graph H. A walk γ in the
graph H of length k, is a sequence of k + 1 vertices (v0 , v1 , . . . , vk ), s.t. dH (vi , vi+1 ) ≤ 1, for all
0 ≤ i ≤ k − 1. We say that γ starts at v0 and ends at vk . A geodesic from vertex v to w in a
graph G is a walk γ from v to w of the shortest length.
Consider a graph G, a subset A ⊂ G and b ∈ G \ A. Define the geodesic extension of A with
respect to b as the following set:
Ext(A, b) := {a ∈ A : there does not exist a′ ∈ A \ {a} s.t. there is a
geodesic γ from a to b which passes through a′ }.

For example, let A ⊂ Z2 \ {(0, 0)}. If (i, j), (k, l) ∈ Ext(A, ~0) are elements of the same quadrant,
then |i| > |k| if and only if |j| < |l|.
Remark 3.1. If A ⊂ Zd be contained in the coordinate axes then |Ext(A, ~0)| ≤ 2d.
The notion of geodesic extension allows us to prove that certain 1-Lipschitz maps can be extended:
Proposition 3.2. Let A ⊂ G, map f : A −→ H be 1-Lipschitz, and let b ∈ G \ A. The map
f has a 1-Lipschitz extension to A ∪ {b} if and only if f |Ext(A,b) has a 1-Lipschitz extension to
Ext(A, b) ∪ {b}.
Proof. The forward direction of the proof is immediate because Ext(A, b) ⊂ A. For the backwards
direction let fe : Ext(A, b) ∪ {b} ⊂ G −→ H be a 1-Lipschitz extension of f |Ext(A,b) and consider the
3
map fˆ : A ∪ {b} ⊂ G −→ H given by
(
f (a) if a ∈ A
fˆ(a) := e
f (b) if a = b.
To prove that fˆ is 1-Lipschitz we need to verify that for all a ∈ A, dH (fˆ(a), fˆ(b)) ≤ dG (a, b). From
the hypothesis it follows for a ∈ Ext(A, b). Now suppose a ∈ A \ Ext(A, b). Then there exists
a′ ∈ Ext(A, b) such that there exists a geodesic from a to b passing through a′ . This implies that
dG (a, b) = dG (a, a′ ) + dG (a′ , b). But
dG (a, a′ ) ≥ dH (fˆ(a), fˆ(a′ )) = dH (f (a), f (a′ )) because f is 1-Lipschitz
dG (a′ , b) ≥ dH (fˆ(a′ ), fˆ(b)) = dH (fe(a′ ), fe(b)) because fe is 1-Lipschitz.
By the triangle inequality, the proof is complete. 

3.2. Helly’s property. Given a graph H, a vertex v ∈ H and n ∈ N denote by BnH (v), the ball of
radius n in H centered at v. We will now interpret the (n, 2)-Helly’s property in a different light.
Proposition 3.3. Let H be a graph satisfying the (n, 2)-Helly’s property. For all 1-Lipschitz maps
f : A ⊂ G −→ H and b ∈ G \ A such that |Ext(A, b)| ≤ n, there exists a 1-Lipschitz extension of f
to A ∪ {b}.
Proof. Consider the extension fe of f to the set A ∪ {b}, where fe(b) is any vertex in
\
BdHG (b,b′ ) (f (b′ ));
b′ ∈Ext(A,b)

the intersection is nonempty because |Ext(A, b)| ≤ n and for all a, a′ ∈ Ext(A, b), we have:


dH f (a), f (a′ ) ≤ dG (a, a′ ) ≤ dG (a, b) + dG (b, a′ )
which implies

BdHG (a,b) (f (a)) ∩ BdHG (b,a′ ) f (a′ ) 6= ∅.
The function fe|Ext(A,b)∪{b} is 1-Lipschitz, so Proposition 3.2 completes the proof. 
3.3. Examples. Let Cn and Pn denote the cycle graph and the path graph with n vertices, respec-
tively.
Corollary 3.4. All connected graphs are Pn –, Cn – and Z–Kirszbraun.
In the case when G = Pn , Cn or Z we have for all A ⊂ G and b ∈ G \ A, |Ext(A, b)| ≤ 2; the
corollary follows from Proposition 3.3 and the fact that all graphs are (2, 2)-Helly.
Let r = (r1 , r2 , . . . rn ) ∈ Nn . Denote by Tr the star-shaped tree with a central vertex b0 and n
disjoint walks of lengths r1 , . . . , rn emanating from it and ending in vertices b1 , b2 , . . . , bn .
Corollary 3.5. Graph H has the (n, 2)-Helly’s property if and only if H is Tr -Kirszbraun, for all
r ∈ Nn .
Proof. For all r ∈ Nn , A ⊂ Tr and b ∈ Tr \ {A}, we have |Ext(A, b)| ≤ n. Thus by Proposition
3.3 if H has the (n, 2)-Helly’s property then H is Tr -Kirszbraun. For the other direction, let H be
Tr -Kirszbraun for all r ∈ Nn . Suppose that
BrH1 (v1 ), BrH2 (v2 ), . . . , BrHn (vn )
are balls in H such that BrHi (vi )∩BrHj (vj ) 6= ∅ for all 1 ≤ i, j ≤ n. Then f : {b1 , b2 , . . . , bn } ⊂ Tr → H
given by f (bi ) := vi is 1-Lipschitz with a 1-Lipschitz extension fe : Tr → H. It follows that
T
fe(b0 ) ∈ n B H (vi ) proving that H has the (n, 2)-Helly’s property.
i=1 ri 
4
3.4. Proof of Theorem 1.1. We will first prove the “only if” direction. Let H be a graph which
is Zd -Kirszbraun. For all r ∈ N2d there is an isometry from Tr to Zd mapping the walks emanating
from the central vertex to the coordinate axes. Hence H is Tr -Kirszbraun for all r ∈ N2d . By
Corollary 3.5, we have proved the (2d, 2)-Helly’s property for H.
In the “if” direction, suppose H has the (2d, 2)-Helly’s property. We need to prove that for all
A ⊂ Zd , every 1-Lipschitz maps f : A → H has a 1-Lipschitz extension. It is sufficient to prove
this for finite subsets A. We proceed by induction on |A|. Namely, we prove the following property
St(n):
Let f : A ⊂ Zd −→ H be 1-Lipschitz with |A| = n. Let b ∈ Zd \ A. Then the function f has
a 1-Lipschitz extension to A ∪ {b}.
We know St(n) for n ≤ 2d by the (2d, 2)-Helly’s property. Let us assume St(n) for some n ≥ 2d; we
want to prove St(n + 1). Let f : A −→ H, A ⊂ Zd , be 1-Lipschitz with |A| = n + 1 and b ∈ Zd \ A.
Without loss of generality assume that b = ~0. Also assume that Ext(A, ~0) = A; otherwise we can
use the induction hypothesis and Proposition 3.2 to obtain the required extension to A ∪ {~0}.
We will prove that there exists a set A e ⊂ Zd and a 1-Lipschitz function fe : A
e −→ H, such that
(1) If fe has an extension to A
e ∪ {~0} then f has an extension to A ∪ {~0}.
e e ≤ 2d.
(2) Either the set A is contained in the coordinate axes of Zd or |A|
By Remark 3.1, if A is contained in the coordinate axis then |Ext(A, ~0)| ≤ 2d. Since H has the
(2d, 2)-Helly’s property, by Proposition 3.3 it follows that fe has an extension to A
e ∪ {~0} which
completes the proof.
Since |A| ≥ n + 1 > 2d, there exists ~i, ~j ∈ A and a coordinate 1 ≤ k ≤ d such that ik , jk are
non-zero and have the same sign. Suppose ik ≤ jk . Then there is a geodesic from ~j to ~i − ik ~ek
which passes through ~i. Since A = Ext(A, ~0) we have that
~i − ik~ek ∈
/ {~0} ∪ A.
Thus ~j ∈ / Ext(A,~i − ik~ek ) and hence |Ext(A,~i − ik~ek )| ≤ n. By St(n) there exists a 1-Lipschitz
extension of f |Ext(A,~i−ik~ek ) to Ext(A,~i − ik~ek ) ∪ {~i − ik~ek }. By Proposition 3.2 there is a 1-Lipschitz
extension of f to f ′ : A ∪ {~i − ik~ek } −→ H. But there is a geodesic from ~i to ~0 which passes through
~i − ik ~ek . Thus



Ext A ∪ {~i − ik ~ek }, ~0 ⊂ A \ {~i} ∪ {~i − ik~ek }.


Set A′ := A \ {~i} ∪ {~i − ik ~ek }. By Proposition 3.2, map f ′ has a 1-Lipschitz extension to
A ∪ {~i − ik ~ek } ∪ {~0} if and only if f ′ |A′ has a 1-Lipschitz extension to A′ ∪ {~0}.
Thus we have obtained a set A′ and a 1-Lipschitz map f ′ : A′ ⊂ Zd −→ H for which
(1) If f ′ has an extension to A′ ∪ {~0} then f has an extension to A ∪ {~0}.
(2) The sum of the number of non-zero coordinates of elements of A′ is less than the sum of
the number of non-zero coordinates of elements of A.
By repeating this procedure (formally this is another induction) we get the required set A e ⊂ Zd
and 1-Lipschitz map fe : A e −→ H. This completes the proof.

4. Applications of the main theorem

4.1. Back to continuous setting. The techniques involved in the proof of Theorem 1.1 extend
to the continuous case with only minor modifications. The following result might be of interest in
metric geometry.
5
 A metric space (X, m) is geodesically complete if for all x, y ∈ X there exists a continuous
function f : [0, 1] → X, such that
m(x, f (t)) = tm(x, y) and m(f (t), y) = (1 − t)m(x, y).
Theorem 4.1. Let Y be a metric space such that every closed ball in Y is compact. Then Y is
(Rd , ℓ1 )-Kirszbraun if and only if Y is geodesically complete and (2d, 2)-Helly.
First, we need the following result.
Lemma 4.2. Let (X, m) be separable and the closed balls in (Y, m′ ) be compact. Then (Y, m′ ) is
(X, m)-Kirszbraun if and only if all finite sets A ⊂ X and 1-Lipschitz maps f : A → Y , y ∈ Y \ A
have a 1-Lipschitz extension to A ∪ {y}.
Proof. The “only if” part is obvious. For the “if” part, let A ⊂ X and f : A → Y be 1-Lipschitz.
Since X is separable, A is also separable. Let
{xi : i ∈ N} ⊂ X and {ai : i ∈ N} ⊂ A
be countable dense sets. By the hypothesis, we have
\
Bm(x1 ,ai ) (f (ai )) 6= ∅.
1≤i≤n
Since closed balls in Y are compact it follows that
\
Bm(x1 ,ai ) (f (ai )) 6= ∅.
i∈N
Thus f has a 1-Lipschitz extension to A ∪ {x1 }. By induction we get that f has a 1-Lipschitz
extension fe : A ∪ {xi : i ∈ N} → Y . Let g : X → Y be the map given by
g(x) := lim fe(xi ) for all x ∈ X,
j
j→∞
where xij is some sequence such that limj→∞ xij = x. The limit above exists since closed balls in
Y are compact, and hence Y is a complete metric space. By the continuity of fe it follows that
g|A = f and by the continuity of the distance function it follows that g is 1-Lipschitz. 
For the proof of Theorem 4.1, note that the main property of Zd exploited in proof of Theorem 1.1
is that the graph metric is same as the ℓ1 metric. From the lemma above, the proof proceeds
analogously. We omit the details.

4.2. Lipschitz constants. The following extension deals with other Lipschitz constants. In the
continuous case this is trivial; however it is more delicate in the discrete setting. Since we are
interested in Lipschitz maps between graphs we restrict our attention to integral Lipschitz constants.
Theorem 4.3. Let t ∈ N and H be a connected graph. Then every t-Lipschitz map f : A −→ H,
A ⊂ Zd , has a t-Lipschitz extension to Zd if and only if
for all balls B1 , B2 , . . . B2d of radii multiples of t mutually intersect =⇒ ∩Bi 6= ∅.
The proof of Theorem 4.3 follow verbatim the proof of Theorem 1.1; we omit the details.
Let H be a Zd -Kirszbraun graph. The theorem implies that all t-Lipschitz maps f : A −→ H,
A ⊂ Zd , have a t-Lipschitz extension. On the other hand, it is easy to construct graphs G and H
for which H is G-Kirszbraun but there exists a 2-Lipschitz map f : A −→ H, A ⊂ G, which does
not have a 2-Lipschitz extension. First, we need the following result.
Proposition 4.4. Let G be a finite graph with diameter n and H be a connected graph such that
BnH (v) is G-Kirszbraun for all v ∈ H. Then H is a G-Kirszbraun graph.
6
Proof. Let f : A ⊂ G −→ H be 1-Lipschitz and pick a ∈ A. Then Image(f ) ⊂ BnH (f (a)). Since
BnH (f (a)) is G-Kirszbraun the result follows. 

Since trees are Helly graphs, we have as an immediate application of the above that Cn is G-
Kirszbraun if diam(G) ≤ n − 1. For instance, let r = (1, 1, 1, 1, 1, 1) ∈ N6 and consider the star Tr .
We obtain that C6 is Tr -Kirszbraun. Now label the leaves of Tr as bi , 1 ≤ i ≤ 6, respectively. For
A = {b1 , . . . , b6 } ⊂ Tr , consider the map
f : A → C6 given by f (bi ) = i.
The function f is 2-Lipschitz but it has no 2-Lipschitz extension to Tr .

4.3. Hyperoctahedron graphs. The hyperoctahedron graph Od is the graph obtained by remov-
ing a perfect matching from the complete graph K2d . Theorem 1.1 combined with the following
proposition implies that Od are Zd−1 -Kirszbraun but not Zd -Kirszbraun. When d = 2 this is the
example in the introduction (see Figure 1).
Proposition 4.5. Graph Od is (2d − 1, 2)-Helly but not (2d, 2)-Helly.
Proof. Let B1 , B2 , . . . , B2d−1 be balls of radius ≥ 1. Then, for all 1 ≤ i ≤ 2d − 1, Bi ⊃ Od \ {ji }
for some ji ∈ Od . Thus:
\
Bi ⊇ Od \ {ji : 1 ≤ i ≤ 2d − 1} = 6 ∅.

This implies that Od is (2d − 1, 2)-Helly.

In the opposite direction, let B1 , B1 , . . . , B2d be distinct balls of radius one in Od . It is easy to see
that they intersect pairwise, but ∩Bi = ∅. Thus, graph Od is not (2d, 2)-Helly, and Theorem 1.1
proves the claim. 

Let us mention that the hyperoctaheron graph Od ≃ K2,...,2 is a well-known obstruction to the
Helly’s property, see e.g. [BC08].

4.4. Bipartite version. In the study of Helly graphs it is well-known (see e.g. [BC08, §3.2])
that results which are true with regard to 1-Lipschitz extensions usually carry forward to graph
homomorphisms in the bipartite case after some small technical modifications. This is also true in
our case.
A bipartite graph H is called bipartite (n, m)-Helly if for balls B1 , B2 , B3 , . . . , Bn (if n 6= ∞
and any finite collection otherwise) and partite class H1 , we have that any subcollection of size m
among B1 ∩ H1 , B2 ∩ H1 , . . . , Bn ∩ H1 has a nonempty intersection implies
n
\
Bi ∩ H1 6= ∅.
i=1

Let G, H be bipartite graphs with partite classes G1 , G2 and H1 , H2 respectively. The graph H is
called bipartite G-Kirszbraun if for all 1-Lipschitz maps f : A ⊂ G −→ H for which f (A∩ G1 ) ⊂ H1
and f (A ∩ G2 ) ⊂ H2 there exists fe ∈ Hom(G, H) extending it.
Theorem 4.6. Graph H is bipartite Zd -Kirszbraun if and only if H is bipartite (2d, 2)-Helly.
As noted in the introduction, Theorem 1.1 implies that graph Z2 is not (4, 2)-Helly. However it
is bipartite (∞, 2)-Helly (see below).
Given a graph H we say that v ∼H w to mean that (v, w) form an edge in the graph. Let H1 , H2
be graphs with vertex sets V1 , V2 respectively. Define:
7
 (1) Strong product H1 ⊠ H2 as the graph with the vertex set V1 × V2 , and edges given by
(v1 , v2 ) ∼H1 ⊠H2 (w1 , w2 ) if v1 = w1 and v2 ∼H2 w2 ,
or v1 ∼H1 w1 and v2 = w2 ,
or v1 ∼H1 w1 and v2 ∼H2 w2 .
(2) Tensor product H1 × H2 as the graph with the vertex set V1 × V2 , and edges given by
(v1 , v2 ) ∼H1 ×H2 (w1 , w2 ) if v1 ∼H1 w1 and v2 ∼H2 w2 .

Proposition 4.7. If for a graph G, graphs H1 and H2 are G-Kirszbraun then H1 ⊠ H2 is G-

Kirszbraun. If for a bipartite graph G, bipartite graphs H1′ and H2′ are bipartite G-Kirszbraun then
the connected components of H1′ × H2′ are bipartite G-Kirszbraun.
Proof. We will prove this in the non-bipartite case; the bipartite case follows similarly. Let f :=
(f1 , f2 ) : A ⊂ G −→ H1 ⊠ H2 be 1-Lipschitz. It follows that the functions f1 and f2 are 1-
Lipschitz as well; hence they have 1-Lipschitz extensions fe1 : G −→ H1 and fe2 : G −→ H2 . Thus
(fe1 , fe2 ) : G −→ H1 ⊠ H2 is 1-Lipschitz and extends f . 
Corollary 4.8 (cf. [BC08, §3.2]). Graph Z2 is bipartite (∞, 2)-Helly.
Proof. As we mentioned above, it is easy to see that all trees are Helly graphs. By Proposition 4.7,
so are the connected components of Z × Z which are graph isomorphic to Z2 . Now Theorem 4.6
implies the result. 

5. Complexity aspects
5.1. The recognition problem. Below we give a polynomial time algorithm to decide whether
a given graph is Zd -Kirszbraun. We assume that the graph is presented by its adjacency matrix.
Proposition 5.1. For all fixed n, m ∈ N, the recognition problem of (n, m)-Helly graphs and
bipartite (n, m)-Helly graphs can be decided in poly(|H|) time.
For n = ∞ and m = 2, the recognition problem was solved in [BP89]; that result does not follow
from the proposition.

Proof. Let us seek the algorithm in the case of (n, m)-Helly graphs; as always, the bipartite case is
similar. In the following, for a function g : R → R by t = O(g(|H|)) we mean t ≤ kg(|H|), where k
is independent of |H| but might depend on m, n.
(1) Determine the distance between the vertices of the graph. This takes O(|H|3 ) time.
(2) Now make a list of all the collections of balls; each collection being of cardinality n. Since
the diameter of the graph H is bounded by |H|; listing the centers and the radii of the balls
takes time O(|H|2n ).
(3) Find the collections for which all the subcollections of cardinality m intersect. For each
collection, this step takes O(|H|) time.
(4) Check if the intersection of the balls in the collections found in the previous step is nonempty.
This step again takes O(|H|) time.
Thus, the total time is O(|H|2n+3 ), as desired. 

8
5.2. The hole filling problem. The following application is motivated by the tileability problems,
see Section 2.
Fix d ≥ 2. By a box Bn in Zd we mean a subgraph {0, 1, . . . , n}d . By the boundary ∂n we mean
the internal vertex boundary of Bn , that is, vertices of Bn where at least one of the coordinates
is either 0 or n. The hole-filling problem asks: Given a graph H and a graph homomorphism
f ∈ Hom(∂n , H), does it extend to a graph homomorphism fe ∈ Hom(Bn , H)?

Theorem 5.2. Fix d ≥ 1. Let H be a finite bipartite (2d, 2)-Helly graph, Bn ⊂ Zd a box and
f ∈ Hom(∂n , H) be a graph homomorphism as above. Then the hole-filling problem for f can be
decided in poly(n + |H|) time.

The same result holds in the context of 1-Lipschitz maps for (2d, 2)-Helly graphs; the algorithm
is similar. For general H, without the (2d, 2)-Helly assumption, the problem is a variation on
existence of graph homomorphism, see [HN04, Ch. 5]. The latter is famously NP-complete in
almost all nontrivial cases, which makes the theorem above even more surprising.

Proof. In the following, for a function g : R2 → R, by t = O(g(|H|, n)) we mean t ≤ kg(|H|, n)

where k is independent of |H| and n. Let f ∈ Hom(∂n , H) be given. Since H is bipartite (2d, 2)-
Helly graph, by Theorem 1.1, f extends to Bn if and only if f is 1-Lipschitz. Thus to decide the
hole-filling problem we need to determine whether or not f is 1-Lipschitz. This can be decided in
polynomial time:
(1) Determine the distances between all pairs of vertices in H. This costs O(|H|3 ).
(2) For each pair of vertices in the graph ∂n , determine the distance between the pair and their
image under f and verify the Lipschitz condition. This costs O(n2d−2 ).
The total cost is O(n2d−2 + |H|3 ), which completes the proof. 

For d = 2 and H = Z, the above algorithm can be modified to give a O(n2 ) time complexity
for the hole-filling problem of an [n × n] box. This algorithm can be improved to the nearly linear
time O(n log n), by using the tools in [PST16]. We omit the details.

6. Final remarks and open problems

6.1. In the view of our motivation, we focus on the Zd -Kirszbraun property throughout the pa-
per. It would be interesting to find characterizations for other bipartite domain graphs such as the
hexagonal and the square-octahedral lattice (cf. [Ken04, Thu90]). Similarly, it would be interest-
ing to obtain a sharper time bound on the recognition problem as in Proposition 5.1, to obtain
applications similar to [PST16].
Note that a vast majority of tileability problems are computationally hard, which makes the
search for tractable sets of tiles even more interesting (see [Pak03]). The results in this paper,
especially the bipartite versions, give a guideline for such a search.

6.2. As we mention in Section 2, there are intrinsic curvature properties of the underlying spaces,
which allow for the Helly-type theorems [LS97]. In fact, there are more general local hyperbolic
properties which can also be used in this setting, see [CE07, CDV17, Lang99]. See also a curious
“local-to-global” characterization of Helly graphs in [C+], and a generalization of Helly’s properties
to hypergraphs [BD75, DPS14].
9
6.3. In literature, there are other “discrete Kirszbraun theorems” stated in different contexts. For
example, papers [AT08, Bre81] give a PL-version of the result for finite A, B ⊂ Rd and 1-Lipschitz
f : A → B. Such results are related to the classical Margulis napkin problem and other isometric
embedding/immersion problems, see e.g. [Pak09, §38–§40] and references therein.
In a different direction, two more related problems are worth mentioning. First, the carpenter’s
rule problem can be viewed as a problem of finding a “discrete 1-Lipschitz homotopy”, see [CD04,
CDR03]. This is also (less directly) related to the well-known Kneser–Poulsen conjecture, see
e.g. [Bez10].

Acknowledgements. We would like to thank the referee for several useful comments and sugges-
tions. We are grateful to Arseniy Akopyan, Alexey Glazyrin, Georg Menz, Alejandro Morales and
Adam Sheffer for helpful discussions. Victor Chepoi kindly read the draft of the paper and gave us
many useful remarks, suggestions and pointers to the literature.
We thank the organizers of the thematic school “Transversal Aspects of Tiling” at Oléron, France
in 2016, for inviting us and giving us an opportunity to meet and interact for the first time. The
first author has been funded by ISF grant Nos. 1599/13, 1289/17 and ERC grant No. 678520. The
second author was partially supported by the NSF.

References
[AT08] A. V. Akopyan and A. S. Tarasov, A constructive proof of Kirszbraun’s theorem, Math. Notes 84 (2008),
725–728.
[BC08] H.-J. Bandelt and V. Chepoi, Metric graph theory and geometry: a survey, in Surveys on discrete and
computational geometry, AMS, Providence, RI, 2008, 49–86.
[BP89] H.-J. Bandelt and E. Pesch, Dismantling absolute retracts of reflexive graphs, European J. Combin. 10
(1989), 211–220.
[BL00] Y. Benyamini and J. Lindenstrauss, Geometric nonlinear functional analysis, Vol. 1, AMS, Providence,
RI, 2000.
[BD75] C. Berge and P. Duchet, A generalization of Gilmore’s theorem, in Recent advances in graph theory,
Academia, Prague, 1975, 49–55.
[Bez10] K. Bezdek, Classical topics in discrete geometry, Springer, New York, 2010.
[BS08] A. I. Bobenko and Yu. B. Suris, Discrete differential geometry, AMS, Providence, RI, 2008.
[Bre81] U. Brehm, Extensions of distance reducing mappings to piecewise congruent mappings on Rm , J. Geom. 16
(1981), 187–193.
[C+] J. Chalopin, V. Chepoi, H. Hirai and D. Osajda, Weakly modular graphs and nonpositive curvature, to
appear in Memoirs AMS ; arXiv:1409.3892
[CDV17] V. Chepoi, F. F. Dragan and Y. Vaxés, Core congestion is inherent in hyperbolic networks, in Proc. 28th
SODA, SIAM, Philadelphia, PA, 2017, 2264–2279.
[CE07] V. Chepoi and B. Estellon, Packing and covering of δ-hyperbolic spaces by balls, in Approximation, Ran-
domization, and Combinatorial Optimization (M. Charikar et al., eds), Springer, Berlin, 2007, 59–73.
[CD04] R. Connelly and E. D. Demaine, Geometry and topology of polygonal linkages, in Handbook of Discrete
and Computational Geometry (Second Ed.), CRC Press, Boca Raton, FL, 2004, 197–218.
[CDR03] R. Connelly, E. D. Demaine and G. Rote, Straightening polygonal arcs and convexifying polygonal cycles,
Discrete Comput. Geom. 30 (2003), 205–239.
[DGK63] L. Danzer, B. Grünbaum and V. Klee, Helly’s theorem and its relatives, in Proc. Sympos. Pure Math.,
vol. VII, AMS, Providence, RI, 1963, 101–180.
[DPS14] M. C. Dourado, F. Protti and J. L. Szwarcfiter, On Helly hypergraphs with variable intersection sizes, Ars
Combin. 114 (2014), 185–191.
[Fed69] H. Federer, Geometric measure theory, Springer, New York, 1969.
[HN04] P. Hell and J. Nešetřil, Graphs and homomorphisms, Oxford Univ. Press, Oxford, 2004.
[Hel23] E. Helly, Über mengen konvexer körper mit gemeinschaftlichen punkten (in German), J. Deutsch. Math.
Vereinig 32 (1923), 175–176.
[Ken04] R. Kenyon, An introduction to the dimer model, in ICTP Lect. Notes XVII, Trieste, 2004, 267–304.
10
[Kir34] M. Kirszbraun, Über die zusammenziehende und lipschitzsche transformationen, Fund. Math. 22 (1934),
77–108.
[Lang99] U. Lang, Extendability of large-scale Lipschitz maps, Trans. AMS 351 (1999), 3975–3988.
[LS97] U. Lang and V. Schroeder, Kirszbraun’s theorem and metric spaces of bounded curvature, Geom. Funct.
Anal. 7 (1997), 535–560.
[Lin02] N. Linial, Finite metric spaces – combinatorics, geometry and algorithms, in Proc. ICM Beijing, Vol. III,
Higher Ed. Press, Beijing, 2002, 573–586.
[Mat02] J. Matoušek, Lectures on discrete geometry, Springer, New York, 2002.
[MT16] G. Menz and M. Tassy, A variational principle for a non-integrable model; arXiv:1610.08103.
[Pak03] I. Pak, Tile invariants: New horizons, Theor. Comp. Sci. 303 (2003), 303–331.
[Pak09] I. Pak, Lectures on discrete and polyhedral geometry, monograph draft (2009); available at
http://www.math.ucla.edu/~ pak/book.htm
[PST16] I. Pak, A. Sheffer and M. Tassy, Fast domino tileability, Discrete Comput. Geom. 56 (2016), 377–394.
[She05] S. Sheffield, Random surfaces, Astérisque 304 (2005), 175 pp.
[Tas14] M. Tassy, Tiling by bars, Ph.D. thesis, Brown University, 2014; available at
http://www.math.ucla.edu/~ mtassy/articles/PhD_thesis.pdf
[Thu90] W. P. Thurston, Groups, tilings and finite state automata, in Lecture Notes, AMS Summer Meetings,
Bolder, CO, 1989.
[Val45] F. A. Valentine, A Lipschitz condition preserving extension for a vector function, Amer. J. Math. 67
(1945), 83–93.

School of Mathematical Sciences, Tel Aviv University, Israel

E-mail address: nishant.chandgotia@gmail.com

Mathematics Department, Unversity of California, Los Angeles, CA

E-mail address: pak@math.ucla.edu

Mathematics Department, Dartmouth College, Hanover, NH

E-mail address: martintassy@gmail.com

11