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

- Faces and face-counting vectors
- Equalities and inequalities
- Graph-theoretic properties
- Computational properties
- Facets of 0-1 polytopes
- See also
- Notes
- References
- External links

Research in polyhedral combinatorics falls into two distinct areas. Mathematicians in this area study the combinatorics of polytopes; for instance, they seek inequalities that describe the relations between the numbers of vertices, edges, and faces of higher dimensions in arbitrary polytopes or in certain important subclasses of polytopes, and study other combinatorial properties of polytopes such as their connectivity and diameter (number of steps needed to reach any vertex from any other vertex). Additionally, many computer scientists use the phrase “polyhedral combinatorics” to describe research into precise descriptions of the faces of certain specific polytopes (especially 0-1 polytopes, whose vertices are subsets of a hypercube) arising from integer programming problems.

A *face* of a convex polytope *P* may be defined as the intersection of *P* and a closed halfspace *H* such that the boundary of *H* contains no interior point of *P*. The dimension of a face is the dimension of this hull. The 0-dimensional faces are the vertices themselves, and the 1-dimensional faces (called *edges*) are line segments connecting pairs of vertices. Note that this definition also includes as faces the empty set and the whole polytope *P*. If *P* itself has dimension *d*, the faces of *P* with dimension *d* − 1 are called *facets* of *P* and the faces with dimension *d* − 2 are called * ridges *.^{ [1] } The faces of *P* may be partially ordered by inclusion, forming a face lattice that has as its top element *P* itself and as its bottom element the empty set.

A key tool in polyhedral combinatorics is the *ƒ-vector* of a polytope,^{ [2] } the vector (*f*_{0}, *f*_{1}, ..., *f*_{d − 1}) where *f _{i}* is the number of

The *extended ƒ-vector* is formed by concatenating the number one at each end of the ƒ-vector, counting the number of objects at all levels of the face lattice; on the left side of the vector, *f*_{−1} = 1 counts the empty set as a face, while on the right side, *f _{d}* = 1 counts

For simplicial polytopes (polytopes in which every facet is a simplex), it is often convenient to transform these vectors, producing a different vector called the *h*-vector. If we interpret the terms of the ƒ-vector (omitting the final 1) as coefficients of a polynomial ƒ(*x*) = Σ*f _{i}x*

The most important relation among the coefficients of the ƒ-vector of a polytope is Euler's formula Σ(−1)^{i}*f _{i}* = 0, where the terms of the sum range over the coefficients of the extended ƒ-vector. In three dimensions, moving the two 1's at the left and right ends of the extended ƒ-vector (1,

In higher dimensions, other relations among the numbers of faces of a polytope become important as well, including the Dehn–Sommerville equations which, expressed in terms of *h*-vectors of simplicial polytopes, take the simple form *h*_{k} = *h*_{d − k} for all *k*. The instance of these equations with *k* = 0 is equivalent to Euler's formula but for *d*> 3 the other instances of these equations are linearly independent of each other and constrain the *h*-vectors (and therefore also the ƒ-vectors) in additional ways.^{ [4] }

Another important inequality on polytope face counts is given by the upper bound theorem, first proven by McMullen (1970), which states that a *d*-dimensional polytope with *n* vertices can have at most as many faces of any other dimension as a neighborly polytope with the same number of vertices:

where the asterisk means that the final term of the sum should be halved when *d* is even.^{ [6] } Asymptotically, this implies that there are at most faces of all dimensions.

Even in four dimensions, the set of possible ƒ-vectors of convex polytopes does not form a convex subset of the four-dimensional integer lattice, and much remains unknown about the possible values of these vectors.^{ [7] }

Along with investigating the numbers of faces of polytopes, researchers have studied other combinatorial properties of them, such as descriptions of the graphs obtained from the vertices and edges of polytopes (their 1-skeleta).

Balinski's theorem states that the graph obtained in this way from any *d*-dimensional convex polytope is *d*-vertex-connected.^{ [8] } In the case of three-dimensional polyhedra, this property and planarity may be used to exactly characterize the graphs of polyhedra: Steinitz's theorem states that *G* is the skeleton of a three-dimensional polyhedron if and only if *G* is a 3-vertex-connected planar graph.^{ [9] }

A theorem of Blind & Mani-Levitska (1987) (previously conjectured by Micha Perles) states that one can reconstruct the face structure of a simple polytope from its graph. That is, if a given undirected graph is the skeleton of a simple polytope, there is only one polytope (up to combinatorial equivalence) for which this is true. This is in sharp contrast with (non-simple) neighborly polytopes whose graph is a complete graph; there can be many different neighborly polytopes for the same graph. Another proof of this theorem based on unique sink orientations was given by Kalai (1988), and Friedman (2009) showed how to use this theorem to derive a polynomial time algorithm for reconstructing the face lattices of simple polytopes from their graphs. However, testing whether a given graph or lattice can be realized as the face lattice of a simple polytope is equivalent (by polarity) to realization of simplicial polytopes, which was shown to be complete for the existential theory of the reals by Adiprasito & Padrol (2014) .

In the context of the simplex method for linear programming, it is important to understand the diameter of a polytope, the minimum number of edges needed to reach any vertex by a path from any other vertex. The system of linear inequalities of a linear program define facets of a polytope representing all feasible solutions to the program, and the simplex method finds the optimal solution by following a path in this polytope. Thus, the diameter provides a lower bound on the number of steps this method requires. The Hirsch conjecture, now disproved, suggested a strong (linear) bound on how large the diameter of a polytope with fixed dimension and number of facets could be.^{ [10] } Weaker (quasi-polynomial in and ) upper bounds on their diameter are known,^{ [11] } as well as proofs of the Hirsch conjecture for special classes of polytopes.^{ [12] }

Deciding whether the number of vertices of a given polytope is bounded by some natural number *k* is a computationally difficult problem and complete for the complexity class PP.^{ [13] }

It is important in the context of cutting-plane methods for integer programming to be able to describe accurately the facets of polytopes that have vertices corresponding to the solutions of combinatorial optimization problems. Often, these problems have solutions that can be described by binary vectors, and the corresponding polytopes have vertex coordinates that are all zero or one.

As an example, consider the Birkhoff polytope, the set of *n* × *n* matrices that can be formed from convex combinations of permutation matrices. Equivalently, its vertices can be thought of as describing all perfect matchings in a complete bipartite graph, and a linear optimization problem on this polytope can be interpreted as a bipartite minimum weight perfect matching problem. The *Birkhoff–von Neumann theorem* states that this polytope can be described by two types of linear inequality or equality. First, for each matrix cell, there is a constraint that this cell has a non-negative value. And second, for each row or column of the matrix, there is a constraint that the sum of the cells in that row or column equal one. The row and column constraints define a linear subspace of dimension *n*^{2} − 2*n* + 1 in which the Birkhoff polytope lies, and the non-negativity constraints define facets of the Birkhoff polytope within that subspace.

However, the Birkhoff polytope is unusual in that a complete description of its facets is available. For many other 0-1 polytopes, there are exponentially many or superexponentially many facets, and only partial descriptions of their facets are available.^{ [14] }

- ↑ Ziegler (1995), p. 51.
- ↑ Ziegler (1995), pp. 245–246.
- ↑ Ziegler (1995), p. 272.
- 1 2 Ziegler (1995), pp. 246–253.
- ↑ Steinitz (1906).
- ↑ Ziegler (1995), pp. 254–258.
- ↑ Höppner & Ziegler (2000).
- ↑ Balinski (1961); Ziegler (1995), pp. 95–96.
- ↑ Ziegler (1995), pp. 103–126.
- ↑ Santos (2012).
- ↑ Kalai & Kleitman (1992).
- ↑ Naddef (1989).
- ↑ Haase & Kiefer (2016), Thm. 5.
- ↑ Ziegler (2000).

In geometry, a **polyhedron** is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.

**Discrete geometry** and **combinatorial geometry** are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

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.

The **Birkhoff polytope***B*_{n} is the convex polytope in **R**^{N} whose points are the doubly stochastic matrices, i.e., the *n* × *n* matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1. It is named after Garrett Birkhoff.

In geometry, a d-dimensional **simple polytope** is a d-dimensional polytope each of whose vertices are adjacent to exactly d edges. The vertex figure of a simple d-polytope is a (*d* – 1)-simplex.

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 geometry, an **edge** is a particular type of line segment joining two vertices in a polygon, polyhedron, or higher-dimensional polytope. In a polygon, an edge is a line segment on the boundary, and is often called a **polygon side**. In a polyhedron or more generally a polytope, an edge is a line segment where two faces meet. A segment joining two vertices while passing through the interior or exterior is not an edge but instead is called a diagonal.

In polyhedral combinatorics, a branch of mathematics, **Steinitz's theorem** is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

In geometry and combinatorics, a **simplicial**** d-sphere** is a simplicial complex homeomorphic to the

In polyhedral combinatorics, a branch of mathematics, **Balinski's theorem** is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected graph from the vertices and edges of a convex *d*-dimensional convex polyhedron or polytope, then the resulting graph is at least *d*-vertex-connected: the removal of any *d* − 1 vertices leaves a connected subgraph. For instance, for a three-dimensional polyhedron, even if two of its vertices are removed, for any pair of vertices there will still exist a path of vertices and edges connecting the pair.

**Polymake** is software for the algorithmic treatment of convex polyhedra.

In geometry and polyhedral combinatorics, an **integral polytope** is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called **lattice polytopes** or **Z-polytopes**. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

In geometry and polyhedral combinatorics, the **Kleetope** of a polyhedron or higher-dimensional convex polytope *P* is another polyhedron or polytope *P ^{K}* formed by replacing each facet of

In geometry, a **Hanner polytope** is a convex polytope constructed recursively by Cartesian product and polar dual operations. Hanner polytopes are named after Olof Hanner, who introduced them in 1956.

In geometry, **Kalai's 3 ^{d} conjecture** is a conjecture on the polyhedral combinatorics of centrally symmetric polytopes, made by Gil Kalai in 1989. It states that every

In graph drawing and geometric graph theory, a **Tutte embedding** or **barycentric embedding** of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. **Tutte's spring theorem**, proven by W. T. Tutte (1963), states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

In polyhedral combinatorics, a **stacked polytope** is a polytope formed from a simplex by repeatedly gluing another simplex onto one of its facets.

In mathematics, the **order polytope** of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the upper sets of the partial order, and its dimension is the number of elements in the partial order. The order polytope is a distributive polytope, meaning that coordinatewise minima and maxima of pairs of its points remain within the polytope.

In polyhedral combinatorics, the **Gale transform** turns the vertices of any convex polytopes into a set of vectors or points in a space of a different dimension, the **Gale diagram** of the polytope. It can be used to describe high-dimensional polytopes with few vertices, by transforming them into sets of points in a space of a much lower dimension. The process can also be reversed, to construct polytopes with desired properties from their Gale diagrams. The Gale transform and Gale diagram are named after David Gale, who introduced these methods in a 1956 paper on neighborly polytopes.

* Convex Polytopes* is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics.

- Adiprasito, Karim A.; Padrol, Arnau (2017), "The universality theorem for neighborly polytopes",
*Combinatorica*,**37**: 129–136, arXiv: 1402.7207 , Bibcode:2014arXiv1402.7207A, doi: 10.1007/s00493-016-3253-9 . - Balinski, Michel L. (1961), "On the graph structure of convex polyhedra in n-space",
*Pacific Journal of Mathematics*,**11**: 431–434, doi: 10.2140/pjm.1961.11.431 . - Blind, Roswitha; Mani-Levitska, Peter (1987), "Puzzles and polytope isomorphisms",
*Aequationes Mathematicae*,**34**(2–3): 287–297, doi: 10.1007/BF01830678 , MR 0921106 . - Cook, William; Seymour, Paul D. (1989),
*Polyhedral Combinatorics*, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, ISBN 978-0-8218-6591-0 . - Friedman, Eric J. (2009), "Finding a simple polytope from its graph in polynomial time",
*Discrete & Computational Geometry*,**41**(2): 249–256, doi: 10.1007/s00454-008-9121-7 , MR 2471873 . - Haase, Christoph; Kiefer, Stefan (2016), "The complexity of the Kth largest subset problem and related problems",
*Information Processing Letters*,**116**(2): 111–115, arXiv: 1501.06729 , doi:10.1016/j.ipl.2015.09.015 - Höppner, Andrea; Ziegler, Günter M. (2000), "A census of flag-vectors of 4-polytopes", in Kalai, Gil; Ziegler, Günter M. (eds.),
*Polytopes — Combinatorics and Computation*, DMV Seminar, vol. 29, pp. 105–110, doi: 10.1007/978-3-0348-8438-9_4 . - Kalai, Gil (1988), "A simple way to tell a simple polytope from its graph",
*Journal of Combinatorial Theory*, Series A,**49**(2): 381–383, doi: 10.1016/0097-3165(88)90064-7 , MR 0964396 . - Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra",
*Bulletin of the American Mathematical Society*,**26**(2): 315–316, arXiv: math/9204233 , doi: 10.1090/S0273-0979-1992-00285-9 , MR 1130448 . - Kalai, Gil; Ziegler, Günter M., eds. (2000),
*Polytopes — Combinatorics and Computation*, DMV Seminar, vol. 29, Birkhäuser, doi: 10.1007/978-3-0348-8438-9 , ISBN 978-3-7643-6351-2 . - McMullen, Peter (1970), "The maximum numbers of faces of a convex polytope",
*Mathematika*,**17**: 179–184, doi:10.1112/S0025579300002850 . - Naddef, Denis (1989), "The Hirsch conjecture is true for (0,1)-polytopes",
*Mathematical Programming*,**45**(1): 109–110, doi: 10.1007/BF01589099 , MR 1017214 . - Santos, Francisco (2012), "A counterexample to the Hirsch conjecture",
*Annals of Mathematics*, Princeton University and Institute for Advanced Study,**176**(1): 383–412, arXiv: 1006.2814 , doi: 10.4007/annals.2012.176.1.7 , MR 2925387 - Schrijver, Alexander (1987),
*Polyhedral Combinatorics*, Centrum voor Wiskunde en Informatica. - Steinitz, Ernst (1906), "Über die Eulerschen Polyederrelationen",
*Archiv für Mathematik und Physik*,**11**: 86–88. - Ziegler, Günter M. (1995),
*Lectures on Polytopes*, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, doi: 10.1007/978-1-4613-8431-1 , ISBN 0-387-94365-X . - Ziegler, Günter M. (2000), "Lectures on 0-1 polytopes", in Kalai, Gil; Ziegler, Günter M. (eds.),
*Polytopes — Combinatorics and Computation*, DMV Seminar, vol. 29, pp. 1–41, doi: 10.1007/978-3-0348-8438-9_1 .

- Kalai, Gil (2008),
*Five Open Problems Regarding Convex Polytopes*.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.