Do there exist "expanding" $1$-skeletons of simple $4$-polytopes?

Question

Let $\{ G_n \}_{n \ge 1}$ be a sequence of graphs such that the number of vertices of $G_n$ tends to $\infty$ as $n \to \infty$. We say that $\{ G_n \}_{n \ge 1}$ is an expander family if $\lambda_2( G_n)$ is bounded away from $0$ as $n \to \infty$. Here $\lambda_2(H)$ is the smallest positive eigenvalue of the normalized graph Laplacian of $H$.

If every $G_n$ is the $1$-skeleton of a simple $3$-polytope, you can not have an expander family. This follows from the planar separator theorem.

What if every $G_n$ is the $1$-skeleton of a simple $4$-polytope? If you relax "simple" then there are obvious examples — in particular, cyclic polytopes in dimension $4$ have complete graphs for their $1$-skeletons, so they are expanders.

If it is hard to come up with an example for simple $4$-polytope, does it make it easier if we allow the dual graph of an arbitrary simplicial $3$-sphere?

Answer 1

As far as I know there are no examples of graphs of simple 4-polytopes (or simple $d$-polytopes, for fixed $d$) that are expanders, and not even such examples for the dual graphs for triangulations of spheres of fixed dimensions. Some information on expansion properties of graphs of polytopes can be found in my chapter polytope skeletons and paths of the Handbook of Discrete and Computational Geometry (Goodman and O'Rourke, eds.).

There is a conjecture that graphs of polytopes are not very good expanders: Let $d$ be fixed. The conjecture asserts that a graph of every simple $d$-polytope with $n$ vertices can be separated into two parts, each having at least $n/3$ vertices by removing $O(n^{1-1/(d-1)})$ vertices.

This is known to be false for dual graphs to triangulations. It is known that there are dual graphs to triangulations of $S^3$ which cannot be separated even by $O(n / \log n)$ vertices. This is a construction from G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis. "Separators for sphere packings and nearest neighbor graphs." J. ACM, 44(1):1-29, 1997. (PDF download) (I would be happy to see a nice exposition of this construction.)

On the positive side it is known that dual to neighborly $d$ polytopes with $n$ facets are $\epsilon$-expanders for $\epsilon =n^{-4}$. This is far from the good expansion in the question but good enough to give a polynomial upper bound in $n$ for the diameter. Unfortunately general simple $d$ polytopes can be fairly poor expanders as seen by gluing two large simplicial polytopes along a facet and taking the dual.