Upper bound theorem

Key takeaways

Upper bound theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Upper bound theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Upper bound theorem from memory before moving on to harder problems.

Reference excerpt

In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics. Originally known as the upper bound conjecture, this statement was formulated by Theodore Motzkin, proved in 1970 by Peter McMullen, and strengthened from polytopes to subdivisions of a sphere in 1975 by Richard P. Stanley.

Cyclic polytopes

The cyclic polytope Δ ( n , d ) {\displaystyle \Delta (n,d)} may be defined as the convex hull of n {\displaystyle n} vertices on the moment curve, the set of d {\displaystyle d} -dimensional points with coordinates ( t , t 2 , t 3 , … ) {\displaystyle (t,t^{2},t^{3},\dots )} . The precise choice of which n {\displaystyle n} points on this curve are selected is irrelevant for the combinatorial structure of this polytope. The number of i {\displaystyle i} -dimensional faces of Δ ( n , d ) {\displaystyle \Delta (n,d)} is given by the formula

f i ( Δ ( n , d ) ) = ( n i + 1 ) for 0 ≤ i < ⌊ d 2 ⌋ {\displaystyle f_{i}(\Delta (n,d))={\binom {n}{i+1}}\quad {\textrm {for}}\quad 0\leq i<\left\lfloor {\frac {d}{2}}\right\rfloor }

and ( f 0 , … , f ⌊ d 2 ⌋ − 1 ) {\displaystyle (f_{0},\ldots ,f_{\left\lfloor {\frac {d}{2}}\right\rfloor -1})} completely determine ( f ⌊ d 2 ⌋ , … , f d − 1 ) {\displaystyle (f_{\left\lfloor {\frac {d}{2}}\right\rfloor },\ldots ,f_{d-1})} via the Dehn–Sommerville equations. The same formula for the number of faces holds more generally for any neighborly polytope.

Statement The upper bound theorem states that if Δ {\displaystyle \Delta } is a simplicial sphere of dimension d − 1 {\displaystyle d-1} with n {\displaystyle n} vertices, then

f i ( Δ ) ≤ f i ( Δ ( n , d ) ) for i = 0 , 1 , … , d − 1. {\displaystyle f_{i}(\Delta )\leq f_{i}(\Delta (n,d))\quad {\textrm {for}}\quad i=0,1,\ldots ,d-1.}

The difference between d − 1 {\displaystyle d-1} for the dimension of the simplicial sphere, and d {\displaystyle d} for the dimension of the cyclic polytope, comes from the fact that the surface of a d {\displaystyle d} -dimensional polytope (such as the cyclic polytope) is a ( d − 1 ) {\displaystyle (d-1)} -dimensional subdivision of a sphere. Therefore, the upper bound theorem implies that the number of faces of an arbitrary polytope can never be more than the number of faces of a cyclic or neighborly polytope with the same dimension and number of vertices. Asymptotically, this implies that there are at most O ( n ⌊ d / 2 ⌋ ) {\displaystyle \scriptstyle O(n^{\lfloor d/2\rfloor })} faces of all dimensions. The same bounds hold as well for convex polytopes that are not simplicial, as perturbing the vertices of such a polytope (and taking the convex hull of the perturbed vertices) can only increase the number of faces.

History The upper bound conjecture for simplicial polytopes was proposed by Motzkin in 1957 and proved by McMullen in 1970. A key ingredient in his proof was the following reformulation in terms of h-vectors:

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Upper bound theorem

Start with the simplest possible case. Write down what Upper bound theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Upper bound theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Upper bound theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Upper bound theorem

In research: Upper bound theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Upper bound theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Upper bound theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Polyhedral combinatorics, Theorems in combinatorics, so understanding it makes those chapters shorter.
In everyday life: Look for Upper bound theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Upper bound theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Upper bound theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Upper bound theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Upper bound theorem in simple terms?

In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics.

Why does Upper bound theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Upper bound theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Upper bound theorem.