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.
login/create account
Drupal
CSI of Charles University
bandwidth
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