Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I have a similar question but for CW-complexes that are realizable in $R^3$ (let us call them spacial complexes). For spacial complexes, Euler's formula dictates $V-E+F-C = 0$ where $C$ is the number of 3-D cells. I can also see that, for spacial complexes to be maximal (by adding faces until if we add any other face in it then can not be embedded in $R^3$), they should be tetrahedralized. For each cell (tetrahedron) we have 4 faces and for each face we have 2 cells, therefore $4C = 2F$. That is, the number of cells is half the number of faces but still I do not know how to find the maximum number of edges as a function of the number of vertices.
-
$\begingroup$ The Euler formula is V - E + F - C = 1 if you consider balls. It is not clear what you mean by "maximal complexes", could you formulate the question more precisely? $\endgroup$– Bruno MartelliCommented Jan 3, 2014 at 10:46
-
$\begingroup$ Hi Bruno, you are right. I am also counting the outer cell in the Euler's formula. About your question, I have slightly changed the question to reflect the definition of maximal spatial simplicial complex. Here is the definition again: A spatial simplicial complex $SC$ is maximal if by adding any face to $SC$, it can not be embedded in $R^3$. $\endgroup$– HoomanCommented Jan 3, 2014 at 13:23
1 Answer
By coincidence I just happened to read the required information to answer this question in a recent preprint, arXiv:math.1308.5798, "Neighborly inscribed poytopes and Delaunay trisngulations", Gonska and Padrol. For references to the following facts (which go back to the late 70's) see this preprint. If a simplicial d+1 polytope has its vertices on the unit sphere, then an appropriate stereographic projection realizes the combinatorial type of the boundary of the polytope as a Delaunay triangulation in d-space. Since cyclic-4 polytopes can be realized with vertices on the unit sphere, it is possible to embed complexes with edges between any pair of vertices. The same argument shows that in dimension d it is possible to embed complexes with the same number of faces in each dimension as cyclic (d+1)-polytopes. So for i at most half the dimension you can get all possible i-faces. The maximum number of higher dimensional faces is unclear. To begin with, I do not see any reason to assume the complex is a ball. As I recall there are two-neighborly seven vertex embeddings of the solid torus in R^3.
