Kirszbraun-type Theorems For Graphs

Abstract

The classical Kirszbraun theorem says that all $1$-Lipschitz functions $f:A⟶{\mathbb{R}}^n$, $A\subset {\mathbb{R}}^n$, with the Euclidean metric have a $1$-Lipschitz extension to ${\mathbb{R}}^n$. For metric spaces $X,Y$ we say that $Y$ is $X$-Kirszbraun if all $1$-Lipschitz functions $f:A⟶Y$, $A\subset 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 ${\mathbb{Z}}^d$-Kirszbraun graphs are exactly graphs that satisfies a certain Helly property. We also consider complexity aspects of these properties.