From:           "Guenter M. Ziegler" <ziegler@math.TU-Berlin.DE>
Date:           Thu, 25 May 2000 15:21:54 +0200 (MET DST)
To:             billera@math.cornell.edu, jrge@math.kth.se, bayer@kuhub.cc.ukans.edu,
                kalai@math.huji.ac.il, eppstein@ics.uci.edu, jeffe@cs.uiuc.edu
Subject:        Flag-vector conjectures for 4-polytopes
Cc:             joswig@math.TU-Berlin.DE

Summary: On three flag-vector conjectures for 4-polytopes.

The inequality proposed by L.J. Billera and R. Ehrenborg and the two inequalities suggested by M. Bayer are false for polytopes, disproved by the neighborly cubical polytopes. The sum of Bayer's first inequality and its dual is false for spheres (as constructed by Eppstein), but open for polytopes.

Dear Colleagues,

This is a short report on the current status of three conjectured inequalities about the flag vectors of 4-polytopes, namely

the Billera-Ehrenborg inequality 10f₀-f₁+9f₃-2f₀₃ \ge 45
the first Bayer inequality [Ba, p. 149] 4f₀-f₁+f₃ \ge 15
and the second Bayer inequality [Ba, p. 145] 2f₀+f₁+3f₃-f₀₃ \ge 15

Billera-Ehrenborg is from personal communication (1999), Bayer's inequalities are from [Ba] M.M. Bayer: extended f-vectors of 4-polytopes, J. Combinatorial Theory, Ser. A 44 (1987), 141-151.

Let's first rewrite the inequalities, using the following invariants of 4-polytopes:

fatness(P) := (f₁+f₂) / (f₀+f₃)
complexity(P) := f₀₃ / (f₀+f₃)

Both parameters are self-dual. To consider the parameter `fatness' is suggested by J. Erickson's page on `intricate polytopes' at compgeom.cs.uiuc.edu/~jeffe/open/intricate.html .

Then the three inequalities in question can be rewritten:

the (selfdual) Billera-Ehrenborg inequality as: 4 complexity(P) + fatness(P) \le 19 - 90/(f₀+f₃), in particular, 4 complexity(P) + fatness(P) < 19,
the sum of the first Bayer inequality and its dual as: fatness(P) \le 5 - 30/(f₀+f₃), in particular, fatness(P) < 5,
and the (self-dual) second Bayer inequality as: 2 complexity(P) - fatness(P) \le 5 - 30/(f₀+f₃), in particular, 2 complexity(P) - fatness(P) < 19.

For example, for a simple or simplicial polytope one easily gets

complexity(P) < 4 [but arbitrarily close]
fatness(P) < 3 [but arbitrarily close].

For the class of bicyclic polytopes introduced by Z. Smilansky (Bi-cyclic 4-polytopes, Israel J. Math. 70 (1990), 82-92) one can compute the flag-vectors explicitly, and finds

complexity(P) < 4 [but arbitrarily close]
fatness(P) < 4 [but arbitrarily close] so they disprove the Billera-Ehrenborg inequality.

The neighborly cubical polytopes of M. Joswig & G.M. Ziegler, Neighborly cubical polytopes, Discrete Comput. Geometry, in print have flag vectors given by

f₀ = 2^n = 4·2^n-2,
f₁ = n·2^n-1 = 2n·2^n-2,
f₂ = 3(n-2)2^n-2 = 3(n-2)·2^n-2,
f₃ = (n-2)2^n-2 = (n-2)·2^n-2, and
f₀₃ = 8f₃ = (n-2)2ⁿ⁺¹ = 8(n-2)·2^n-2. Thus complexity(P) < 8 [but arbitrarily close]
fatness(P) < 5 [but arbitrarily close] so they disprove the Billera-Ehrenborg inequality as well as the second Bayer inequality!

Incidentally, if you plug the flag-vector of the neighborly cubical polytopes into the first Bayer inequality, then you get

4f₀-f₁+ f₃ = (4·4 - 2n + (n-2))2^n-2 = (14 - n)2^n-2 \ge 15 which is violated for n \ge 14! However, the dual inequality 2f₀-f₁+3f₃ = (2·4 - 2n + 3(n-2))2^n-2 = (n - 2)2^n-2 \ge 15 is satisfied (for n\ge 4), and so is the sum of the two inequalities, which evaluates to 12·2^n-2\ge 15 (n\ge 4).

David Eppstein (1997, unpublished) has a construction of polytopes most of whose facets are octahedra and bipyramids over hexagons, occurring in ratio 3:1, and for those one computes that

complexity(P) ~ 4 [arbitrarily close]
fatness(P) ~ 5 [arbitrarily close] so they also disprove the Billera-Ehrenborg inequality.

David Eppstein (1997, unpublished) also has a construction of 3-spheres consisting of octahedra and bipyramids, for which it's not clear whether they can be realized, but where the computation yields that

complexity(P) ~ 4 [arbitrarily close]
fatness(P) < 6 [but arbitrarily close] so if they were realizable, then they would disprove Billera-Ehrenborg as well as the sum of the first Bayer inequality and its dual.

Best regards,
G"unter