Enough of the ‘trying to understand recent big theorems’ on this blog, let’s do something light and fun this week!

As I was browsing the ArXiv one day, one thing led to anther and I eventually arrived in a very short and cute paper of Greg Kuperberg and Oded Schramm.

So, we have sphere packings, which is simply a bunch of spheres (say in ) with disjoint interiors, some of them might be tangent to others, in which case we say the two sphere ‘kiss‘, like this: (points of tangency are marked with a red cross)

We can associate a graph to a sphere packing with vertices representing spheres and join two vertices with an edge if two sphere kisses:

Question: What kind of graph can appear this way?

Now if we go back to two-dimensions, it’s a classical theorem that any planar graph can appear as the nerve of a circle packing. (In fact, as mentioned at the end of this earlier post, something much stronger is true. i.e. it’s a theorem of Schramm that one can ‘kiss’ pretty much any given set of planar objects with a given nerve.)

In light of this, it’s nature to wonder whether every graph can be realized as a nerve of some sphere packing (since all graph embeds in some oriented surface which then embeds in ). Turns out, no.

However I would imagine it’s not easy to show things such as a given graph cannot be realized. In the paper they came up with what’s perhaps the first restriction that shows not all graphs can be realized in such packing, namely:

The average kissing number is, as one might expect, in average how many kisses does each sphere get, i.e.

2 * number of tangency points / number of balls

If one thinks about it, how might one attempt to construct a packing with super large average kissing number? Well, perhaps we start with a single sphere, put a huge amount of small spheres around it (because one cannot fit many large spheres), then this middle one does get a lot of kisses, but what about the smaller ones? If they are equal sized then all the small spheres only gets roughly 7 kisses…now we need to put even smaller spheres around each of those…If we stop at any stage, there would be more smallers spheres that’s not taken care of than the larger ones with lots of kisses, so it’s not clear at all if the average can blow up.

As usual, things are much simpler in two dimensions: Since the Euler characteristic of any planar graph is 2 (), and (any face needs at least 3 edges around them, precisely two faces share an edge) we have

, hence <

On the other hand, for our all-time favorite hexagonal packing of congruent circles, if we take more and more layers, the number of balls with six kisses grow like , the number of balls on the boundary (hence with less than six kisses) is like . Hence by adding enough layers we can make the average as close to 6 as we want~

Hexagonals are the best, as expected~

Now comes what’s in the paper: they showed that for any sphere packing, the average kissing number is less than . Hence any graph with average degree larger than 15 cannot be realized. They also provided an example of sphere packings with average kissing number larger than 12.

For simplicity I’ll only reproduce the ‘warm-up case’ in the paper which proves the kissing number is no more than 24. (well, since our goal here is only to say that not all graphs can be realized.) I find this observation (due to Schramm) is very simple, cute, and works in any dimensions.

Let’s first define some numbers:

the maximum number of congruent sphere kissing one sphere (i.e. how many unit spheres we can place around a unit sphere) can be easily computed, for example and , etc.

Let average kissing number of sphere packings in dimension . As we have seen and we are interested in giving upper bounds to .

Theorem: .

Given a sphere packing , let be the set of kissing pairs and be the set of spheres.

Define map where maps each pair to the sphere in the pair with smaller radius (if the two spheres has the same radius, then just randomly choose one).

Since each sphere can only be surrounded by spheres of its size (of course larger than its size would give us fewer), we conclude that is at most to . Therefore, we have

, i.e.

How simple!

Now going from 24 to requires some estimates relying on us being in 3-dimensions. Essentially, given any sphere in the packing, if we enlarge it by a ratio w.r.t its center, then this ‘shell’ intersect some other spheres in disjoint circles. Those circles of course cuts out a fraction of the area that’s < 1 on the shell. Summing this fraction over all shells results a number that’s less than .

Now if we look at each pair of balls, say take pair (V_1, V_2), it turns out that if they kiss, the fraction of shell around that’s cut out by plus the fraction of shell around cut out by is a constant depending only on .

Hence we get a relation . Choose an optimum gives which is a bit less than 15.

So we know but larger than 12, the problem of finding the exact value of remains open, so is the problem of giving other restrictions on the graph for being the nerve of a sphere packing.