7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ What is a planar subdivision? $\endgroup$ Aug 21, 2012 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$ Aug 21, 2012 at 17:52
  • 4
    $\begingroup$ You should edit your question to include this information. $\endgroup$ Aug 22, 2012 at 3:05

2 Answers 2

6
$\begingroup$

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).

$\endgroup$
3
  • $\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$ Aug 23, 2012 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$ Aug 23, 2012 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$ Aug 24, 2012 at 5:00
4
$\begingroup$

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})$.

$\endgroup$
3
  • $\begingroup$ All of this is interesting, but isn’t the question about a lower bound on C(X)? $\endgroup$ Aug 22, 2012 at 15:58
  • 1
    $\begingroup$ D'oh!! (What? You mean $<$ isn't commutative?) $\endgroup$
    – Jeffε
    Aug 22, 2012 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$ Aug 22, 2012 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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