Open Problem Garden - Difference between neighbors in a matrix - Comments

bandwidth (re: Difference between neighbors in a matrix)

Daniel Soltész — Sat, 20 Jul 2013 17:03:54 +0200

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

Solution (re: Difference between neighbors in a matrix)

Daniel Soltész — Tue, 28 May 2013 06:29:50 +0200

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

Difference between neighbors in a matrix

Vadim Lioubimov — Mon, 20 May 2013 01:39:45 +0200

Author(s): Vadim Lioubimov

Subject: Combinatorics » Matrices

Conjecture Any matrix with different integer entries has two neighboring entries with .

Open Problem Garden - Difference between neighbors in a matrix - Comments

bandwidth (re: Difference between neighbors in a matrix)

Related questions: continued (re: Difference between neighbors in a matrix)

Related questions (re: Difference between neighbors in a matrix)

Solution (re: Difference between neighbors in a matrix)

Difference between neighbors in a matrix