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
10f0-f1+9f3-2f03 \ge 45
- the first Bayer inequality [Ba, p. 149]
4f0-f1+f3 \ge 15
- and the second Bayer inequality [Ba, p. 145]
2f0+f1+3f3-f03 \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) := (f1+f2) / (f0+f3)
complexity(P) := f03 / (f0+f3)
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/(f0+f3),
in particular,
4 complexity(P) + fatness(P) < 19,
-
the sum of the first Bayer inequality and its dual as:
fatness(P) \le 5 - 30/(f0+f3),
in particular,
fatness(P) < 5,
-
and the (self-dual) second Bayer inequality as:
2 complexity(P) - fatness(P) \le 5 - 30/(f0+f3),
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
f0 = 2^n = 4·2n-2,
f1 = n·2n-1 = 2n·2n-2,
f2 = 3(n-2)2n-2 = 3(n-2)·2n-2,
f3 = (n-2)2n-2 = (n-2)·2n-2, and
f03 = 8f3 = (n-2)2n+1 = 8(n-2)·2n-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
4f0-f1+ f3 = (4·4 - 2n + (n-2))2n-2
= (14 - n)2n-2 \ge 15
which is violated for n \ge 14!
However, the dual inequality
2f0-f1+3f3 = (2·4 - 2n + 3(n-2))2n-2
= (n - 2)2n-2 \ge 15
is satisfied (for n\ge 4),
and so is the sum of the two inequalities, which
evaluates to 12·2n-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