A Simple Proof of the Upper Bound Theorem

N. Alon, G. Kalai

Research output: Contribution to journalArticle

16 Scopus citations

Abstract

Let ci(n, d) be the number of i-dimensional faces of a cyclic d-polytope on n vertices. We present a simple new proof of the upper bound theorem for convex polytopes, which asserts that the number of i-dimensional faces of any d-polytope on n vertices is at most ci(n, d). Our proof applies for arbitrary shellable triangulations of (d−1) spheres. Our method provides also a simple proof of the upper bound theorem for d-representable complexes.

Original languageEnglish (US)
Pages (from-to)211-214
Number of pages4
JournalEuropean Journal of Combinatorics
Volume6
Issue number3
DOIs
StatePublished - Jan 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'A Simple Proof of the Upper Bound Theorem'. Together they form a unique fingerprint.

  • Cite this