---
title: "Basic Combinatorics of Polytopes and Polyhedra"
canonical: "https://docs.magma-maths.org/v2.30-1/Geometry/Polytopes/basic-combinatorics.html"
source: "https://docs.magma-maths.org/v2.30-1/Geometry/Polytopes/basic-combinatorics.md"
part: "Geometry"
chapter: "Convex Polytopes and Polyhedra"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Geometry", "source": "https://docs.magma-maths.org/v2.30-1/Geometry/index-geometry.md"}
  - {"title": "Convex Polytopes and Polyhedra", "source": "https://docs.magma-maths.org/v2.30-1/Geometry/Polytopes/index-polytopes.md"}
prev: {"title": "Polytopes, Cones, and Polyhedra", "source": "https://docs.magma-maths.org/v2.30-1/Geometry/Polytopes/polytopes-cones-polyhedra.md"}
next: {"title": "The Combinatorics of Polytopes", "source": "https://docs.magma-maths.org/v2.30-1/Geometry/Polytopes/combinatorics.md"}
intrinsics:
  - {"name": "Vertices", "signature": "Vertices(P): TorPol -> SeqEnum[TorLatElt]"}
  - {"name": "NumberOfVertices", "signature": "NumberOfVertices(P): TorPol -> RngIntElt"}
  - {"name": "Rays", "signature": "Rays(C): TorCon -> SeqEnum"}
  - {"name": "Ray", "signature": "Ray(C, i): TorCon, RngIntElt -> TorLatElt"}
  - {"name": "LinearSpanEquations", "signature": "LinearSpanEquations(C): TorCon -> SeqEnum"}
  - {"name": "LinearSpanEquations", "signature": "LinearSpanEquations(Q): [TorLatElt] -> SeqEnum"}
  - {"name": "LinearSpanGenerators", "signature": "LinearSpanGenerators(C): TorCon -> SeqEnum"}
  - {"name": "LinearSpanGenerators", "signature": "LinearSpanGenerators(Q): [TorLatElt] -> SeqEnum"}
  - {"name": "LinearSubspaceGenerators", "signature": "LinearSubspaceGenerators(C): TorCon -> SeqEnum"}
  - {"name": "Inequalities", "signature": "Inequalities(C): TorCon -> SeqEnum"}
  - {"name": "Inequalities", "signature": "Inequalities(P): TorPol -> SeqEnum, RngIntElt"}
  - {"name": "MinimalInequalities", "signature": "MinimalInequalities(C): TorCon -> SeqEnum"}
  - {"name": "MatrixOfInequalities", "signature": "MatrixOfInequalities(R, C): Rng, TorCon -> ModMatRngElt"}
  - {"name": "MatrixOfInequalities", "signature": "MatrixOfInequalities(C): TorCon -> ModMatRngElt"}
  - {"name": "NormalCone", "signature": "NormalCone(P, F): TorPol, TorPol -> TorCon"}
  - {"name": "NormalEdgeCones", "signature": "NormalEdgeCones(P): TorPol -> [TorCon]"}
  - {"name": "InnerNormal", "signature": "InnerNormal(C): TorCon -> TorLatElt"}
  - {"name": "OuterNormal", "signature": "OuterNormal(C): TorCon -> TorLatElt"}
  - {"name": "fVector", "signature": "fVector(C): TorCon -> SeqEnum[RngIntElt]"}
  - {"name": "fVector", "signature": "fVector(P): TorPol -> SeqEnum[RngIntElt]"}
  - {"name": "hVector", "signature": "hVector(C): TorCon -> SeqEnum[RngIntElt]"}
  - {"name": "hVector", "signature": "hVector(P): TorPol -> SeqEnum[RngIntElt]"}
  - {"name": "Facets", "signature": "Facets(C): TorCon -> SeqEnum"}
  - {"name": "Facets", "signature": "Facets(P): TorPol -> SeqEnum"}
  - {"name": "FacetIndices", "signature": "FacetIndices(P): TorPol -> SeqEnum"}
  - {"name": "NumberOfFacets", "signature": "NumberOfFacets(P): TorPol -> RngIntElt"}
  - {"name": "Faces", "signature": "Faces(C): TorCon -> SeqEnum"}
  - {"name": "Faces", "signature": "Faces(P): TorPol -> SeqEnum"}
  - {"name": "Faces", "signature": "Faces(C, i): TorCon, RngIntElt -> SeqEnum"}
  - {"name": "Faces", "signature": "Faces(P, i): TorPol, RngIntElt -> SeqEnum"}
  - {"name": "FaceIndices", "signature": "FaceIndices(P, i): TorPol, RngIntElt -> SeqEnum"}
  - {"name": "NumberOfFaces", "signature": "NumberOfFaces(P, i): TorPol, RngIntElt -> RngIntElt"}
  - {"name": "Edges", "signature": "Edges(P): TorPol -> SeqEnum"}
  - {"name": "EdgeIndices", "signature": "EdgeIndices(P): TorPol -> SeqEnum"}
  - {"name": "NumberOfEdges", "signature": "NumberOfEdges(P): TorPol -> RngIntElt"}
  - {"name": "Graph", "signature": "Graph(P): TorPol -> GrphUnd"}
  - {"name": "FaceSupportedBy", "signature": "FaceSupportedBy(C, H): TorCon, TorLatElt -> TorCon"}
  - {"name": "IsSupportingHyperplane", "signature": "IsSupportingHyperplane(v, h, P): TorLatElt, FldRatElt, TorPol -> BoolElt, RngIntElt"}
  - {"name": "SupportingCone", "signature": "SupportingCone(P, v): TorPol, TorLatElt -> TorCon"}
  - {"name": "IsFace", "signature": "IsFace(C, F): TorCon, TorCon -> BoolElt"}
  - {"name": "IsFace", "signature": "IsFace(P, F): TorPol, TorPol -> BoolElt"}
examples:
  - "ex-b4cdf2"
---

<a id="polytopes-basic-combinatorics"></a>
# Basic Combinatorics of Polytopes and Polyhedra

Cones, polytopes, and polyhedra have similar combinatorial features: they are composed of faces of various dimensions that meet in faces of lower dimensions. Some functions apply to all of these geometrical objects, some do not.

A face of a cone $C$ is the intersection of $C$ with an affine hyperplane whose defining equation is non-negative on $C$. A facet of a cone $C$ is a codimension 1 face of $C$. Definitions for polytopes and polyhedra are similar.

## Vertices and Inequalities

<a id="function-vertices-torpol"></a>
### `Vertices(P): TorPol -> SeqEnum[TorLatElt]`

A sequence containing the vertices of the polyhedron $P$.

<a id="function-numberofvertices-torpol"></a>
### `NumberOfVertices(P): TorPol -> RngIntElt`

The number of vertices of the polyhedron $P$.

<a id="function-rays-torcon"></a>
### `Rays(C): TorCon -> SeqEnum`

The sequence of generators of the rays of the cone $C$ (returned as primitive lattice points). If $C$ is strictly convex, this is the same as the minimal ${\bf R}$-generators.

<a id="function-ray-torcon-rngintelt"></a>
### `Ray(C, i): TorCon, RngIntElt -> TorLatElt`

The $i$th ray of the of the cone $C$ (in the order returned by `Rays(C)`).

<a id="function-linearspanequations-torcon"></a>
### `LinearSpanEquations(C): TorCon -> SeqEnum`

<a id="function-linearspanequations-torlatelt"></a>
### `LinearSpanEquations(Q): [TorLatElt] -> SeqEnum`

A sequence of equations defining the minimal linear subspace containing the cone $C$ (or the sequence of toric lattice points $Q$).

<a id="function-linearspangenerators-torcon"></a>
### `LinearSpanGenerators(C): TorCon -> SeqEnum`

<a id="function-linearspangenerators-torlatelt"></a>
### `LinearSpanGenerators(Q): [TorLatElt] -> SeqEnum`

A sequence of generators of the minimal linear subspace containing the cone $C$ (or the sequence of toric lattice points $Q$).

<a id="function-linearsubspacegenerators-torcon"></a>
### `LinearSubspaceGenerators(C): TorCon -> SeqEnum`

A basis of the maximal linear subspace contained in the cone $C$.

<a id="function-inequalities-torcon"></a>
### `Inequalities(C): TorCon -> SeqEnum`

<a id="function-inequalities-torpol"></a>
### `Inequalities(P): TorPol -> SeqEnum, RngIntElt`

<a id="function-minimalinequalities-torcon"></a>
### `MinimalInequalities(C): TorCon -> SeqEnum`

If the cone $C$ or polyhedron $P$ lies in a toric lattice $L$, then return a finite sequence of vectors in the dual lattice $\check{L}$ which define supporting hyperplanes of $C$ or $P$. The list is forced to be minimal for `MinimalInequalities`, but might not be otherwise. If the argument is a polyhedron, then an integer $k$ is returned as a second return value, so that the first $k$ inequalities correspond to the facets of $P$ while the remaining cut out the subspace containing $P$.

<a id="function-matrixofinequalities-rng-torcon"></a>
### `MatrixOfInequalities(R, C): Rng, TorCon -> ModMatRngElt`

<a id="function-matrixofinequalities-torcon"></a>
### `MatrixOfInequalities(C): TorCon -> ModMatRngElt`

The inequalities of $C$ arranged in a matrix, with each row representing an inequality.

<a id="example-ex-b4cdf2"></a>
### `Example: Inequalities Defining a Polytope (ex-b4cdf2)`

Build a polytope and recover the inequalities that define it: the second return value, $3$, says that all three inequalities define facets of $P$—we see an example below where this is not the case.

```magma
> P := Polytope([[1,0],[0,1],[-1,-1]]);
> Inequalities(P);
[
    <(2, -1), -1>,
    <(-1, -1), -1>,
    <(-1, 2), -1>
]
3
```

For each inequality use `HalfspaceToPolyhedron(m,h)` to define the corresponding halfspace, and then intersect them all to recover $P$—and finally recover the vertices we started with.

```magma
> PP := &meet  [HalfspaceToPolyhedron(H[1],H[2]) : H in Inequalities(P)];
> PP eq P;
true
> PP;
2-dimensional polytope PP with 3 vertices:
    ( 0,  1),
    (-1, -1),
    ( 1,  0)
```

It can happen that a polytope does not span the ambient toric lattice in which it lies and that some of the inequalities are used to cut out the affine subspace that it does span.

```magma
> Q := Polytope([[1,0,2],[0,1,2],[-1,0,2],[0,-1,2]]);
> Inequalities(Q);
[
    <(1, -1, 0), -1>,
    <(-1, -1, 0), -1>,
    <(-1, 1, 0), -1>,
    <(1, 1, 0), -1>,
    <(0, 0, 1), 2>,
    <(0, 0, -1), -2>
]
4
```

In this case the final two inequalities are opposites of one another and cut out the affine hyperplane $z=2$. The second return value $4$ indicates that the first $4$ inequalities are cutting out facets of the polytope while the remaining inequalities are cutting out the affine hyperplane.

<a id="function-normalcone-torpol-torpol"></a>
### `NormalCone(P, F): TorPol, TorPol -> TorCon`

The (outer) normal cone of the face $F$ of the polyhedron $P$.

<a id="function-normaledgecones-torpol"></a>
### `NormalEdgeCones(P): TorPol -> [TorCon]`

The (outer) normal cones of the edges of the polyhedron $P$. The cones are presented in the same order as the edges of $P$; i.e. the $i$-th cone in the resulting sequence is the normal cone to the $i$-th edge returned by `Edges(P)` or `EdgeIndices(P)`.

<a id="function-innernormal-torcon"></a>
### `InnerNormal(C): TorCon -> TorLatElt`

<a id="function-outernormal-torcon"></a>
### `OuterNormal(C): TorCon -> TorLatElt`

For a Gorenstein cone $C$, i.e. a cone such that the primitive generators $\rho_i$ of the rays of $C$ lie in a common hyperplane, gives an element $u$ in the dual lattice such that $u(\rho_i) = -1$ (inner normal) or $u(\rho_i) = 1$ (outer normal).

## Facets and Faces

<a id="function-fvector-torcon"></a>
### `fVector(C): TorCon -> SeqEnum[RngIntElt]`

<a id="function-fvector-torpol"></a>
### `fVector(P): TorPol -> SeqEnum[RngIntElt]`

The $f$-vector of the polyhedron $P$ or cone $C$.

<a id="function-hvector-torcon"></a>
### `hVector(C): TorCon -> SeqEnum[RngIntElt]`

<a id="function-hvector-torpol"></a>
### `hVector(P): TorPol -> SeqEnum[RngIntElt]`

The $h$-vector of the polyhedron $P$ or cone $C$.

<a id="function-facets-torcon"></a>
### `Facets(C): TorCon -> SeqEnum`

<a id="function-facets-torpol"></a>
### `Facets(P): TorPol -> SeqEnum`

A sequence containing all facets of the toric cone $C$ or polyhedron $P$.

<a id="function-facetindices-torpol"></a>
### `FacetIndices(P): TorPol -> SeqEnum`

A sequence of sets describing the facets of the polytope $P$. The $j$th set gives the indices of the vertices of $P$ which define the $j$th facet of $P$.

<a id="function-numberoffacets-torpol"></a>
### `NumberOfFacets(P): TorPol -> RngIntElt`

The number of facets of the polyhedron $P$.

<a id="function-faces-torcon"></a>
### `Faces(C): TorCon -> SeqEnum`

<a id="function-faces-torpol"></a>
### `Faces(P): TorPol -> SeqEnum`

<a id="function-faces-torcon-rngintelt"></a>
### `Faces(C, i): TorCon, RngIntElt -> SeqEnum`

<a id="function-faces-torpol-rngintelt"></a>
### `Faces(P, i): TorPol, RngIntElt -> SeqEnum`

A sequence containing all face cones of the toric cone $C$ or polyhedron $P$, or only those of dimension $i$ if an integer $i$ is also specified.

<a id="function-faceindices-torpol-rngintelt"></a>
### `FaceIndices(P, i): TorPol, RngIntElt -> SeqEnum`

A sequence of sets describing the $i$-dimensional faces of the polyhedron $P$. The $j$th set gives the indices of the vertices of $P$ which define the $j$th $i$-dimensional face.

<a id="function-numberoffaces-torpol-rngintelt"></a>
### `NumberOfFaces(P, i): TorPol, RngIntElt -> RngIntElt`

The number of $i$-dimensional faces of the polyhedron $P$.

<a id="function-edges-torpol"></a>
### `Edges(P): TorPol -> SeqEnum`

A sequence containing all the edges of the polyhedron $P$.

<a id="function-edgeindices-torpol"></a>
### `EdgeIndices(P): TorPol -> SeqEnum`

A sequence of sets describing the edges of the polyhedron $P$. The $j$th set gives the indices of the vertices of $P$ which define the $j$th edge of $P$.

<a id="function-numberofedges-torpol"></a>
### `NumberOfEdges(P): TorPol -> RngIntElt`

The number of edges of the polyhedron $P$.

<a id="function-graph-torpol"></a>
### `Graph(P): TorPol -> GrphUnd`

The graph of the face lattice of the polyhedron $P$. The vertices of the graph are labeled by the dimension of the corresponding face.

<a id="function-facesupportedby-torcon-torlatelt"></a>
### `FaceSupportedBy(C, H): TorCon, TorLatElt -> TorCon`

The face of the toric cone $C$ supported by the toric lattice element $H$ in the dual lattice to the one containing $C$ (so $H$ is a linear form on the ambient lattice of $C$).

<a id="function-issupportinghyperplane-torlatelt-fldratelt-torpol"></a>
### `IsSupportingHyperplane(v, h, P): TorLatElt, FldRatElt, TorPol -> BoolElt, RngIntElt`

Return `true` if and only if the hyperplane defined by $v\cdot u = h$ is a supporting hyperplane of the polyhedron $P$, where $v$ is a lattice point of the dual ambient lattice of $P$ and $h$ is a rational number. If so, also gives the sign $\tau$ such the hyperplane is a support of $P$ (i.e. $\tau$ in $\{-1,0,+1\}$ such that Sign$(v\cdot u - h)$ is either $0$ or $\tau$ for all u in $P$). If $P$ is contained within the hyperplane, then $\tau$ will be $0$.

<a id="function-supportingcone-torpol-torlatelt"></a>
### `SupportingCone(P, v): TorPol, TorLatElt -> TorCon`

The cone $C$ such that $C + v$ is a supporting cone of the polyhedron $P$, where $v$ is a vertex of $P$.

<a id="function-isface-torcon-torcon"></a>
### `IsFace(C, F): TorCon, TorCon -> BoolElt`

<a id="function-isface-torpol-torpol"></a>
### `IsFace(P, F): TorPol, TorPol -> BoolElt`

Return `true` if and only if $F$ is a face of the cone $C$ or polyhedron $P$.
