Isabella Novik and Hailun Zheng: Neighborly centrally symmetric spheres exist in all dimensions!

Combinatorics and more 2019-08-20

A tweet-long summary: The cyclic polytope is wonderful and whenever we construct an analogous object we are happy. Examples: Neighborly cubic polytopes; The amplituhedron; and as of last week, the Novik-Zheng new construction of neighborly centrally symmetric spheres!

At last: Neighborly CS spheres!

The news: Isabella Novik and Hailun Zheng’ paper Highly neighborly centrally symmetric spheres, resolves an old standing problem in this field.

Here is the abstract:

In 1995, Jockusch constructed an infinite family of centrally symmetric 3-dimensional simplicial spheres that are cs-2-neighborly. Here we generalize his construction and show that for all d ≥ 4 and n ≥ d, there exists a centrally symmetric (d − 1)-dimensional simplicial sphere with 2n vertices that is cs-[d/2]-neighborly. This result combined with work of Adin and Stanley completely resolves the upper bound problem for centrally symmetric simplicial spheres.

Congratulations to Isabella and Hailun!

Some background to the Novik and Zheng breakthrough

Centrally symmetric bodies: A centrally symmetric (cs) polytope convex body in $\mathbb R^d$ satisfies $x \in P$ implies $-x \in P$ . Centrally symmetric bodies are the unit balls of normed spaces.

Centrally symmetric simplicial spheres: A triangulation $K$ of a $(d-1)$ -dimensional sphere with a set $V$ of vertices is centrally symmetric if there is an involution $\phi$ on $V$ that $\phi$ maps a face of $K$ to a face of $K$ and for every vertex $v$ , $\phi(v) \ne v$ and $\{v , \phi (v)\}$ is not an edge of $K$ . The boundary complex of a cs $d$ -polytopes is a cs triangulation of $S^{d-1}$ .

Neighborliness. A simplicial complex $K$ is $m$ -neighborly of every set of $m$ vertices of $P$ form a face. (The definition was first considered for simplicial $d$ -polytopes $P$ .) The cyclic $d$ -polytope with $n$ vertices is $[d/2]$ -neighborly. (The only ( $[d/2]$ +1)-neighborly simplicial $(d-1)$ -sphere is the simplex. There are many other $[d/2]$ -neighborly simplicial $d$ -polytopes and $(d-1)$ -spheres.

cs-Neighborliness. Let $K$ be a simplicial complex with an involution $\phi$ on its vertices which acts on $K$ (maps faces to faces) and has the property that $\phi(v)$ is not adjacent to $v$ (and $\phi (v) \ne v$ ). We will call $v$ and $\phi (v)$ antipodal. $K$ is cs- $m$ -neighborly if every set of $m$ vertices that contains no pair of antipodal vertices is a face of $K$ . The only cs- $m$ -neighborly simplicial sphere is the boundary complex of the cross polytope.

The existence of cs- $[d/2]$ -neighborly spheres. It was an important open question whether cs $[d/2]$ -neighborly simplicial spheres exist. (The only cs- $([d/2]+1)$ -neighborly spheres is the boundary complex of the cross polytope.) The first example (which is not a cross polytope) was given by Grünbaum in 1969 in his paper “The importance of being straight(?).” In 1995 Jockusch constructed an infinite family cs-2-neighborly centrally symmetric 3-dimensional simplicial spheres. This problem has now been solved by Novik and Zheng.

Neighborly centrally symmetric polytopes. In the 1960s Grünbaum noted the big difference between neighborly centrally symmetric spheres and centrally symmetric polytopes. He proved (This is Theorem 4.1 in his book “Convex polytopes”) that no cs-2-neighborly 4 polytope with 12 vertices exists. This is an example of the important themes of “straightening” or “linearizing” combimatorial objects and of extending theorems from the “straight” or “linear” case to more general combinatorial settings.)

This result by Grünbaum was extended in various directions. Let me mention two major results in the field:

Theorem McMullen and Shephard (1968): A cs d-dimensional polytope with 2(d + 2) vertices cannot be more than cs-⌊(d + 1)/3⌋-neighborly.

Theorem Linial and Novik (2006): A cs-2-neighborly d-dimensional polytope has at most $2^d$ ;

Novik (2017) constructed cs-2-neighborly d polytopes with $2^{d-1}+1$ vertices. She used a 2017 breakthrough construction by Gerencsér–Harang of an acute set of size $2^{d-1}+1$ in $\mathbb R^d$ . (A set S is acute if every three points from S determine an acute triangle.)

Face numbers of centrally-symmetric polytopes and spheres. As the abstract asserts the new construction is related to questions about face numbers of centrally symmetric polytopes, spheres and other cellular objects. In fact, this was the next item in our planned posts on algebraic combinatorics of cellular objects. (The first and only post so far is here.) Here is a recent survey by Isabella Novik A tale on centrally symmetric polytopes and spheres.

Upper bound theorems. Neighborly polytopes and spheres are the equality cases of the upper bound theorem (proved by McMullen for polytopes and by Stanley for spheres). A version of the upper bound inequality for centrally symmetric spheres was proved by Adin and Stanley and the new construction shows that the Adin-Stanley inequality is tight. For more on the upper bound theorem and neighborliness see Section 2 of my 2000 survey Combinatorics with geometric flavor. See also the post How the g-conjecture came about and the post Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found.