Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I once proved this question many years ago but now I have completely forgotten how I did it. I remember it being a fun problem and wouldn't mind seeing a proof again, with the likelihood of it being a lot more elegant than what my own proof was

The problem:

Let $G$ be a typical $n \times n$ grid or a square lattice graph. Let $f : G \rightarrow \mathbb{Z}$ be a function on the vertices such that $|f(v) - f(w)| \leq 1$ if $v$ and $w$ are adjacent. Show that at least $n$ of those vertices have the same $f$-value.

Aside for those interested in Go:

I remember my proof used some reductions where I ended up proving that the groups in Go with the fewest liberties for the amount of stones invested are those which are clumped in the corner. I now have no idea how this relates to the problem at all so if you can see what I was thinking at the time, it would be nice to know.

Further questions that I find interesting:

Sorry if open ended discussion is not what this site is about, just some other thoughts I had after typing this out. I was wondering about what can we say about other graphs satisfying this bounded difference property. The more connected a graph is, the larger the necessarily largest amount of equal $f$-values there has to be is. $K_n$ has to have $\lceil n/2\rceil $ equal $f$-values. Is there some standard property of a graph we can use to determine this number? What about other higher dimensional square lattices?

Thanks.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Aha, I think I remember how the proof goes. Here is a basic sketch of the idea:

Let $g(c) = |S_c|$ where $S_c = \{v \in V : f(v) \leq c\}$

Now since $g$ is increasing and $g(-\infty) = 0$ and $g(\infty) = n^2$, there is some $i$ such that $g(i) < \frac{n(n+1)}{2} + 1$ and $g(i+1) \geq \frac{n(n+1)}{2}$

Suppose we can't find $n$ vertices with the same $f$-value, then $g(i+1)-g(i)<n$. This means that $\frac{n(n+1)}{2} - n \leq g(i) < \frac{n(n+1)}{2}$.

Then it remains to show that any subset of $g(i)$ vertices can have at fewest $n$ neighbours when $g(i)$ is restricted to this range. This is where I used the idea of bad shape in Go and realised that the fewest neighbours occur when all these vertices are clumped up in a corner. There are a few tricks to showing this last part, allowing various operations which do not increase the neighbour size and eventually pulling everything back up to the top left corner.

This method could perhaps work in general. Find the largest $n$ over all values of $n$ and $m$ for which the following is true: $n \leq \displaystyle\min_{U\subseteq G, m-n \leq |U| < m}|N(U)|$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.