# Upper bound theorem
The upper bound theorem is a result in convex geometry stating that, among all d-dimensional convex polytopes with n vertices, the cyclic polytope has the largest possible number of faces of every dimension[1](https://kam.mff.cuni.cz/~matousek/kvg1-tb.pdf). It answers the question of how combinatorially complex a polytope can be once its dimension and vertex count are fixed, and it supplies the worst-case output size for convex hull algorithms in computational geometry[2](https://www.cis.upenn.edu/~jean/combtopol-n.pdf).
| Key fact | Detail |
|---|---|
| Statement | For any d-polytope P with n vertices, \( f_k(P) \le f_k(C(d,n)) \) for all \( k = 1, \ldots, d-1 \), where \( C(d,n) \) is a cyclic polytope[3](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html) |
| Conjecture origin | Formulated by T. S. Motzkin in 1957 as the upper bound conjecture[2](https://www.cis.upenn.edu/~jean/combtopol-n.pdf) |
| Proof for polytopes | Peter McMullen, 1970, using shellings of the boundary complex[4](https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/S0025579300002850) |
| Extension to spheres | Richard P. Stanley, 1975, proved the bound for simplicial spheres via Cohen–Macaulay rings[5](https://onlinelibrary.wiley.com/doi/pdf/10.1002/sapm1975542135) |
| Growth rate | A d-polytope with n vertices has at most \( 2\binom{n}{\lfloor d/2 \rfloor} \) facets; for fixed d the face counts grow as \( n^{\lfloor d/2 \rfloor} \)[1](https://kam.mff.cuni.cz/~matousek/kvg1-tb.pdf) |
| Dual form | The maximum number of vertices of a d-polytope with m facets is attained by a polytope dual to the cyclic polytope C(d, m)[3](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html) |
| Algorithmic consequence | The convex hull of n points in \( \mathbb{R}^d \) has \( O(n^{\lfloor d/2 \rfloor}) \) facets, which bounds the output size of hull algorithms[6](https://www.cs.cmu.edu/afs/cs/academic/class/15456-f15/Handouts/cmsc754-lects.pdf) |
## The cyclic polytope
The extremal object in the theorem is the cyclic polytope, defined as the convex hull of n distinct points on the moment curve \( M_d = \{(t, t^2, \ldots, t^d) : t \in \mathbb{R}\} \) in \( \mathbb{R}^d \)[7](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/13483049ECEDF0F2D760C50BAE8D6F21/S0025579300002850a.pdf/div-class-title-the-maximum-numbers-of-faces-of-a-convex-polytope-div.pdf). Its combinatorial type, meaning its face lattice, does not depend on which n points on the curve are chosen, so it is written \( C(d,n) \) or \( C_d(n) \)[3](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html) • [7](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/13483049ECEDF0F2D760C50BAE8D6F21/S0025579300002850a.pdf/div-class-title-the-maximum-numbers-of-faces-of-a-convex-polytope-div.pdf).
Two properties make the cyclic polytope the record holder. It is simplicial, meaning all its proper faces are simplices, and it is neighborly: for each \( r \le \lfloor d/2 \rfloor \), every subset of r vertices is the vertex set of a face[7](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/13483049ECEDF0F2D760C50BAE8D6F21/S0025579300002850a.pdf/div-class-title-the-maximum-numbers-of-faces-of-a-convex-polytope-div.pdf). Neighborliness is what pushes the face numbers up, because for \( i \le \lfloor d/2 \rfloor \) the number \( f_{i-1}(C_d(n)) \) equals \( \binom{n}{i} \), which is the largest count of \( (i-1) \)-faces any \( (d-1) \)-dimensional simplicial complex on n vertices can have[8](https://sites.math.washington.edu/~novik/publications/ICM2022.pdf).
Which subsets of vertices form facets is described by Gale's evenness condition: for vertices \( t_1 < t_2 < \cdots < t_n \) on the moment curve, a d-subset \( T_d \) is a facet exactly when any two elements outside \( T_d \) are separated by an even number of elements of \( T_d \)[9](https://etd.lib.metu.edu.tr/upload/12622511/index.pdf).
## Statement and quantitative form
Writing \( f_k(P) \) for the number of k-dimensional faces of P, the theorem says
\[ f_k(P) \le f_k(C(d,n)) \quad \text{for all } k = 1, \ldots, d-1, \]
for every d-polytope P with n vertices[3](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html). The face numbers of the cyclic polytope itself are given by an explicit binomial-coefficient formula, and in particular the number of facets is[3](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html)
\[ f_{d-1}(C(d,n)) = \binom{n - \lfloor (d+1)/2 \rfloor}{n-d} + \binom{n - \lfloor (d+2)/2 \rfloor}{n-d}. \]
For fixed d this is \( O(n^{\lfloor d/2 \rfloor}) \)[10](https://www.csun.edu/~ctoth/Handbook/chap17.pdf). When precision is unnecessary, a looser form of the result says that any convex polytope of dimension d having n vertices is bounded in its number of facets by \( 2\binom{n}{\lfloor d/2 \rfloor} \), and in its total count of faces by \( 2^{d+1}\binom{n}{\lfloor d/2 \rfloor} \)[1](https://kam.mff.cuni.cz/~matousek/kvg1-tb.pdf).
Concrete values illustrate how quickly the counts grow. The cyclic polytope \( C(5,30) \), a 5-polytope with 30 vertices, has \( f_0 = 30 \), \( f_1 = 435 \), \( f_2 = 1460 \), \( f_3 = 1755 \), and \( f_4 = 702 \)[3](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html).
The theorem also has a dual form: for any d-polytope with m facets, \( f_k(P) \le f_{d-k-1}(C(d,m)) \) for \( k = 0, 1, \ldots, d-2 \). This gives, for example, the maximum number of vertices a d-polytope with m facets can have[3](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html).
## History
The problem of maximizing \( f_j(P) \) over d-polytopes with a fixed number of vertices was recorded by Motzkin in 1957 as the upper bound conjecture[7](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/13483049ECEDF0F2D760C50BAE8D6F21/S0025579300002850a.pdf/div-class-title-the-maximum-numbers-of-faces-of-a-convex-polytope-div.pdf). The cases \( d \le 4 \) were already known to Brückner in 1893, and partial contributions came from Fieldhouse in 1961, [Victor Klee](https://www.edgepedia.org/victor-klee) in 1964, and Gale in 1964[7](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/13483049ECEDF0F2D760C50BAE8D6F21/S0025579300002850a.pdf/div-class-title-the-maximum-numbers-of-faces-of-a-convex-polytope-div.pdf). The question remained open for roughly twenty years before McMullen settled it in 1970, in a proof that uses shellings of the boundary complex, a combinatorial decomposition of the polytope's boundary into facets added one at a time[2](https://www.cis.upenn.edu/~jean/combtopol-n.pdf) • [4](https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/S0025579300002850). McMullen discovered the proof while writing a book with Shephard[11](https://www.ms.uky.edu/~lee/ma714fa13/notes.pdf).
**Extension beyond polytopes.** In 1975 [Richard P. Stanley](https://www.edgepedia.org/richard-p-stanley), a mathematician at the [Massachusetts Institute of Technology](https://www.edgepedia.org/massachusetts-institute-of-technology), proved a more general statement: for any triangulation of a \( (d-1) \)-dimensional sphere with n vertices, the number of i-dimensional faces is at most \( c_i(n,d) \), the corresponding count for the cyclic polytope[5](https://onlinelibrary.wiley.com/doi/pdf/10.1002/sapm1975542135). His proof passes through the Stanley–Reisner ring, a commutative ring built from the squarefree monomials supported on the faces of the complex, and uses G. Reisner's theorem that this ring is Cohen–Macaulay for a simplicial sphere[5](https://onlinelibrary.wiley.com/doi/pdf/10.1002/sapm1975542135) • [12](https://www.math-challenge.org/en/projects/upper_bound_simplicial_spheres/problems/upper_bound_simplicial_spheres). Since not every abstract simplicial sphere is the boundary complex of a polytope, this strictly extends McMullen's result[12](https://www.math-challenge.org/en/projects/upper_bound_simplicial_spheres/problems/upper_bound_simplicial_spheres).
A second proof was given by [Noga Alon](https://www.edgepedia.org/noga-alon) and [Gil Kalai](https://www.edgepedia.org/gil-kalai) in 1985 in the European Journal of Combinatorics; it is shorter and applies to arbitrary shellable triangulations of \( (d-1) \)-spheres as well as to d-representable complexes[13](https://collaborate.princeton.edu/en/publications/a-simple-proof-of-the-upper-bound-theorem/).
## Why the exponent is ⌊d/2⌋
An elementary argument shows where the exponent \( \lfloor d/2 \rfloor \) comes from. Passing to the dual polytope, which is simple, one rotates it so that no two vertices share the same height. At any vertex, of the d incident edges at least \( \lceil d/2 \rceil \) point upward or at least \( \lceil d/2 \rceil \) point downward; each \( \lceil d/2 \rceil \)-tuple of such edges determines a face for which the vertex is respectively the lowest or the highest vertex. Since each face has a unique lowest and highest vertex, the number of vertices is at most twice the number of \( \lceil d/2 \rceil \)-faces, which yields the \( n^{\lfloor d/2 \rfloor} \) growth rate[1](https://kam.mff.cuni.cz/~matousek/kvg1-tb.pdf).
The same source records a caveat about polytopes that are neither simple nor simplicial: for fixed dimension, their total combinatorial complexity can exceed in order of magnitude both the number of facets and the number of vertices[1](https://kam.mff.cuni.cz/~matousek/kvg1-tb.pdf).
## Role in computational geometry
The theorem fixes the worst-case output size of the convex hull problem. Any convex hull algorithm for n points in \( \mathbb{R}^d \) must in the worst case produce \( O(n^{\lfloor d/2 \rfloor}) \) facets, and for fixed \( d \ge 4 \) there are algorithms running in \( O(n^{\lfloor d/2 \rfloor}) \) time, which cannot be improved because the largest possible output is of the same order[6](https://www.cs.cmu.edu/afs/cs/academic/class/15456-f15/Handouts/cmsc754-lects.pdf) • [14](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node18.html). This is what makes exact hull computation tractable in low dimensions and expensive in high ones[15](https://technav.ieee.org/topic/convex-hulls/).
## Place in f-vector theory
The upper bound theorem is one half of the classical description of face numbers. The complementary lower bound theorem, due to [David Barnette](https://www.edgepedia.org/david-w-barnette) in 1971 and 1973, gives the minimum face numbers, attained by stacked polytopes[2](https://www.cis.upenn.edu/~jean/combtopol-n.pdf) • [10](https://www.csun.edu/~ctoth/Handbook/chap17.pdf). The full characterization of f-vectors of simplicial polytopes is the g-theorem, proved in 1980 with necessity by Stanley, via the hard Lefschetz theorem for toric varieties, and sufficiency by Louis Billera and Carl Lee[16](https://arxiv.org/abs/1706.03322). Whether the same characterization extends to all simplicial spheres is the g-conjecture, which remained open for decades; it was announced as proved for simplicial spheres by Karim Adiprasito in December 2018, with a different proof by Papadakis and Petrotou in 2020[17](https://mathoverflow.net/questions/349406/updates-to-stanleys-1999-survey-of-positivity-problems-in-algebraic-combinatori).
The upper bound theorem has also been extended to classes of manifolds. Isabella Novik, a mathematician at the University of Washington, proved a version for homology manifolds: a \( (d-1) \)-dimensional homology manifold with n vertices satisfies \( f_k(\Delta) \le f_k(C_d(n)) \) for \( 1 \le k \le d-1 \) when d is even, and for odd d under additional conditions on the [Euler characteristic](https://www.edgepedia.org/euler-characteristic) or Betti numbers[10](https://www.csun.edu/~ctoth/Handbook/chap17.pdf).
## References
1. [Jiří Matoušek, Lectures on Discrete Geometry, Chapter 5: Convex Polytopes, Section 5.5, The Upper Bound Theorem](https://kam.mff.cuni.cz/~matousek/kvg1-tb.pdf)
2. [Jean Gallier, Notes on Convex Sets, Polytopes, Polyhedra, Chapter 7: The Upper Bound Theorem and Cyclic Polytopes](https://www.cis.upenn.edu/~jean/combtopol-n.pdf)
3. [Komei Fukuda, Polyhedra FAQ: What is the best upper bound of the numbers of k-dimensional faces of a d-polytope with n vertices?](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node12.html)
4. [P. McMullen (1970). The maximum numbers of faces of a convex polytope. Mathematika 17: 179–184.](https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/S0025579300002850)
5. [Richard P. Stanley (1975). The Upper Bound Conjecture and Cohen–Macaulay Rings. Studies in Applied Mathematics 54(2): 135–142.](https://onlinelibrary.wiley.com/doi/pdf/10.1002/sapm1975542135)
6. [CMSC 754 lecture notes, University of Maryland: The Upper Bound Theorem](https://www.cs.cmu.edu/afs/cs/academic/class/15456-f15/Handouts/cmsc754-lects.pdf)
7. [the maximum numbers of faces of a convex polytope](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/13483049ECEDF0F2D760C50BAE8D6F21/S0025579300002850a.pdf/div-class-title-the-maximum-numbers-of-faces-of-a-convex-polytope-div.pdf)
8. [Isabella Novik, Face numbers: the upper bound side of the story, ICM 2022](https://sites.math.washington.edu/~novik/publications/ICM2022.pdf)
9. [METU thesis: The Upper Bound Theorem and Gale's evenness condition](https://etd.lib.metu.edu.tr/upload/12622511/index.pdf)
10. [L. J. Billera and A. Björner, Chapter 17: Face numbers of polytopes and complexes, Handbook of Discrete and Computational Geometry](https://www.csun.edu/~ctoth/Handbook/chap17.pdf)
11. [MA 714 course notes, University of Kentucky: The Upper Bound Theorem](https://www.ms.uky.edu/~lee/ma714fa13/notes.pdf)
12. [Math-Challenge: Upper bound theorem for geometric simplicial spheres (Stanley 1975)](https://www.math-challenge.org/en/projects/upper_bound_simplicial_spheres/problems/upper_bound_simplicial_spheres)
13. [N. Alon and G. Kalai (1985). A Simple Proof of the Upper Bound Theorem. European Journal of Combinatorics 6(3): 211–214.](https://collaborate.princeton.edu/en/publications/a-simple-proof-of-the-upper-bound-theorem/)
14. [Komei Fukuda, Polyhedra FAQ: How do we measure the complexity of a convex hull algorithm?](https://www.cs.mcgill.ca/~fukuda/soft/polyfaq/node18.html)
15. [IEEE Technology Navigator: Convex hulls](https://technav.ieee.org/topic/convex-hulls/)
16. [The face numbers of homology spheres, arXiv:1706.03322](https://arxiv.org/abs/1706.03322)
17. [MathOverflow: Updates to Stanley's 1999 survey of positivity problems in algebraic combinatorics](https://mathoverflow.net/questions/349406/updates-to-stanleys-1999-survey-of-positivity-problems-in-algebraic-combinatori)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics › Geometric, polyhedral, and topological combinatorics › Face numbers and face vectors*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 11, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license