Welcome to MathOverflow

Question

3

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

edited Oct 14 2011 at 13:21

asked Oct 14 2011 at 13:06

Valerio Capraro
3,595●11●25

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

Dejan Govc · Accepted Answer · 2011-10-14 13:48:59Z UTC

5

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)$

answered Oct 14 2011 at 13:48

Dejan Govc
313●2●8

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

Carl Offner · Answer 2 · 2011-10-14 13:21:38Z UTC

0

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

answered Oct 14 2011 at 13:21

Carl Offner
354●3●4

	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

A Brouwer fixed point theorem on finite sets

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

2 Answers

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.