Convex Polytopes: Seperation, Expansion, Chordality, and Approximations of Smooth Bodies

I am happy to report on two beautiful results on convex polytopes. One disproves an old conjecture of mine and one proves an old conjecture of mine.

Does Lipton-Tarjan’s theorem extends to high dimensions? Can polytopes be expanders?

Lipton and Tarjan proved that a planar graph (hence the graph of a 3-polytope) with n vertices can be separated to connected parts each with no more than 2n/3 vertices by deleting $C\sqrt n$ vertices. I proposed a similar property (with a different exponent depending on the dimension) for graphs of simple polytopes in higher dimensions. This turned out to be false.

Simple polytopes without small separators:

Lauri Loiskekoski, Günter M. Ziegler

Abstract:  We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least $\Omega(n/log^{3/2}n)$ This disproves a conjecture by Kalai from 1991/2004.

A major remaining open question is if we can have examples of graphs of simple 4-polytopes where every separator has at least cn vertices or perhaps even examples of such graphs that are expanders. (I conjecture that the answer is negative).

Expansion is closely related to diameter and there are various interesting higher dimensional analogs for the expansion property, for diameter question, and for the non-revisiting property which is crucial in the study of diameter of polytopal graphs.

Adiprasito, Nevo and Samper: Higher chordality and approximating smooth bodies by polytopes.

Consider a sequence of polytopes $P_n$ that converge to a smooth convex body K. It is easy that the number of vertices of these polytopes must tend to infinity and there are interesting theorems relating the quality of the approximation and the the number of vertices.

For a d-dimensional simplicial polytope P there are is remarkable set of parameters introduced by McMullen $(g_1(P),g_2(P),\dots g_m(P))$ where m=[d/2]. $g_1(P)$ is the number of vertices minus (d+1).  $g_2(P)$ is the dimension of the space of stresses of a framework based on P. The nonnegativity of these numbers is the generalized lower bound theorem which is part of Stanley’s 1980 “g-theorem” (necessity part), which is one of the most important results on convex polytopes in the last decades. Here on the blog we devoted several posts (I,II,III,IV) to the g-theorem and the related g-conjecture for simplicial spheres. (Probably the g-conjecture for spheres is the single problem I devoted the most effort to in my career.)

I conjectured that for a sequence of polytopes $P_n$ that converge to a smooth convex body K, $g_i(K)$ tends to infinity for ≤ [d/2]. This was now proved.

Higher Chordality III: A Geometric Lower Bound Theorem

Karim A. Adiprasito, Eran Nevo, José Alejandro Samper

Abstract: We resolve a conjecture of Kalai relating approximation theory of convex bodies by simplicial polytopes to the face numbers and primitive Betti numbers of these polytopes and their toric varieties. The proof uses higher notions of chordality. Further, for $C^2$-convex bodies, asymptotically tight lower bounds on the g-numbers of the approximating polytopes are given, in terms of their Hausdorff distance from the convex body.

The paper continues a project which led already to:

Higher chordality I. From graphs to complexes by Karim A. Adiprasito, Eran Nevo, Jose A. Samper and

Further extensions for general polytopes, and similar results regarding the nonlinear part of the g-theorem would be of great interest.

More news in brief

A polymath10 project devoted to the Erdos Rado Delta System Conjecture will start over this blog in about a week. (This is one of the project proposals by Tim Gowers in this post.)  Quanta magazine has an article on important progress by Maria Chudnovsky, Irene Lo,  Frédéric Maffray, Nicolas Trotignon and Kristina Vušković towards an efficient coloring argorithm for perfect graphs! (BTW, while we have several notions of chordality in high dimensions I am curious about appropriate notions of perfectness.)  In this MathOverflow answer, I report (and describe the background) on the 2013 paper by Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volec   “Subcubic triangle-free graphs have fractional chromatic number at most 14/5“.  This recent mathoverflow question asks for proposals for polymath projects.

$latex \Omega(n/log^{3/2}n)$.

In https://arxiv.org/abs/1708.06718 Lauri Loiskekoski and Günter M. Ziegler improved their constructions! They got $\Omega (n/\log n)$.