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

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.

Related publications (32)

Related people (7)

Related lectures (6)

Ontological neighbourhood

Related concepts (16)

Related units (1)

Closest Vector Problem: Voronoi Cells

Explores the closest vector problem in lattices and the role of Voronoi cells in determining the closest vector.

Topological Polyhedron: Creating a Pavilion in TopSolid

Demonstrates creating a pavilion using a topological cube in TopSolid, emphasizing geometric accuracy and practical modeling techniques.

Closest Vector Problem: Voronoi Cells

Explores the Closest Vector Problem and Voronoi cells in lattice reduction algorithms.

Steinitz's theorem

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.

Linear programming relaxation

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form The relaxation of the original integer program instead uses a collection of linear constraints The resulting relaxation is a linear program, hence the name.

Birkhoff polytope

The Birkhoff polytope Bn (also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph ) is the convex polytope in RN (where N = n2) 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. The Birkhoff polytope has n! vertices, one for each permutation on n items.

Yuri Faenza, Manuel Francesco Aprile

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...

We consider the problem of trajectory planning in an environment comprised of a set of obstacles with uncertain locations. While previous approaches model the uncertainties with a prescribed Gaussian distribution, we consider the realistic case in which th ...

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...