Skip to main content
1 of 4
Will Jagy
  • 25.7k
  • 2
  • 65
  • 121

Minimum dimension for sphere packing a graph in Euclidean space

Igor Pak suggested I ask this as a separate question. In Extensions of the Koebe–Andreev–Thurston theorem to sphere packing? it was asked whether there were simple conditions to decide whether a finite graph could be expressed by a bunch of spheres in $\mathbb R^3,$ two spheres touching if and only if the relevant vertices shared an edge.

Steve Carnahan and I are of the opinion that any graph on $n$ vertices can be placed in $\mathbb R^{n-1}$ in the manner described. It is proved in Igor's book that the complete graph can be placed in $\mathbb R^{n-2}$ and no smaller dimension, one regular simplex with unit radii and then one extra sphere in the center. Of course, the complete graph can also be placed as a regular simplex with all unit spheres in $\mathbb R^{n-1}.$ But the varying radius question seems more fortunate, we get the same answer, if it works, in $\mathbb H^{n-1}$ and $\mathbb S^{n-1}.$

So, that is the initial question, can anyone prove that any graph on $n$ vertices, however many or few edges, can be placed in $\mathbb R^{n-1}$ as a set of spheres, if we allow varying radius?

Secondarily, and I have not the slightest idea, is there any sort of expected dimension or "normal behavior" for this?

Will Jagy
  • 25.7k
  • 2
  • 65
  • 121