Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Polyhedral combinatorics
Summary
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.
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. 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, the vector (f0, f1, ..., fd − 1) where fi is the number of i-dimensional features of the polytope. For instance, a cube has eight vertices, twelve edges, and six facets, so its ƒ-vector is (8,12,6).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.