MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Minimum dimension for sphere packing a graph in Euclidean space

Igor Pak suggested I ask this as a separate question. In http://mathoverflow.net/questions/85547/extensions-of-the-koebeandreevthurston-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.

Scott 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 value of the minimum dimension, or, at least, some sort of "normal behavior" for this, meaning that "most" graphs on $n$ vertices need a minimum dimension of about __?

-
 Is Steve Carnahan any relation to one of the MathOverflow moderators? Gerhard "Ask Me About System Design" Paseman, 2012.01.19 – Gerhard Paseman Jan 19 2012 at 23:22 Anyway, an induction on the number of vertices seems plausible. To wit, given n vectors in R^(n-1), add an extra coordinate and see if you can solve the system of n equations which would place a sphere touching k of the n spheres whose centers sit in the hyperplane. Gerhard "Is This A Sweet Solution?" Paseman, 2012.01.19 – Gerhard Paseman Jan 19 2012 at 23:26 Further, if a planar graph cannot be so packed in R^3, I would like to see it. Gerhard "Ask Me About System Design" Paseman, 2012.01.19 – Gerhard Paseman Jan 19 2012 at 23:29 Gerhard, it took me a few days to work it out, it is actually Scott Carnahan. – Will Jagy Jan 21 2012 at 0:38 As long as you get it straight before publication, Walt. Gerhard "What Is My Name Again" Paseman, 2012.01.20 – Gerhard Paseman Jan 21 2012 at 2:03

Start with a regular simplex with unit length edges in ${\mathbf{R}}^{n-1}$, representing $K_n$. In any non-degenerate simplex, one can increase or decrease the length of any edge by a sufficiently small amount, leaving all other edge lengths fixed and flexing the dihedral angle opposite to the edge. Do this to increase the length of every edge in $K_n$ that is not present in your given graph $G$, one edge at a time. Finally, place radius-1/2 balls at the vertices of the resulting simplex. The result is a sphere packing representing $G$.

-
 Yes, I think I understand. It would never have occurred to me that we can perturb one edge at a time. – Will Jagy Jan 21 2012 at 3:13

This is a longish comment rather than a complete answer.

Long ago Fred Roberts introduced the notion of the "boxicity" of a graph, and later the related notion of "sphericity" of a graph was studied. To quote Michael and Quint in their paper, "Sphericity, cubicity, and edge clique covers of graphs," Discrete Applied Mathematics, Volume 154, Issue 8, 2006,

The sphericity sph$(G)$ of a graph $G$ is the minimum dimension $d$ for which $G$ is the intersection graph of a family of congruent spheres in $\mathbb{R}^d$.

There are upper bounds known on the sphericity of graphs. The paper I quoted shows that sph$(G) \le \theta(G)$, where $\theta(G)$ is the edge clique cover number of $G$, i.e., "the minimum cardinality of a set of cliques that covers all edges of $G$."

Here's another upper bound result, in the paper "The Johnson-Lindenstrauss lemma and the sphericity of some graphs," by Frankl and Maehara, Journal of Combinatorial Theory, Series B,Volume 44, Issue 3, 1988, Pages 355–362.

if $G$ is a graph on $n$ vertices and with smallest eigenvalue $\lambda$ then its sphericity sph$(G)$ is less than $c \lambda^2 \log n$.

If you can realize $G$ by touching balls in $\mathbb{R}^d$, then you have established its sphericity is at most $d$.

-
 Thanks, Joseph. Although I think they must be close, I think there may be graphs with a certain sphericity, but the more difficult task of arranging the spheres to be perfectly tangent may require an increase of dimension by 1 or 2. That is, it is not clear to me that we can shrink radii and perturb centers to improve a given sphere-intersecting arrangement into a sphere-tangency arrangement. We probably can, I suppose, I am not seeing very clearly what continuity methods give us here. – Will Jagy Jan 20 2012 at 3:04 @Will: Excellent point re shrinking! It is not clear one can shrink intersecting spheres to produce tangent spheres. Many simultaneous constraints... – Joseph O'Rourke Jan 20 2012 at 11:37

It should be doable with constant radii in $\mathbf{R}^{n-1}$. A subgraph of the complete graph can be laid out as some of the edges of a regular simplex. At each vertex take a tiny ball (very much smaller than the length of the edges. Each ball is cut by hyperplanes through the center of the ball perpendicular to the edges (all of them) of the simplex. Combinatorially, the hyperplanes in each ball behave like the coordinate hyperplanes. Thus each ball is cut into regions that cover all combinations of being closer to or farther from the other vertices of the simplex. For each vertex choose a region that is closer to those vertices that are neighbors in the desired subgraph of the simplex edges, and farther if not. Now for the belief part. It should be true that for some distance only slightly smaller than the edge length, points in the chosen regions (one per each) can be found of that distance if an edge is desired, and farther than that distance if an edge is not desired.

-