Maximising distance between sets in the grid

Define a grid to be ${1, dots, k}^n$.

Treat the grid as a graph where where two points are adjacent if they are equal in all positions except one, where they differ by 1 (for example $(1,1,1) ~ (2,1,1)$)

For vertices $x,y$ in the grid, define the distance $d(x,y)$ to be the length of the shortest path between $x$ and $y$ in the grid.

For non-empty subsets $A,B$, define the distance $d(A,B)$ to be $d(A,B) = min{d(x,y) mid x in A, y in B}$

Define the simplicial ordering on the grid to be $x < y$ if:

$sum_i x_i < sum_i y_i$, or

$sum_i x_i = sum_i y_i$ and $x_i > y_i$ for $i = min{j mid x_j neq y_j}$

Finally let $I_l$ be the initial segment of simplicial ordering on the grid of size $l$, and let $bar I_m$ be the last $m$ elements (final segment) of the simplicial ordering on the grid.

I am asked to prove that if two non-empty subsets of the grid $A,B$ are such that $d(A,B) geq t$ with $|A| = l, |B| = m$ then $d(I_l, bar I_m) geq t$

My immediate thought is to show that inital and final segments of the simplicial ordering maximise this distance between subsets. However, I couldn't think of a nice way to do this.

If I try induction on $l+m$, then:

Base case: $l+m = 2 Rightarrow l = m = 1$, in which case $d(I_1, bar I_1) = n(k-1)$ and this is clearly maximal (At least I think it's clear)

Inductive: $l+m > 2$. We start by picking an $x in A$ such that $d(Abackslash{x}, B) geq t$.

Removing this $x$, we get a set $A'$ of size $l-1$, which means that by induction we see that $d(I_{l-1}, bar I_m) geq t$.

Now, we consider adding one point, $z$ to $I_{l-1}$ to get $I_l$. Let $y$ be the last point of $I_{l-1}$

Notice, in the simplicial ordering, we go through hyperplances of the grid of the form $H_r = {x mid sum_i x_i = r}$ for $n leq r leq nk$.

Case 1: $y,z$ are in different hyperplanes, $H_r$ and $H_{r+1}$ respectively.

In this case, we know $z$ must be the last element of $H_r$ and $y$ must be the first element of $H_{r+1}$ which tells us that $y = (r-n + 2, 1, dots, 1)$.

Then for all $x = (x_1, dots, x_n) in bar I_m$, we have: $d(x,y) = sum_i|x_i - y_i|$

Notice that $x$ is in a hyperplane $H_s$ where $s geq r + 1$.

If $s = r + 1$ then: $d(x,y) = y_1 - x_1 + sum_{i=2} x_i - y_i = 2y_1 - (r+1) + (r+1) - 2x_1 = 2y_1 - 2x_1$

It is at this point that I notice there seem to be far too many cases to check, and it makes me think that perhaps this is not the right approach.

Will I be able to solve the question if I pursue this train of thought, or am I on the wrong tracks? Any help would be appreciated, thank you!

asked Dec 15 '18 at 20:29

user366818

1,000410

add a comment |

Define a grid to be ${1, dots, k}^n$.

Treat the grid as a graph where where two points are adjacent if they are equal in all positions except one, where they differ by 1 (for example $(1,1,1) ~ (2,1,1)$)

For vertices $x,y$ in the grid, define the distance $d(x,y)$ to be the length of the shortest path between $x$ and $y$ in the grid.

For non-empty subsets $A,B$, define the distance $d(A,B)$ to be $d(A,B) = min{d(x,y) mid x in A, y in B}$

Define the simplicial ordering on the grid to be $x < y$ if:

$sum_i x_i < sum_i y_i$, or

$sum_i x_i = sum_i y_i$ and $x_i > y_i$ for $i = min{j mid x_j neq y_j}$