# A Brouwer fixed point theorem on finite sets

I have casually almost (i.e. up to details that shoud work) proved the following discrete version of Brouwer's fixed point theorem. I should have obtained this result as a corollary of quite complicated things and I do not understand if the result is trivial and can be easily proved directly or it deserves to be stressed. I would like to hear your opinion about that.

Let $n\geq1$ be a fixed integer and denote by $X=[-n,n]^2\subseteq\mathbb Z^2$. Given $(x,y)\in X$ I denote by $A(x,y)$ the set formed by the following at most five points: $(x-1,y),(x,y),(x+1,y),(x,y-1),(x,y+1)$. At most means that if one of those points does not belong to $X$, I will not consider it.

The result would be: let $f:X\rightarrow X$ such that for all $(x,y)\in X$ one has $f(A(x,y))\subseteq A(f(x,y))$. Then $f$ has a fixed point.

Is that trivial?

Valerio

-
You probably mean to universally quantify that condition: $\forall (x, y) \in X^2 (f(A(x, y)) \subseteq A(f(x, y))$. – Todd Trimble Oct 14 '11 at 13:20
When writing $[−n,n]$, do you mean $\{-n,-n+1,\dots,n\}$ or the real interval? – Emil Jeřábek Oct 14 '11 at 13:23
yes, thanks. I ve just corrected – Valerio Capraro Oct 14 '11 at 13:24
Did you check $n=1$? – Andreas Thom Oct 14 '11 at 14:20
Actually, I am quite convinced that I have misunderstood my own property! The right formulation of my application is little different. If you are interested, I have opened another topic: mathoverflow.net/questions/78147/… – Valerio Capraro Oct 14 '11 at 16:42

I believe the following is a counter-example:

$f: \lbrace -1,0,1\rbrace^2 \to \lbrace -1,0,1\rbrace^2$

$\forall x:$

$f(-1,x) = (1,x)$

$f(0,x)=(1,x)$

$f(1,x)=(0,x)$

-
Well I agree that this is a counter-example and I have also understood where was my mistake (the devil is in the details!). I am trying to add a simple condition in order to make the details working.. – Valerio Capraro Oct 14 '11 at 14:16
I am wondering ... Maybe it is still possible to get a version of Brouwer's fixed point theorem. The condition $f(A(x,y))\subseteq A(f(x,y))$ looks a lot like continuity. If you equip $X$ with the Euclidean metric, it just says that whenever $d(x,y) \leq 1$ it follows that $d(f(x),f(y)) \leq 1$. My intuition suggests that it should still be possible to prove that there is an almost-fixed point $x_0$ in the sense that $d(f(x_0),x_0) \leq 1$. This certainly works for the one-dimensional analog of the problem ($X = \lbrace 1,2, ..., n \rbrace$). – Dejan Govc Oct 15 '11 at 16:50
this is a nice idea! Indeed I have thought about that condition as a discrete version of continuity. I will think about that. – Valerio Capraro Oct 15 '11 at 20:57
I have thought about it some more and $d(f(x_0),x_0)\leq 1$ won't always work, but I am quite sure you can prove that there always exists a point $x_0$ such that $d(f(x_0),x_0)\leq C$ where $C$ is a constant depending only on the dimension $d$. This is because you can extend your function by piecewise linear interpolation to a continuous function on $[-n,n]^d \subseteq \mathbb{R}^d$ and then use the original Brouwer fixed point theorem obtaining a fixed point. Now choose the closest lattice point. This point has the property we seek (this follows from your property and piecewise linearity). – Dejan Govc Oct 16 '11 at 1:58
It is a beautiful problem, I must say. – Dejan Govc Oct 16 '11 at 1:59

Wouldn't the Tietze extension theorem (with range $X$) show that any permutation of $A$ extends to a function $f$?

-
I don't understand: in that case the extension has a fixed point but it might not belong to $X$. Indeed it is not true that any permutation of $X$ has a fixed point. Am I missing something? – Valerio Capraro Oct 14 '11 at 13:23
Yes, that was my point. As originally stated, I don't believe what you are hoping for is true. But I see that you have edited your question in the meantime, and I'm not sure what you are asking any more. – Carl Offner Oct 14 '11 at 13:25