## [Math] Why cellular network has hexagonal shape?

In many advertisements of mobile phone providers, you can see a hexagonal network resembling bee's honeycomb.

In Russian language, "cellular/mobile phone" was often called "сотовый телефон", and "сота" in Russian means a cell in bee's honeycomb. In Ukrainian language, "cellular network" is called "стільниковий зв'язок", and "стільник" in Ukrainian is also bee's honeycomb.

Do bees have a connection to cellular phones? Yes, many knows that mobile stations are places in such hexagonal network.

Why it's so? If mobile stations are too close to each other, they can't use the same frequency, they will interfere with each other. Mobile stations can share the same frequency only if they are too far from each other.

Let's use graph coloring to assign frequency to each mobile station. Here I use Z3 SMT solver, but the problem is well-known and many libraries and algorithms exists to find graph coloring.

A number in each cell in this graph cannot be equal to one in neighbour cell. Each cell has 8 neighbours.

5 0 5 3 5 3 1 3 4 0 5 2 1 2 0
1 2 4 1 2 4 5 2 5 3 1 0 5 3 1
3 5 3 5 0 3 0 3 1 2 4 2 4 2 0
4 1 2 1 2 1 4 2 0 3 0 1 3 1 3
2 3 0 3 4 0 5 1 4 5 2 5 4 5 4
0 1 2 5 1 2 3 0 2 3 4 3 1 3 1
2 3 4 3 4 5 4 5 1 5 1 2 4 0 2
0 1 2 1 0 1 2 3 4 2 4 3 1 3 4


Minimum number of colors is 6. I can't make it smaller. You may also have heard about "chromatic number of a graph" -- and this is 6. So if you place mobile station in rectangular network, you'll need at least 6 frequencies.

It's all different if they are placed in hexagonal network. Each cell has 6 neighbours.

0 3 0 3 0 3 0 3 0 3 0 3 0 3 0
1 2 1 2 1 2 1 2 1 2 1 2 1 2
0 3 0 3 0 3 0 3 0 3 0 3 0 3 0
1 2 1 2 1 2 1 2 1 2 1 2 1 2
3 0 3 0 3 0 3 0 3 0 3 0 3 0 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2
3 0 3 0 3 0 3 0 3 0 3 0 3 0 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1


Only 4 frequencies are needed. The "chromatic number" is 4. 4 frequencies -- this is much better. Also, you can clearly see regularities in this network. You can assign frequencies even manually.

But in practice, mobile providers can't place stations in such an ideal network. But even if stations are placed in random places, graph coloring can still be used to assign frequencies. Read more about radio coloring.

###### (the post first published at 20231206.)

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.