Introduction x - math.ucla.edu

1 KIRSZBRAUN-TYPE THEOREMS FOR GRAPHSNISHANT CHANDGOTIA, IGOR PAK, AND MARTIN classicalKirszbraun theoremsays that all 1-Lipschitz functionsf:A Rn,A Rn, with the Euclidean metric have a 1-Lipschitz extension toRn. For metric spacesX,Ywesay thatYisX-Kirszbraunif all 1-Lipschitz functionsf:A Y,A X, have a 1-Lipschitzextension toX. We analyze the case whenXandYare graphs with the usual path metric. Weprove thatZd-Kirszbraun graphs are exactly graphs that satisfies a certainHelly s property. Wealso consider complexity aspects of these results in metric geometry is important for many applications, ranging from discretedifferential geometry to numerical methods.

2 The discrete results are stronger as they typicallyimply the continuous results in the limit. Unfortunately, more often than not, straightforwarddiscretizations fall apart; new tools and ideas are needed to even formulate these extensions; [BS08, Lin02] and [Pak09, 21 24].In this paper we introduce a new notion ofG-Kirszbraun graphs, whereGis vertex-transitivegraph. The idea is to discretize the classicalKirszbraun theoremin metric geometry [Kir34] (seealso [BL00, ]). Our main goal is to explain the variational principle for the height functionsof tilings introduced by the third author in [Tas14] and further developed in [PST16, MT16] (seeSection 2); we also aim to lay a proper foundation for the future second goal is to clarify the connection to theHelly theorem, a foundational result in convexand discrete geometry [Hel23] (see also [DGK63, Mat02]).

3 Graphs that satisfy theHelly s propertyhas been intensely studied in recent years [BC08], and we establish a connection between two , we show thatZd-Kirszbraun graphs are somewhat rare, and are exactly the graphs thatsatisfy the Helly s property with certain `2denote the usual Euclidean metric onRnfor alln. Given a metricspaceXand a subsetA, we writeA Xto mean that the subsetAis endowed with the restrictedmetric fromX. TheKirszbraun theoremsays that for allA (Rn,`2), and all Lipschitz functionsf:A (Rn,`2), there is an extension to a Lipschitz function onRnwith the same now theHelly theorem: Suppose a collection of convex setsB1,B2.

4 ,Bksatisfies theproperty that every (n+ 1)-subcollection has a nonempty intersection, then Bi6= . Valentinein [Val45] famously showed how the Helly theorem can be used to obtain the Kirszbraun connection between these two theorems is the key motivation behind this metric spacesXandY, we say thatYisX-Kirszbraunif allA X, every 1-Lipschitzmapsf:A Yhas a 1-Lipschitz extension fromAtoX. In this notation, the Kirszbrauntheorem says that (Rn,`2) is (Rn,`2) Subject , words and theorem, Helly theorem, graph homomorphism, Lipschitz Nandn N { },n > m. Metric spaceXis said to have (n,m)-Helly s propertyif for every collection of closed ballsB1,B2.

5 ,Bnof radius 1 whenever everym-subcollectionhas a nonempty intersection, we have ni=1Bi6= . Since balls inRnwith the Euclidean metric areconvex, the Helly theorem can be restated to say that (Rn,`2) is ( ,n+ 1)-Helly. Note that themetric is important here, (Rn,` ) is ( ,2)-Helly, see [DGK63, Pak09].Given a graphH, we endow the set of vertices (also denoted byH) with the path metric. ByZdwe mean the Cayley graph of the groupZdwith respect to standard generators. All graphs in thispaper are nonempty, connected and simple (no loops and multiple edges). The following is themain result of this (Main theorem).

6 GraphHisZd-Kirszbraun if and only ifHis(2d,2) thecomplete graphonn-vertices. Clearly,KnisG-Kirszbraun for all graphsG,since all mapsf:G Knare 1-Lipschitz. On the other hand,Z2is notZ2-Kirszbraun, seeFigure 1. This example can be modified to satisfy a certain extendability property, see 'b'c'd'bacdOFigure {a,b,c,d} Z2. Definef:a a ,b b ,c c ,d d .Thenf:A Z2is 1-Lipschitz but not extendable to{O,a,b,c,d}. of the begin with a short non-technical Section 2 describing somebackground results and ideas. In essence, it is a remark which is too long to be in the reflects the authors different points of view on the subject, which includes ergodic theory,geometric combinatorics and discrete probability.

7 While in principle this section it can be skipped,we do recommend reading it as it motivates other parts of the then proceed to prove Theorem in Section 3. In Section 4, we present several extensionsand applications of the main theorem. These section is a mixed bag: we include a continuousanalogue of the main theorem (Theorem ), the extension to larger integral Lipschitz constants(Theorem ), and the bipartite extension useful for domino tilings (Theorem ). In a shortSection 5, we discuss computational aspects of theZd-Kirszbraun property, motivated entirely byapplications to tilings.

8 We conclude with final remarks and open problems in Section and backgroundAgraph homomorphismfrom a graphGto a graphHis an adjacency preserving map betweenthe respective vertices. Let Hom(G,H) denote the set of all graph homomorphisms refer to [HN04] for background on graph homomorphisms and connections to coloring andcomplexity 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 inZdtoHextends to the entire box.(2) Finding a natural parametrization of the so-called ergodic Gibbs measures on space of graphhomomorphisms Hom(Zd,H) (see [She05, MT16]).

9 For (1), roughly, suppose we are given a certain simple set of tiles T, such as dominoes ormore 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 referto [Pak03, Thu90] for the background, and to [PST16, Tas14] for further details. Our Theorem motivated by these both these problems, theZd-Kirszbraun property of the graphH(or a related graph) iscritical and motivates this line of research; the space of 1-Lipschitz maps is the same as the space ofgraph homomorphisms if and only ifHisreflexive, that is, every vertex has a self-loop.

10 The studyof Kirszbraun-type theorems among metric spaces and its relationship to Helly-like properties is anold one and goes back to the original paper by Kirszbraun [Kir34]. A short and readable proof isgiven in [Fed69, p. 201]. This was later rediscovered in [Val45] where it was generalized to the caseswhere the domain and the range are spheres in the Euclidean space or Hilbert spaces. The effortof understanding which metric spaces satisfy Kirszbraun properties culminated in the theorem byLang and Schroeder [LS97] that identified the right curvature assumptions on the underlying spacesfor which the theorem the metric graph theory, the research has focused largely on a certain universality , a graph is calledHellyif it is ( ,2)-Helly.