## A Brouwer fixed point theorem on finite sets

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

Thank you in advance,

Valerio

-

1
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 2011 at 13:20

1
When writing $[−n,n]$, do you mean $\{-n,-n+1,\dots,n\}$ or the real interval? – Emil Jeřábek Oct 14 2011 at 13:23

1
yes, thanks. I ve just corrected – Valerio Capraro Oct 14 2011 at 13:24
Did you check $n=1$? – Andreas Thom Oct 14 2011 at 14:20

1
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 2011 at 16:42
show 2 more comments

## 2 Answers

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 2011 at 14:16

1
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 2011 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 2011 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 2011 at 1:58
It is a beautiful problem, I must say. – Dejan Govc Oct 16 2011 at 1:59

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 2011 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 2011 at 13:25
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9432316422462463, "perplexity_flag": "head"}