Consider a planar subdivision, with F faces, V vertices, E edges, and I face-vertex incidences. For simplicity, assume a "non-degenerate" situation in which each vertex occurs on the boundary cycle of each face only once. Then I is the sum over all faces of the number of vertices per face, or equivalently, the sum over all vertices of the number of incident faces. We have I = 2E, and therefore Euler's formula gives us:

F + V = I/2 + 2.

All I actually care about is:

F + V < I/2.

Does this also hold in for three-dimensional subdivisions, when F is the number of three-dimensional cells of the subdivision, and V and I are as defined above?

Note that I am looking for an inequality that is independent of the number of one- and two-dimensional faces in the subdivision. When the cells are convex I can get something using quite a bit of geometry, but it seems to me that the requirement that the cells be convex is an artifact of my proof technique, and something more general should be possible and/or known. Does anybody have an idea where to look for the answer?

  • $\begingroup$ What is a planar subdivision? $\endgroup$ – Tyson Williams Aug 21 '12 at 16:13
  • 1
    $\begingroup$ A subdivision of the plane, e.g. by means of a planar graph. Anyway, I just realized I need to clarify something else, namely: "F + V < I/2". Of course this is not true, not even in 2D, but it is true up to an additive constant. I do not care about the additive constant. I would like to know if asymptotically, if I refine a subdivision by subdividing cells further, F + V cannot grow faster than I/2. $\endgroup$ – Herman Haverkort Aug 21 '12 at 17:52
  • 4
    $\begingroup$ You should edit your question to include this information. $\endgroup$ – Tyson Williams Aug 22 '12 at 3:05

Doesn't $F + V \le 2I$ hold trivially for every system of incidences between things called vertices and things called faces? Under some reasonable assumptions, every vertex has at least one incidence, and every face has at least one incidence. If you add those incidences together you count each incidence at most twice.

To get from there to your desired $F + V \le I/2 + O(1)$ you'd need to use some actual geometry show that the vertices and faces each have at least four incidences on average. This is obvious for convex subdivisions but maybe needs more assumptions in general (e.g. consider a system of bubbles in 3d space, linked one to the next in a chain: each face has no vertex-face incidences, because there are no vertices).

  • $\begingroup$ So the question is: what assumptions do I need? In 2D I need to assume that the network of vertices and edges is connected, otherwise the inequality breaks down there as well. Now what about 3D? In fact, convexity is not even sufficient, because we can make a convex subdivision by slicing a cylinder $\endgroup$ – Herman Haverkort Aug 23 '12 at 5:35
  • $\begingroup$ (continued from my previous comment, which was somehow saved prematurely) we can make a convex subdivision by slicing a cylinder and then there are no vertices either... I wonder if we can avoid actual geometry by, e.g., assuming that all faces are simply connected (no holes) and not counting things that are adjacent to the outer face (would be ok for my application). But I guess now the question becomes to specific already to have a standard answer... $\endgroup$ – Herman Haverkort Aug 23 '12 at 6:04
  • $\begingroup$ A natural assumption would be that the edges of the arrangement are connected. Otherwise, as Herman pointed out, this seems false. $\endgroup$ – Sariel Har-Peled Aug 24 '12 at 5:00

As Tsuyoshi points out in the comments, the following answer is about upper bounds for $I$ in terms of $F$ and $V$, while the original question is about the lower bound $I \ge 2(F+V)$. (Sorry!)

See David Eppstein's response for the correct answer to the original question.

Ziegler defines the fatness and complexity of a cell decomposition $X$ of the 3-sphere (for example, a 4-dimensional convex polytope) as follows: $$ F(X) = \frac{f_1 + f_2 - 20}{f_0 + f_3 - 10} \quad\text{and}\quad C(X) = \frac{f_{03} - 20}{f_0 + f_3 - 10}. $$ Here, $f_i$ denotes the number of $i$-dimensional cells (0=vertices, 1=edges, 2=polygons, 3=chambers), and $f_{03}$ is the number of incidences between vertices and chambers. (The -10 and -20 terms simplify some inequalities.)

Your question is equivalent to asking whether $C(X)$ is always less than some fixed constant. Ziegler observes that the generalized Dehn-Sommerville relations (a particular generalization of a generalization of Euler's formula) imply that $$ C(X) \le 2F(X) -2 \quad\text{and}\quad F(X) \le 2C(X) - 2. $$ So equivalently, you are asking whether there is an upper bound on the maximum possible fatness of a 3d cell complex.

In fact, there is no such upper bound. Eppstein, Kuperberg, and Ziegler construct, for any integer $n$, a cellular 3-sphere $X_n$ with $O(n^{12})$ vertices and chambers but $\Omega(n^{13})$ edges and polygons, so $C(X_n) = \Omega(n)$.

Moreover, it is an open question whether $C(X)$ is bounded for convex 4-polytopes. Eppstein, Kuperberg, and Ziegler also construct an infinite family of 4-polytopes $X$ such that $F(X)>5$ and thus $C(X)>3.5$; these are the fattest 4-polytopes known.

On the other hand, it is known that fatness cannot grow arbitrarily quickly; specifically, any $n$-vertex cell decomposition has fatness $O(n^{2/3})$, and any $n$-vertex convex 4-polytope has fatness $O(n^{1/3})$.

  • $\begingroup$ All of this is interesting, but isn’t the question about a lower bound on C(X)? $\endgroup$ – Tsuyoshi Ito Aug 22 '12 at 15:58
  • 1
    $\begingroup$ D'oh!! (What? You mean $<$ isn't commutative?) $\endgroup$ – Jeffε Aug 22 '12 at 19:43
  • 2
    $\begingroup$ If I remember correctly, it is known that if the < on ℚ is commutative, then the polynomial hierarchy collapses to the second level. $\endgroup$ – Tsuyoshi Ito Aug 22 '12 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.