# 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