<p>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.</p>

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

CC BY-SA 3.0
2012-08-23T05:35:25.503Z
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
Herman Haverkort
CC BY-SA 3.0
2012-08-23T06:04:45.367Z
(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...
Herman Haverkort
CC BY-SA 3.0
2012-08-24T05:00:31.673Z
A natural assumption would be that the edges of the arrangement are connected. Otherwise, as Herman pointed out, this seems false.
Sariel Har-Peled
CC BY-SA 3.0
2012-08-22T18:05:33.370Z
2012-08-22T18:12:25.900Z
2012-08-22T18:12:25.900Z
David Eppstein
<p>As Tsuyoshi points out in the comments, the following answer is about <em>upper</em> bounds for $I$ in terms of $F$ and $V$, while the original question is about the <em>lower</em> bound $I \ge 2(F+V)$.  (Sorry!)</p>

<p><strong>See David Eppstein's response for the correct answer to the original question.</strong></p>

<hr>

<p><a href="http://arxiv.org/abs/math/0208073v2" rel="nofollow">Ziegler</a> defines the <em>fatness</em> and <em>complexity</em> 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.)</p>

<p>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 <em>fatness</em> of a 3d cell complex.</p>

<p><strong>In fact, there is no such upper bound.</strong>  <a href="http://arxiv.org/abs/math/0204007v3" rel="nofollow">Eppstein, Kuperberg, and Ziegler</a> 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)$.</p>

<p>Moreover, it is an open question whether $C(X)$ is bounded for convex 4-polytopes.  <a href="http://arxiv.org/abs/math/0204007v3" rel="nofollow">Eppstein, Kuperberg, and Ziegler</a> also construct an infinite family of 4-polytopes $X$ such that $F(X)&gt;5$ and thus $C(X)&gt;3.5$; these are the fattest 4-polytopes known.</p>

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

CC BY-SA 3.0
2012-08-22T15:58:08.513Z
All of this is interesting, but isn’t the question about a lower bound on C(X)?
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-22T19:43:00.563Z
D'oh!!  (What?  You mean $<$ _isn't_ commutative?)
Jeffε
CC BY-SA 3.0
2012-08-22T20:51:26.913Z
If I remember correctly, it is known that if the < on ℚ is commutative, then the polynomial hierarchy collapses to the second level.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-22T02:30:03.410Z
2012-08-22T19:48:31.940Z
2012-08-22T19:48:31.940Z
Jeffε
<p>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:</p>

<p>F + V = I/2 + 2.</p>

<p>All I actually care about is:</p>

<p>F + V &lt; I/2.</p>

<p>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? </p>

<p>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?</p>

CC BY-SA 3.0
2012-08-21T16:13:17.163Z
What is a planar subdivision?
Tyson Williams
CC BY-SA 3.0
2012-08-21T17:52:42.823Z
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.
Herman Haverkort
CC BY-SA 3.0
2012-08-22T03:05:37.680Z
You should edit your question to include this information.
Tyson Williams
<graph-theory><cg.comp-geom><topology>
Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions
Herman Haverkort
# Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions

(Asked by: username_0 on 2012-08-21)

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?

**Tags:** graph-theory, cg.comp-geom, topology

> **Comments:**
> **username_1**: What is a planar subdivision?  
> **username_0**: 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.  
> **username_1**: You should edit your question to include this information.  

---

## 2 answers

### Answer by username_2 on 2012-08-22. Score: 6

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

> **Comments:**
> **username_0**: 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  
> **username_0**: (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...  
> **username_3**: A natural assumption would be that the edges of the arrangement are connected. Otherwise, as Herman pointed out, this seems false.  

---

### Answer by username_4 on 2012-08-22. Score: 4

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 username_2's response for the correct answer to the original question.**

---

[Ziegler](http://arxiv.org/abs/math/0208073v2) 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](http://arxiv.org/abs/math/0204007v3) 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](http://arxiv.org/abs/math/0204007v3) 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})$.

> **Comments:**
> **username_5**: All of this is interesting, but isn’t the question about a lower bound on C(X)?  
> **username_4**: D'oh!!  (What?  You mean $<$ _isn't_ commutative?)  
> **username_5**: If I remember correctly, it is known that if the < on ℚ is commutative, then the polynomial hierarchy collapses to the second level.  

---

