Home » Subject » Combinatorics » Matrices

Difference between neighbors in a matrix (Solved)

Importance: Low ✭
Author(s): Vadim Lioubimov
Subject: Combinatorics
» Matrices
Keywords:
Recomm. for undergrads: yes
Posted by: Vadim Lioubimov
on: May 20th, 2013
Solved by: Daniel Soltész
Conjecture   Any $ n\times n $ matrix with different integer entries has two neighboring entries $ a,b $ with $ |a-b|\ge n $.

Only neighbors in the same row or column are considered. Given a matrix $ A $, let $ v(A) $ be the maximum difference between two neighboring entries of $ A $. Given integers $ n,m\ge2 $, let $ \xi(n,m) $ be the smallest possible value of $ v(A) $ among all $ n\times m $ matrices $ A $ with different integer entries. Thus the conjecture asserts that $ \xi(n,n)\ge n $.

Consider the $ n\times m $ matrix $ B:=\{b_{i,j}\} $ defined by $ b_{i,j}:=i + (j-1)n $. The entries of $ B $ is $ [nm] $ and $ v(B)=n $. Thus $ \xi(n,m)\le\min\,\{n,m\} $. Consequently the conjecture is equivalent to the assertion $ \xi(n,m)=\min\,\{n,m\} $.

It can be easily seen that for any $ n\times m $ matrix $ A $ with different integer entries, there exists a matrix $ A^* $ with the entries $ [nm] $ such that $ v(A^*)\le v(A) $. Therefore, in the definition of $ \xi(n,m) $, we may assume that the entries of each matrix is $ [nm] $. Consequently the conjecture reduces to the case when the entries of the matrix is $ [n^2] $.

I have proved the conjecture for $ n\le5 $. The proof is separate for each of the 4 cases $ n=2,3,4,5 $ and pretty elementary. However, I am not so sure at the moment whether the conjecture is true for all $ n\ge6 $. If it turns out to be generally false, it would be an interesting problem to evaluate $ \xi(n,m) $. I wonder if there are any related results.

Bibliography



* indicates original appearance(s) of problem.
add new comment

Related questions: continued

On July 6th, 2013 Vadim Lioubimov says:

2. What is the smallest number, denoted $ P(k,n) $, to guarantee that a $ [k]^n $-matrix $ A $ with the entries $ [k^n] $ has 2 neighboring entries $ a,b $ such that $ b-a\ge V(k,n) $ and $ a \le P(k,n) $? Obviously, $ P(k,n)\le U(k,n) $, where $ U(k,n) $ is the smallest number such that any subset of $ [k]^n $ of size $ U(k,n) $ has at least $ V(k,n) $ neighbors. Due to Theorem 11, $ U(k,n) $ is the smallest number $ m $ such that the initial segment $ C_{k,n}(m) $ of length $ m $ in the simplicial order on $ [k]^n $ has $ V(k,n) $ neighbors. In your proof you used the fact that $ |b\big(B_{k,2}(k-1)\big)| = k $, which implies by Theorem 11 that $ U(k,2)\le |B_{k,2}(k-1)| = k(k-1)/2 $. However this bound is not tight. Consider the hamming ball $ H:=C_{k,n}\big(|B_{k,2}(k-2)|+1\big) $. It is easy to see that $ |b(H)| = k $ and $ |b\big(B_{k,2}(k-2)\big)| = k-1 $. Thus $ U(k,2)= |H| = (k-1)(k-2)/2 +1 $. What about higher dimensions?

reply

Related questions

On July 6th, 2013 Vadim Lioubimov says:

Dear Daniel, thank you for the very nice proof! Theorem 11 from the lecture notes you refer to suggests some answers to other general questions related to the conjecture (let us now refer to it as Theorem 0). In particular I have the following 2 questions in mind.

1. I wonder how the generalization of Theorem 0 to higher dimensional matrices looks like. More specifically, given integers $ k,n\ge2 $, what is the smallest value, denoted $ V(k,n) $, of $ v(A) $ among all $ [k]^n $-matrices $ A $ with distinct integer entries? Theorem 0 states that $ V(k,2)= k $. Theorem 11 implies that $$ V(k,n)\ge |b\big( B_{k,n}(k+n-2)\big)| = |S_{k,n}(k+n-1)|, $$ where $ B_{k,n}(r):=\{x\in[k]^n : |x| \le r\} $ and $ S_{k,n}(r):=\{x\in[k]^n : |x| = r\} $. My feeling is that $ V(k,n)= |S_{k,n}(k+n-1)| $. What do you think? Note that $ |S_{k,n}(r)| $ is the number of all ordered partitions of $ r $ into exactly $ n $ parts not exceeding $ k $.

reply

bandwidth

On July 20th, 2013 Daniel Soltész says:

Dear Dr. Lioubimov!

At first sight your feeling seemed plausible, but since then i managed to find the more general problem: The graph bandwidth problem. (see wiki page)

At the wikipedia page, you can see that a classical result of Harper is the bandwidth of the hypercube. Well, if your feeling were true, the bandwidth of the cube would be the middle binomial coefficient, which is not true.

We can see this in a different way too, i'll give some heuristics. Take a look at the proof of the 2 dimensional case: We had a single vertex which had a big label (at least n(n-1)/2+n). And we concluded that since it has at least one vertex with "small" label, we found a big difference. If we only have 2 dimensions, this bound is sharp, because the degrees of the vertices are not too big. In higher dimensionan grids there are more neighbours of this vertex with "small" labell. Thus a better lower bound can be obtained.

Sincerely, Daniel Soltész

reply

Solution

On May 28th, 2013 Daniel Soltész says:

Dear Dr. Lioubimov

Your problem is equivalent to the following: We label the vertces of the nxn grid graph with distinct elements from the set [n^2]. Then there are adjacent vertices such that their labels differ by at least n. I think i found a solution. The key related result is the vertex isoperimetric inequality in the grid. For our problem it is enough to consider the corollary 12 in the following .pdf:

https://www.dpmms.cam.ac.uk/~par31/notes/extcomb.pdf

With parameters: n=2 since we are in a 2 dimensional grid. Let A be the set which have the labels: 1,2,..., n(n-1)/2. Clearly then we can set r=n-1 and with t=1 we obtain that there are at least n neighbors of this set. This finishes our proof since one of these neighbors will have a label of at least n(n-1)/2+n.

Sincerely Daniel Soltész

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.