1710.11007.pdf

KIRSZBRAUN-TYPE THEOREMS FOR GRAPHS

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

NISHANT CHANDGOTIA, IGOR PAK, AND MARTIN TASSY

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 c

d'

c'

a'

b'

a

O

d

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 boundary 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) fˆ(a) := e f (b)

if a ∈ A 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, respectively. 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}. e ⊂ Zd and a 1-Lipschitz function fe : A e −→ H, such that We will prove that there exists a set A e ∪ {~0} then f has an extension to A ∪ {~0}. (1) If fe has an extension to A 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 e ∪ {~0} which (2d, 2)-Helly’s property, by Proposition 3.3 it follows that fe has an extension to A 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. e ⊂ Zd By repeating this procedure (formally this is another induction) we get the required set A e −→ H. This completes the proof. and 1-Lipschitz map fe : A 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)

m(f (t), y) = (1 − t)m(x, y).

and

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 GKirszbraun 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 removing 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 )

v1 ∼H1 w1 and v2 ∼H2 w2 .

if

Proposition 4.7. If for a graph G, graphs H1 and H2 are G-Kirszbraun then H1 ⊠ H2 is GKirszbraun. 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 1Lipschitz 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 paper. 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 interesting 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 suggestions. 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´eron, 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´es, 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, Randomization, 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¨ unbaum 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ˇsetˇril, Graphs and homomorphisms, Oxford Univ. Press, Oxford, 2004. ¨ [Hel23] E. Helly, Uber mengen konvexer k¨ orper 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

¨ M. Kirszbraun, Uber 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ˇsek, 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´erisque 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. [Kir34]

School of Mathematical Sciences, Tel Aviv University, Israel E-mail address: [email protected] Mathematics Department, Unversity of California, Los Angeles, CA E-mail address: [email protected] Mathematics Department, Dartmouth College, Hanover, NH E-mail address: [email protected]

11