TITLE: When does there exist a convex polyhedron with given edge lengths?
QUESTION [5 upvotes]: Let $n$ be a positive integer, and let $n = \ell_1 + \dots + \ell_k$ be
a partition of $n$. Then there exists a convex polygon with side lengths
$\ell_1, \dots, \ell_k$ if and only if all of the $\ell_i$ are smaller
than $\frac{n}{2}$.
Questions: 

What is the corresponding criterion in $3$ dimensions,
i.e. under which conditions does there exist a convex polyhedron with
edge lengths $\ell_1, \dots, \ell_k$?
How many of the $p(n)$ partitions of $n$ do occur as lists of edge
lengths of some polyhedron -- i.e. which are these values for small $n$,
and what is asymptotically the proportion of such partitions among all
partitions of $n$ when $n$ goes to infinity?

REPLY [7 votes]: Since I expect the answer for all combinatorial types of polytopes to be somewhat obscure, let me give an answer to the more simple question of what happens for the tetrahedron. We denote the six edges of the tetrahedron by $(x,y,z,a,b,c)$ and assume six faces the ones with edges $(a,b,c), (x,y,c), (x,b,z)$ and  $(a,y,z)$. The sextuple $(x,y,z,a,b,c)$ corresponds to such a tetrahedron if and only if 

$(a,b,c), (x,y,c), (x,b,z)$ and  $(a,y,z)$ satisfy the triangle inequality, and 
the Cayley-Menger determinant $$CM(x,y,z,a,b,c):=\left(\begin{array}{rrrrr}
0 & x^{2} & y^{2} & z^{2} & 1 \\
x^{2} & 0 & c^{2} & b^{2} & 1 \\
y^{2} & c^{2} & 0 & a^{2} & 1 \\
z^{2} & b^{2} & a^{2} & 0 & 1 \\
1 & 1 & 1 & 1 & 0
\end{array}\right)$$ is positive. 

This would be a complete answer to your first question if you only asked for the tetrahedron.
So if you consider a partition $(p_1,\dots,p_6)$ of $n$, you have to say which of the $p_i$s correspond to which edge, or just check all permutations of the partition (so perhaps it would be more natural to consider compositions?!). In any case if you do this for the first few $n$, you get a sequence like this (if there is no mistake in my calculations):$$[0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 3, 2, 3, 4, 4, 6, 9, 9, 11, 13, 16, 17, 24, 25, 32, 34, 40, 47, 55, 61, 70, 83, 91, 101, 117, 124, 148, 160, 181, 195, 225, 243, 270, 301, 327, 359, 396, 432, 473, 513, 566, 604, 668, 712, 782, 844, 913, 985, 1056, 1148, 1227, 1313, 1421, 1509, 1640, 1730, 1863, 1985, 2127, 2269, 2410, 2572, 2738, 2905, 3099, 3276, 3490, 3682, 3914, 4128, 4377, 4615, 4892, 5170, 5450, 5753, 6057, 6389, 6725, 7067, 7460, 7807, 8236, 8638, 9077, 9504, 10005, 10461, 10961].$$ 
Compare this to partitions into 6 parts:$$[0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 5, 7, 11, 14, 20, 26, 35, 44, 58, 71, 90, 110, 136, 163, 199, 235, 282, 331, 391, 454, 532, 612, 709, 811, 931, 1057, 1206, 1360, 1540, 1729, 1945, 2172, 2432, 2702, 3009, 3331, 3692, 4070, 4494, 4935, 5427, 5942, 6510, 7104, 7760, 8442, 9192, 9975, 10829, 11720, 12692, 13702, 14800, 15944, 17180, 18467, 19858, 21301, 22856, 24473, 26207, 28009, 29941, 31943, 34085, 36308, 38677, 41134, 43752, 46461, 49342, 52327, 55491, 58767, 62239, 65827, 69624, 73551, 77695, 81979, 86499, 91164, 96079, 101155, 106491, 111999, 117788, 123755, 130019, 136479]$$
If you plot these two, you get:
For a better comparison, I take the fifths root of the values to get this plot (since we now that partitions into 6 parts roughly grow like $n^5$):
From these few values one might conjecture that the blue values also grow roughly like $n^5$, perhaps with a factor $(1/2)^5$ slower than all partitions into 6 parts.
{"set_name": "stack_exchange", "score": 5, "question_id": 236422}