# Largest sphere in a “grid graph”

Let $G=(V,E)$ be an undirected graph, such that $V$ is a subset of $\{1,\dotsc,N\} \times \{1,\dotsc,N\}$ and there is an edge between $2$ vertices if and only if they have one identical coordinate and differ by exactly $1$ in the other coordinate (we can think about it as a grid, with some points omitted, such that we can move up/down/right/left).

The graph $G$ defines a metric (by $d(v_1,v_2)=$minimum number of edges in a path from $v_1$ to $v_2$). A sphere is defined as usual: for $v \in V$, we let $S(v,r)=\{u \in V \mid d(v,u)=r\}$.

What is $\max\limits_{v,r}|S(v,r)|$? An asymptotic expression in terms of $N$ would be enough. I strongly suspect it is $O(N)$ because that is what we get if $V=\{1,\dotsc,N\} \times \{1,\dotsc,N\}$ (i.e: no point omitted) and take $v=(N/2,N/2)$ and $r=N/2$.

-
I presume by $\underset{v,r}{\max}|S(v,r)|$ you mean $\underset{v,r,V}{\max}|S(v,r)|$? – joriki Aug 1 '11 at 7:10
@moonshine I misunderstood and trivialised your question, my apologies. Your actual question looks very interesting. – Srivatsan Aug 1 '11 at 14:55

I'm leaving my original $N^{\log_23}\approx N^{1.585}$ construction below since it's easier to understand and verify, but I've found an improved $N^{\log_2(3+\sqrt{17})-1}\approx N^{1.833}$ construction:

I've increased the time per frame to $2$ seconds to make it easier to see the principle. (By the way, Mac OS Preview allows you to browse through the individual frames with the cursor keys if you download the image.)

Here's a static image of an intermediate stage:

Each branch brings forth $3$ branches of the next generation and $2$ of the generation after that, so the growth is determined by the recurrence

$$a_{k+2}=3a_{k+1}+2a_k$$

with characterstic values $(3\pm\sqrt{17})/2$. Thus, the number of points is $\sim k^{(3+\sqrt{17})/2}$ for $N=2k+1$, so $\underset{v,r}{\max}|S(v,r)|$ is $\Omega(N^{\log_2(3+\sqrt{17})-1})\approx \Omega(N^{1.833})$.

Here's a not quite rigorous argument that the number is in fact $\Omega(N^{2-\epsilon})$ for any $\epsilon>0$. Looking at the later stages of the constructions, you see areas that don't get filled. The reason they don't get filled is that they're close to points that are reached early and it would be more complicated to "waste enough time" to get to these areas late enough -- one would have to add paths that go back and forth a couple of times and then sprout out into these areas. But the "cost" of going back and forth a certain number of times, the number of points used up by such paths, is linear in $N$, whereas the area that can be filled using them is quadratic in $N$. So it may not be possible to efficiently fill all the small holes that are left by the final stages, but for any given pattern of paths leading into the empty areas, it can be applied at all stages except for the last $s$ stages, where $s$ depends on the "thickness" of the pattern. But these $s$ stages only give us a constant factor of $4^s$ in the number of points; we can simply drop them without changing the asymptotic dependence on $N$. So we can keep building more and more complicated paths into the empty areas, and the cost of using up a few rows of points will asymptotically not matter since the number $s$ of stages at which it becomes impossible to lay those paths is independent of $N$ whereas the number of stages at which the cost of the paths is negligible compared to the areas opened up by them grows with $N$. I believe this shows that the number is $\Omega(N^{2-\epsilon})$ for any $\epsilon>0$, though it might be a bit tedious to spell the argument out rigorously.

Here's the original $N^{\log_23}\approx N^{1.585}$ construction:

Here's a static version:

The images are being scaled down to fit the column width; you can open them in a new tab/window to get the full resolution (by right/ctrl-clicking).

All the bright points at the ends of the segments are at the same distance from the centre. Some of these are reached in different ways; I counted the number of distinct points while drawing the frames. Counting from $k=0$, and not counting the initial frame with $4$ points, there are $4(3^k+2^k)$ distinct points in the $k$-th frame, with $N=2^{k+1}+1$, so we have

$$\underset{v,r}{\max}|S(v,r)|>4\cdot3^{\log_2(N-1)-1}>3^{\log_2(N-1)}\sim3^{\log_2N}=N^{\log_23}\;.$$

I suspect that the number is also $O(N^{\log_23})$, but I haven't found a proof yet.

P.S.: I just realized that the construction was unnecessarily complicated -- almost the same figure can be constructed in a more straightforward way, which avoids points being reached twice and makes it obvious that the number of points is being tripled in each step:

(Again, right/ctrl-click on the image and open it in a new tab/window to get the full resultion -- it looks much nicer :-)

Here the number of points in the $k$th frame is simply $\frac433^k$.

P.P.S: I just realized that since there's automatically an edge between adjacent points, we actually need to double $N$ to be able to realize only the connections shown in the images; but that's just a constant factor so it doesn't change the $\Omega(N^{\log_23})$ conclusion.

-
Nice idea! Btw, is this a standard pattern? Does it have a name? I tried googling for "fractals" (is it even a fractal?), but couldn't find this. – Srivatsan Aug 1 '11 at 18:58
@Srivatsan: I don't know if it's a standard pattern; I made it up for this answer. I don't know much about fractals, but I think this must be one, and its Hausdorff dimension should be $\log_23$, which is also the Hausdorff dimension of the Sierpinski triangle. – joriki Aug 1 '11 at 19:10
Thank you very much! I don't know whether or not to accept because it is not a full answer, but it is indeed very helpful. – moonshine Aug 2 '11 at 8:54
When in doubt, wait :-) – joriki Aug 2 '11 at 9:30
@moonshine: I see you haven't been on the site since you asked this question in August. If you ever do come back, I suggest you accept Matt's answer. – joriki Jan 5 '12 at 0:25

It is possible to achieve a sphere of size $O(n^2)$ by using "the H fractal".

Define V=\left\{ (x,y)\in\{1,\ldots,N\}\times\{1,\ldots,N\} {\ \Huge|\ } \begin{aligned} 2\mid x \ \ \wedge\ \ l(x)+1 \in g(y) \\ or\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,\,\\ 4\mid y \ \ \wedge\ \ l(y) \in g(x) \ \ \ \ \ \ \ \,\, \end{aligned} \right\} where $g(n)$ is the set of $k$ for which the binary "$2^k$s" and "$2^{k+1}$s" digits of $n$ differ, and $l(n)=\mbox{min}(g(n))$.

Here is a picture for $N=15$.

   . . . . . . . # . . . . . . .
. # . . . # . # . # . . . # .
. # . . . # . # . # . . . # .
. # # # # # . # . # # # # # .
. # . # . # . # . # . # . # .
. # . # . # . # . # . # . # .
. . . # . . . # . . . # . . .
. . . # # # # # # # # # . . .
. . . # . . . . . . . # . . .
. # . # . # . . . # . # . # .
. # . # . # . . . # . # . # .
. # # # # # . . . # # # # # .
. # . . . # . . . # . . . # .
. # . . . # . . . # . . . # .
. . . . . . . . . . . . . . .


The size of a large sphere centered at the top, when $N$ is a power of 2, is $N^2/16$. Considering the connectivity as $N$ grows, we can see that for all $N$, there is a sphere of size at least $N^2/36$.

(The problem with "the Plus fractal" (underlying Joriki's very nice animations) is that although it is space-filling, the nearest of the four pluses (not drawn in those animations) is closer than the other three and so does not contribute to the sphere. The H fractal doesn't have this problem because the route to any part of the H starts by going to the center.)

Here's an animation for this very nice solution – as with the others, you can right-click to open it in a new window in full size or open it in Mac OS Preview to browse the individual frames at leisure.

-
Since you liked my animations and I like your solution, I made an animation for your solution :-) I took the liberty of adding it to your answer. It turns out there's a minor error in your formula -- it doesn't cover the upper ends of the leaves -- here's a slightly augmented version that works: $(2\mid x\land ((l(x)+1 \in g(y)) \lor (4\nmid x \land l(x)+1\in g(y-1)))) \lor (4\mid y\land l(y)\in g(x))$. By the way, I'd be interested in how you came up with that formula to express this construction. – joriki Jan 5 '12 at 0:24

Added. I greatly misunderstood and misjudged the question. As @Jyrki points out, the set $V$ is relevant to the problem (and without it, the question, just like my answer, becomes trivial), the distance between $(x_1, y_1)$ and $(x_2, y_2)$ is not $|x_1 - x_2| + |y_1-y_2|$, and so on. I am just keeping the answer for the records.

A wrong attempt.

I hope I understood your question correctly. I do not see how $V$ is relevant to the problem.

We'll prove that any sphere is indeed of size $O(N)$. Fix any center $v = (v_1, v_2)$ and a radius $0 \leq r \leq 2N-2$. (The upper bound $2N-2$ is the diameter of the graph.) The sphere $S$ is defined to be the set of points $(v_1+x,v_2+y)$ such that $|x| + |y| = r$. Clearly, $-r \leq x \leq r$; moreover, for any value of $x$, there are at most $2$ possible values of $y$, namely $\pm(r-|x|)$. So, the total number of points is at most $$\sum_{x=-r}^r 2 = 2(2r+1) \leq 2(4N-4+1) = O(N) .$$

-
The choice of $V$ is relevant. If you, say, only include the points with an even $y$-coordinate, and in addition to them `the connecting points' alternating at left and right ends, you get a chain of length about $N^2/2$. With that choice of $V$ the diameter of the graph is then also about $N^2/2$. All the spheres have only two points, though, so this is the opposite of a counterexample. IOW the distance between $(x_1,y_1)$ and $(x_2,y_2)$ is NOT necessarily equal to $|x_1-x_2|+|y_1-y_2|$ because the connecting paths of that length may be broken. – Jyrki Lahtonen Aug 1 '11 at 11:16
@Jyrki Ah, looks like I messed it up completely. Anyway I'll keep the answer for the record and to preserve your (great!) comment. And, thanks for pointing out what I am doing wrong. – Srivatsan Aug 1 '11 at 14:54
No problem. To tell you the truth I first thought that my chain $V$ was a counterexample. Only then I realized that the OP does NOT want to maximize the diameter. So we can share some of the shame, and perhaps try to turn a sequence of snowflaky $V$:s into a counterexample :-) – Jyrki Lahtonen Aug 1 '11 at 15:23
Well, the chain was long enough, which was exactly the problem in a way. – Jyrki Lahtonen Aug 1 '11 at 18:43
@Jyrki Oh sorry. I misread again (this time, what you meant by a chain, though you have clearly said it has $N^2/2$ points). I'll just not say or read anything for a while. :-) – Srivatsan Aug 1 '11 at 18:47