A Simple Proof of the Upper Bound Theorem

N. Alon; G. Kalai

doi:10.1016/S0195-6698(85)80029-9

A Simple Proof of the Upper Bound Theorem

N. Alon, G. Kalai

Research output: Contribution to journal › Article › peer-review

25 Scopus citations

Abstract

Let c_i(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 c_i(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 language	English (US)
Pages (from-to)	211-214
Number of pages	4
Journal	European Journal of Combinatorics
Volume	6
Issue number	3
DOIs	https://doi.org/10.1016/S0195-6698(85)80029-9
State	Published - 1985
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0195-6698(85)80029-9

Cite this

@article{7baad809b35a411ebe5717bbea093e1d,

title = "A Simple Proof of the Upper Bound Theorem",

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.",

author = "N. Alon and G. Kalai",

year = "1985",

doi = "10.1016/S0195-6698(85)80029-9",

language = "English (US)",

volume = "6",

pages = "211--214",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - A Simple Proof of the Upper Bound Theorem

AU - Alon, N.

AU - Kalai, G.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85016174015&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016174015&partnerID=8YFLogxK

U2 - 10.1016/S0195-6698(85)80029-9

DO - 10.1016/S0195-6698(85)80029-9

M3 - Article

AN - SCOPUS:85016174015

SN - 0195-6698

VL - 6

SP - 211

EP - 214

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 3

ER -

A Simple Proof of the Upper Bound Theorem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this