What is a polytope/polyhedron with $O(n)$ vertices each with degree $O(\sqrt{n})$?

Question

Is there a class of polytopes (preferably polyhedra) where if the number of vertices is $O(n)$, then the degree of each vertex is $O(\sqrt{n})$? By "degree of a vertex", I mean the number of edges coming out of that vertex.

As a non-example, a Hypercube with $O(n)$ vertices has a degree of $O(\log(n))$ for each vertex (which isn't enough).

Furthermore, it would be a great plus if the polytope could be quickly and easily specified in a computer program. I.e. If the vertices were indexed, one could quickly enumerate the indices of the vertices connected to the $i$th vertex. For example, it's very easy say which vertices are connected to a particular one in a hypercube by just enumerating all the bit-strings that are off by one from the bit-string of $i$.

Answer 1

You might be interested into the set of rectified orthoplexes.

The vertex count of the rectified orthoplex, as a function of the dimension, is $2\cdot D\cdot (D-1)$.

The count of edges per vertex of the rectified orthoplex, as a function of the dimension, is $4\cdot (D-2)$.

Thus indeed in the long run the former increases more or less like the square of the latter.

Note that the vertex figure of the rectified orthoplex is nothing but the orthoplex prism.

--- rk

Answer 2

I try to give you some geometric intuition and some actual coordinates to the answer of Dr. Klitzing.

The "rectified $d$-orthoplex" has vertices whose coordinates are all the vertex permutations and sign selections of the vector

$$(\pm1 ,\pm 1, 0,...,0)\in\Bbb R^d.$$

In other words, choose two coordinates, make them $1$ or $-1$, and make all the other $0$. This is a vertex of the "rectified $d$-orthoplex", and every vertex is of this form. It is an easy combinatorial exercise to see that this is indeed $2d(d-1)$ vertices.

The edge-graph of this polytope is the line graph of the edge-graph of the orthoplex (also known as the cocktail party graph). The edge-graph of the $d$-orthoplex can e.g. be constructed as the complement graph of the disjoint union of $d$ isolated edges. Its degree is $2(d-1)$. Hence, the degree of its line graph is $2[2(d-1)-1] = 4d-6$.

So indeed, you got a family with quadratically growing vertex count and linear growing degree, which conversely means, that you have an $\mathcal O(\sqrt n)$-growth for the degree if $n$ is the number of vertices.