# Combinatorially equivalent polyhedron with vertices from a given dense set

In this question we are only interested in convex polyhedra in the Euclidean space $\mathbb R^3$.

Polyhedra $P$ and $P'$ are said to be combinatorially equivalent iff there is a bijection between them (denoted here as $X\mapsto X'$) preserving the number of vertices, edges and faces and their relations (i.e. edge $E$ connects vertices $A$ and $B$ and separates faces $G$ and $H$ in $P$ iff edge $E'$ connects vertices $A'$ and $B'$ and separates faces $G'$ and $H'$ in $P'$). Note that we ignore possible chirality, and thus every polyhedron is combinatorially equivalent to its mirror image.

Recall that a subset $S$ of $\mathbb R^3$ is dense iff there is a point from $S$ in every neighborhood of every point of $\mathbb R^3$. For example, the set of all points with rational coordinates is dense.

Question: Is it true that for every dense subset $S$ and every polyhedron $P$ there is a combinatorially equivalent polyhedron whose all vertices belong to $S$?

• It's kinda obvious for me that it is always possible to find a combinatorially equalent skeleton, but I have doubts about faces can always be made planar. – Vladimir Reshetnikov Feb 19 '16 at 19:47
• Is there some obvious counterexample that tells us, that $S = \mathbb Z^3$ doesn't work? It seems to me that it might be enough and if that's the case, your question follows from this in a straightforward fashion. – Stefan Mesken Feb 19 '16 at 19:50
• @Stefan $\mathbb Z^3$ is not dense in $\mathbb R^3$ – Vladimir Reshetnikov Feb 19 '16 at 20:11
• Sure, but it seems to me that your claim might hold for $S = \mathbb Z^3$ and if one can prove that, the result for dense subsets follows easily. – Stefan Mesken Feb 19 '16 at 23:50
• @Stefan Thanks. In your (deleted) answer you mentioned that by adding additional vertices any polyhedron can be transformed into a polyhedron with only triangular faces. You further assumed that those vertices can be safely removed later, after we "snap vertices to grid", restoring combinatorial properties of the original polyhedron. I think there is a problem with this step. If we started with a quadrilateral face, then after the transformation its 4 vertices might be not coplanar anymore, so they cannot become the vertices of a quadrilateral face in the transformed polyhedron. – Vladimir Reshetnikov Feb 21 '16 at 2:26

Your comment guided me onto the right track.

Claim. There is a dense subset $S \subseteq \mathbb R^3$ that doesn't contain $4$ distinct, coplanar points.

Proof. Fix a countable basis $\mathcal B = \{ O_n \mid n \in \mathbb N \}$ for the topology of $\mathbb R^3$ not containing $\emptyset$ as an element. We recursively construct a sequence $(S_n \mid n \in \mathbb N_0)$ such that for all $m,n \in \mathbb N_0$ with $m < n$

• $S_m$ is finite,
• $S_m \subseteq S_n$,
• if $0 < m$, then $S_m \cap O_m \neq \emptyset$,
• no $3$ distinct points of $S_m$ are colinear and
• no $4$ distinct points of $S_m$ are coplanar.

If we manage to construct such a sequence, then $S = \bigcup \{ S_n \mid n \in \mathbb N_0 \}$ is countable, dense and doesn't contain $4$ distinct coplanar points. Towards this end let $S_0$ be any set of $4$ points that are not coplanar and such that no $3$ points of $S_0$ are colinear (e.g. $S_0 = \{(0,0,0), (1,0,0), (0,1,0), (0,0,1) \}$).

Given $S_n$ let $[S_n]^3$ be the set of all subsets of $S_n$ that contain precisely $3$ distinct points. Since no $3$ points of $S_n$ are colinear, any $s \in [S_n]^3$ spans a two dimensional, affine subspace of $\mathbb R^3$ which we denote by $P_s$. Let $[S_n]^2$ be the set of all subset of $S_n$ that contain precisely $2$ distinct points. For each $s \in [S_n]^2$ let $L_s$ be the affine line spanned by $s$. Let $X = \bigcup \{ P_s \mid s \in [S_n]^3 \} \cup \bigcup \{ L_s \mid s \in [S_n]^2 \}$. Since $X$ is a finite union of sets with Lebesgue measure $0$, we know that $X$ has Lebesgue measure $0$. In particular, this yields $O_n \setminus X \neq \emptyset$. Choosing some $s_n \in O_n \setminus X$, we let $S_{n+1} = S_n \cup \{s_n\}$. $\square$

If $S$ is as in the claim, there is no polyhedra with vertices in $S$ that is combinatorially equivalent to the 'unit cube'. So your question indeed has a negative answer - contrary to my initial instinct.