Return to Question

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.

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 ____?

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.

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 ____?

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 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 ____?

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.

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 ____?

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?

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 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 ____?