This is just too good.

Network of Thrones by Andrew Beveridge and Jie Shan

Skip to content
# Category: Graph Theory

## Graph Theory & Game of Thrones

## Integer Lattice Graphs

An **integer lattice graph **can be defined as a graph such that and , i.e., two vertices are adjacent when exactly one of their co-ordinates differ by 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 or decrease it by and this may be done for all n co-ordinates. Thus, there are 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 , where 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 . However, everything changes for the points whose co-ordinates have at least one or .

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

Is this enough? No. Just the degree won’t do. We also need to know the exact number of vertices of each degree between and . How many vertices can have exactly co-ordinates equal to or and the remaining not equal to ? The answer is clearly [Note that there are possibilities for each co-ordinate].

Then, we have

Hence, the average degree of the graph is .

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

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

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