Integer Lattice Graphs

An integer lattice graph can be defined as a graph G=(V,E) such that V = \mathbb{Z}^n and E = \{vw|v,w\in V, ||v-w||=1\}, i.e., two vertices are adjacent when exactly one of their co-ordinates differ by 1 while the other co-ordinates are all equal. It is a particularly easy graph to visualize. It is 2n-regular. [Clearly, given a vertex, to get one of its neighbours, you have to change exactly one of the co-ordinates. You may either increase it by 1 or decrease it by 1 and this may be done for all n co-ordinates. Thus, there are 2n neighbours for every vertex.]

It becomes a bit more interesting when you consider the finite integer lattice graph. As you can guess, the vertex set is now defined by V = \{-n, -(n-1), ..., 0, ..., n\}^d, where d is a +ve integer. The edge set has the same definition. This graph, while still quite easy to visualize is no longer regular. And this makes way for an interesting problem:

Find the average degree of a finite integer lattice graph.

How do we do this? Well, it is clear that the interior points still have degree 2d. However, everything changes for the points whose co-ordinates have at least one n or -n.

We have to tackle this part carefully. Let v\in V. Let k be the number of co-ordinates whose absolute value is not n. Then, 0\leq k\leq d. To find the degree of v, we have to find out the number of neighbours of v. To go to a neighbour from v, we have to change exactly one of the co-ordinates as before. For the k co-ordinates which are strictly between -n and n, we can either increase or decrease by 1 as before. However, for the other d-k co-ordinates, we can only decrease by 1 (when the co-ordinate is n) or increase by 1 (when the co-ordinate is -n, but we cannot do both. So, now we can obtain a neighbour of v in d+k ways. Hence, deg(v)=d+k.

Is this enough? No. Just the degree won’t do. We also need to know the exact number of vertices of each degree between d and 2d. How many vertices can have exactly d-k co-ordinates equal to n or -n and the remaining not equal to \pm n? The answer is clearly {n\choose k}2^{d-k} (2n-1)^k [Note that there are 2n + 1 possibilities for each co-ordinate].

Then, we have

\sum_{v\in V} deg(v) = \sum_{k=0}^{d} (d+k){n\choose k}2^{d-k} (2n-1)^k

\Rightarrow \sum_{v\in V} deg(v) = d \sum_{k=0}^{d} {n\choose k}2^{d-k} (2n-1)^k+\sum_{k=0}^{d} k{n\choose k}2^{d-k} (2n-1)^k

\Rightarrow \sum_{v\in V} deg(v) = d(2n+1)^d + (2n-1)d\sum_{k-1=0}^{d-1} \frac{(d-1)!}{((k-1)!(d-k)!}2^{d-k} (2n-1)^{k-1}

\Rightarrow \sum_{v\in V} deg(v) = d(2n+1)^d + (2n-1)d(2n+1)^{d-1} = 4nd(2n+1)^{d-1}

Hence, the average degree of the graph is \frac{4nd}{2n+1}.

That was interesting, wasn’t it? The result isn’t very surprising if you try putting d=2.

Phew! I am literally sick and tired of writing \LaTeX now. The next such post will be at least a week later.

Acknowledgements: Prof Young, who gave this problem in an assignment