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, [1] and strengthened from polytopes to subdivisions of a sphere in 1975 by Richard P. Stanley.
The cyclic polytope may be defined as the convex hull of vertices on the moment curve, the set of -dimensional points with coordinates . The precise choice of which points on this curve are selected is irrelevant for the combinatorial structure of this polytope. The number of -dimensional faces of is given by the formula
and completely determine via the Dehn–Sommerville equations. The same formula for the number of faces holds more generally for any neighborly polytope.
The upper bound theorem states that if is a simplicial sphere of dimension with vertices, then
The difference between for the dimension of the simplicial sphere, and for the dimension of the cyclic polytope, comes from the fact that the surface of a -dimensional polytope (such as the cyclic polytope) is a -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 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.
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:
Victor Klee suggested that the same statement should hold for all simplicial spheres and this was indeed established in 1975 by Stanley [2] using the notion of a Stanley–Reisner ring and homological methods. For a nice historical account of this theorem see Stanley's article "How the upper bound conjecture was proved". [3]
In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,
In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their n-dimensional counterparts. Simplicial complexes should not be confused with the more abstract notion of a simplicial set appearing in modern simplicial homotopy theory. The purely combinatorial counterpart to a simplicial complex is an abstract simplicial complex. To distinguish a simplicial complex from an abstract simplicial complex, the former is often called a geometric simplicial complex.
In mathematics, the barycentric subdivision is a standard way to subdivide a given simplex into smaller ones. Its extension on simplicial complexes is a canonical method to refine them. Therefore, the barycentric subdivision is an important tool in algebraic topology.
In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.
In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.
In mathematics, triangulation describes the replacement of topological spaces by piecewise linear spaces, i.e. the choice of a homeomorphism in a suitable simplicial complex. Spaces being homeomorphic to a simplicial complex are called triangulable. Triangulation has various uses in different branches of mathematics, for instance in algebraic topology, in complex analysis or in modeling.
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.
In information theory, information dimension is an information measure for random vectors in Euclidean space, based on the normalized entropy of finely quantized versions of the random vectors. This concept was first introduced by Alfréd Rényi in 1959.
In number theory, the divisor summatory function is a function that is a sum over the divisor function. It frequently occurs in the study of the asymptotic behaviour of the Riemann zeta function. The various studies of the behaviour of the divisor function are sometimes called divisor problems.
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general.
In algebraic combinatorics, the h-vector of a simplicial polytope is a fundamental invariant of the polytope which encodes the number of faces of different dimensions and allows one to express the Dehn–Sommerville equations in a particularly simple form. A characterization of the set of h-vectors of simplicial polytopes was conjectured by Peter McMullen and proved by Lou Billera and Carl W. Lee and Richard Stanley (g-theorem). The definition of h-vector applies to arbitrary abstract simplicial complexes. The g-conjecture stated that for simplicial spheres, all possible h-vectors occur already among the h-vectors of the boundaries of convex simplicial polytopes. It was proven in December 2018 by Karim Adiprasito.
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
In geometry and combinatorics, a simpliciald-sphere is a simplicial complex homeomorphic to the d-dimensional sphere. Some simplicial spheres arise as the boundaries of convex polytopes, however, in higher dimensions most simplicial spheres cannot be obtained in this way.
In mathematics, a Stanley–Reisner ring, or face ring, is a quotient of a polynomial algebra over a field by a square-free monomial ideal. Such ideals are described more geometrically in terms of finite simplicial complexes. The Stanley–Reisner ring construction is a basic tool within algebraic combinatorics and combinatorial commutative algebra. Its properties were investigated by Richard Stanley, Melvin Hochster, and Gerald Reisner in the early 1970s.
In geometry and polyhedral combinatorics, a k-neighborly polytope is a convex polytope in which every set of k or fewer vertices forms a face. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an edge, forming a complete graph. 2-neighborly polytopes with more than four vertices may exist only in spaces of four or more dimensions, and in general a k-neighborly polytope requires a dimension of 2k or more. A d-simplex is d-neighborly. A polytope is said to be neighborly, without specifying k, if it is k-neighborly for k = ⌊d⁄2⌋. If we exclude simplices, this is the maximum possible k: in fact, every polytope that is k-neighborly for some k ≥ 1 + ⌊d⁄2⌋ is a simplex.
In mathematics, a cyclic polytope, denoted C(n,d), is a convex polytope formed as a convex hull of n distinct points on a rational normal curve in Rd, where n is greater than d. These polytopes were studied by Constantin Carathéodory, David Gale, Theodore Motzkin, Victor Klee, and others. They play an important role in polyhedral combinatorics: according to the upper bound theorem, proved by Peter McMullen and Richard Stanley, the boundary Δ(n,d) of the cyclic polytope C(n,d) maximizes the number fi of i-dimensional faces among all simplicial spheres of dimension d − 1 with n vertices.
In geometry, Kalai's 3d conjecture is a conjecture on the polyhedral combinatorics of centrally symmetric polytopes, made by Gil Kalai in 1989. It states that every d-dimensional centrally symmetric polytope has at least 3d nonempty faces.
Peter McMullen is a British mathematician, a professor emeritus of mathematics at University College London.
The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.
A chessboard complex is a particular kind of abstract simplicial complex, which has various applications in topological graph theory and algebraic topology. Informally, the (m, n)-chessboard complex contains all sets of positions on an m-by-n chessboard, where rooks can be placed without attacking each other. Equivalently, it is the matching complex of the (m, n)-complete bipartite graph, or the independence complex of the m-by-n rook's graph.
Finally, in 1970 McMullen gave a complete proof of the upper-bound conjecture – since then it has been known as the upper bound theorem. McMullen's proof is amazingly simple and elegant, combining two key tools: shellability and h-vectors.
