Kalai's 3^d conjecture

In geometry, Kalai's 3d conjecture is a conjecture on the polyhedral combinatorics of centrally symmetric polytopes, made by Gil Kalai in 1989.[1] It states that every d-dimensional centrally symmetric polytope has at least 3d nonempty faces (including the polytope itself as a face but not including the empty set).

Examples

The cube and the octahedron, two examples for which the bound of the conjecture is tight

In two dimensions, the simplest centrally symmetric convex polygons are the parallelograms, which have four vertices, four edges, and one polygon; 4 + 4 + 1 = 9 = 32. A cube is centrally symmetric, and has 8 vertices, 12 edges, 6 square sides, and 1 solid; 8 + 12 + 6 + 1 = 27 = 33. Another three-dimensional convex polyhedron, the regular octahedron, is also centrally symmetric, and has 6 vertices, 12 edges, 8 triangular sides, and 1 solid; 6 + 12 + 8 + 1 = 27 = 33.

In higher dimensions, the hypercube [0,1]d has exactly 3d faces, each of which can be determined by specifying, for each of the d coordinate axes, whether the face projects onto that axis onto the point 0, the point 1, or the interval [0,1]. More generally, every Hanner polytope has exactly 3d faces. If Kalai's conjecture is true, these polytopes would be among the centrally symmetric polytopes with the fewest possible faces.[1]

Generalizations

In the same work as the one in which the 3d conjecture appears, Kalai conjectured more strongly that the f-vector of every convex centrally symmetric polytope P dominates the f-vector of at least one Hanner polytope H of the same dimension. This means that, for every number i from 0 to the dimension of P, the number of i-dimensional faces of P is greater than or equal to the number of i-dimensional faces of H. If it were true, this would imply the truth of the 3d conjecture; however, the stronger conjecture was later disproven.[2]

Status

The conjecture is known to be true for d ≤ 4.[2] It is also known to be true for simplicial polytopes: it follows in this case from a conjecture of Bárány & Lovász (1982) that every centrally symmetric simplicial polytope has at least as many faces of each dimension as the cross polytope, proven by Stanley (1987).[3][4] Indeed, these two previous papers were cited by Kalai as part of the basis for making his conjecture.[1] Another special class of polytopes that the conjecture has been proven for are the Hansen polytopes of split graphs, which had been used by Sanyal, Werner & Ziegler (2009) to disprove the stronger conjectures of Kalai.[5]

The 3d conjecture remains open for arbitrary polytopes in higher dimensions.

References

  1. 1 2 3 Kalai, Gil (1989), "The number of faces of centrally-symmetric polytopes", Graphs and Combinatorics, 5 (1): 389–391, doi:10.1007/BF01788696, MR 1554357.
  2. 1 2 Sanyal, Raman; Werner, Axel; Ziegler, Günter M. (2009), "On Kalai's conjectures concerning centrally symmetric polytopes", Discrete & Computational Geometry, 41 (2): 183–198, doi:10.1007/s00454-008-9104-8, MR 2471868/
  3. ↑ Bárány, I.; Lovász, L. (1982), "Borsuk's theorem and the number of facets of centrally symmetric polytopes", Acta Mathematica Academiae Scientiarum Hungaricae, 40 (3-4): 323–329, doi:10.1007/BF01903592, MR 686332.
  4. ↑ Stanley, Richard P. (1987), "On the number of faces of centrally-symmetric simplicial polytopes", Graphs and Combinatorics, 3 (1): 55–66, doi:10.1007/BF01788529, MR 932113.
  5. ↑ Freij, Ragnar; Henze, Matthias; Schmitt, Moritz W.; Ziegler, Günter M. (2013), "Face numbers of centrally symmetric polytopes produced from split graphs", Electronic Journal of Combinatorics, 20 (2): #P32, arXiv:1201.5790Freely accessible, MR 3066371.
This article is issued from Wikipedia - version of the 7/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.