Combinatorial polyhedron#
This module gathers algorithms for polyhedra that only depend on the
vertex-facet incidences and that are called combinatorial polyhedron.
The main class is CombinatorialPolyhedron
. Most importantly,
this class allows to iterate quickly through the faces (possibly
of given dimension) via the FaceIterator
object. The CombinatorialPolyhedron
uses this iterator to quickly generate the f-vector, the edges,
the ridges and the face lattice.
Terminology used in this module:
Vrep –
[vertices, rays, lines]
of the polyhedron.Hrep – inequalities and equations of the polyhedron.
Facets – facets of the polyhedron.
Vrepresentation – represents a face by the list of Vrep it contains.
Hrepresentation – represents a face by a list of Hrep it is contained in.
bit representation – represents incidences as bitset, where each bit represents one incidence. There might be trailing zeros, to fit alignment requirements. In most instances, faces are represented by the bit representation, where each bit corresponds to a Vrep or facet. Thus a bit representation can either be a Vrep or facet representation depending on context.
EXAMPLES:
Construction:
sage: P = polytopes.hypercube(4)
sage: C = CombinatorialPolyhedron(P); C
A 4-dimensional combinatorial polyhedron with 8 facets
Obtaining edges and ridges:
sage: C.edges()[:2]
((A vertex at (1, -1, -1, -1), A vertex at (-1, -1, -1, -1)),
(A vertex at (-1, -1, -1, 1), A vertex at (-1, -1, -1, -1)))
sage: C.edges(names=False)[:2]
((6, 15), (14, 15))
sage: C.ridges()[:2]
((An inequality (0, 0, 1, 0) x + 1 >= 0,
An inequality (0, 1, 0, 0) x + 1 >= 0),
(An inequality (0, 0, 0, 1) x + 1 >= 0,
An inequality (0, 1, 0, 0) x + 1 >= 0))
sage: C.ridges(names=False)[:2]
((6, 7), (5, 7))
Vertex-graph and facet-graph:
sage: C.vertex_graph() # needs sage.graphs
Graph on 16 vertices
sage: C.facet_graph() # needs sage.graphs
Graph on 8 vertices
Face lattice:
sage: C.face_lattice() # needs sage.combinat
Finite lattice containing 82 elements
Face iterator:
sage: C.face_generator()
Iterator over the proper faces of a 4-dimensional combinatorial polyhedron
sage: C.face_generator(2)
Iterator over the 2-faces of a 4-dimensional combinatorial polyhedron
AUTHOR:
Jonathan Kliem (2019-04)
- class sage.geometry.polyhedron.combinatorial_polyhedron.base.CombinatorialPolyhedron#
Bases:
SageObject
The class of the Combinatorial Type of a Polyhedron, a Polytope.
INPUT:
data
– an instance ofPolyhedron_base
or a
LatticePolytopeClass
or an
incidence_matrix
as inincidence_matrix()
In this case you should also specify theVrep
andfacets
argumentsor list of facets, each facet given as a list of
[vertices, rays, lines]
if the polyhedron is unbounded, then rays and lines and the extra argumentnr_lines
are required if the polyhedron contains no lines, the rays can be thought of as the vertices of the facets deleted from a bounded polyhedron seePolyhedron_base
on how to use rays and linesor an integer, representing the dimension of a polyhedron equal to its affine hull
or a tuple consisting of facets and vertices as two
ListOfFaces
.
Vrep
– (optional) whendata
is an incidence matrix, it should be the list of[vertices, rays, lines]
, if the rows in the incidence_matrix should correspond to namesfacets
– (optional) whendata
is an incidence matrix or a list of facets, it should be a list of facets that would be used instead of indices (of the columns of the incidence matrix).unbounded
– value will be overwritten ifdata
is a polyhedron; ifunbounded
anddata
is incidence matrix or a list of facets, need to specifyfar_face
far_face
– (semi-optional); if the polyhedron is unbounded this needs to be set to the list of indices of the rays and line unlessdata
is an instance ofPolyhedron_base
.
EXAMPLES:
We illustrate all possible input: a polyhedron:
sage: P = polytopes.cube() sage: CombinatorialPolyhedron(P) A 3-dimensional combinatorial polyhedron with 6 facets
a lattice polytope:
sage: points = [(1,0,0), (0,1,0), (0,0,1), ....: (-1,0,0), (0,-1,0), (0,0,-1)] sage: L = LatticePolytope(points) sage: CombinatorialPolyhedron(L) A 3-dimensional combinatorial polyhedron with 8 facets
a cone:
sage: M = Cone([(1,0), (0,1)]) sage: CombinatorialPolyhedron(M) A 2-dimensional combinatorial polyhedron with 2 facets
an incidence matrix:
sage: P = Polyhedron(rays=[[0,1]]) sage: data = P.incidence_matrix() sage: far_face = [i for i in range(2) if not P.Vrepresentation()[i].is_vertex()] sage: CombinatorialPolyhedron(data, unbounded=True, far_face=far_face) A 1-dimensional combinatorial polyhedron with 1 facet sage: C = CombinatorialPolyhedron(data, Vrep=['myvertex'], ....: facets=['myfacet'], unbounded=True, far_face=far_face) sage: C.Vrepresentation() ('myvertex',) sage: C.Hrepresentation() ('myfacet',)
a list of facets:
sage: CombinatorialPolyhedron(((1,2,3),(1,2,4),(1,3,4),(2,3,4))) A 3-dimensional combinatorial polyhedron with 4 facets sage: facetnames = ['facet0', 'facet1', 'facet2', 'myfacet3'] sage: facetinc = ((1,2,3),(1,2,4),(1,3,4),(2,3,4)) sage: C = CombinatorialPolyhedron(facetinc, facets=facetnames) sage: C.Vrepresentation() (1, 2, 3, 4) sage: C.Hrepresentation() ('facet0', 'facet1', 'facet2', 'myfacet3')
an integer:
sage: CombinatorialPolyhedron(-1).f_vector() (1) sage: CombinatorialPolyhedron(0).f_vector() (1, 1) sage: CombinatorialPolyhedron(5).f_vector() (1, 0, 0, 0, 0, 0, 1)
tuple of
ListOfFaces
:sage: from sage.geometry.polyhedron.combinatorial_polyhedron.conversions \ ....: import facets_tuple_to_bit_rep_of_facets, \ ....: facets_tuple_to_bit_rep_of_Vrep sage: bi_pyr = ((0,1,4), (1,2,4), (2,3,4), (3,0,4), ....: (0,1,5), (1,2,5), (2,3,5), (3,0,5)) sage: facets = facets_tuple_to_bit_rep_of_facets(bi_pyr, 6) sage: Vrep = facets_tuple_to_bit_rep_of_Vrep(bi_pyr, 6) sage: C = CombinatorialPolyhedron((facets, Vrep)); C A 3-dimensional combinatorial polyhedron with 8 facets sage: C.f_vector() (1, 6, 12, 8, 1)
Specifying that a polyhedron is unbounded is important. The following with a polyhedron works fine:
sage: P = Polyhedron(ieqs=[[1,-1,0],[1,1,0]]) sage: C = CombinatorialPolyhedron(P) # this works fine sage: C A 2-dimensional combinatorial polyhedron with 2 facets
The following is incorrect, as
unbounded
is implicitly set toFalse
:sage: data = P.incidence_matrix() sage: vert = P.Vrepresentation() sage: C = CombinatorialPolyhedron(data, Vrep=vert) sage: C A 2-dimensional combinatorial polyhedron with 2 facets sage: C.f_vector() Traceback (most recent call last): ... ValueError: not all vertices are intersections of facets sage: C.vertices() (A line in the direction (0, 1), A vertex at (1, 0), A vertex at (-1, 0))
The correct usage is:
sage: far_face = [i for i in range(3) if not P.Vrepresentation()[i].is_vertex()] sage: C = CombinatorialPolyhedron(data, Vrep=vert, unbounded=True, far_face=far_face) sage: C A 2-dimensional combinatorial polyhedron with 2 facets sage: C.f_vector() (1, 0, 2, 1) sage: C.vertices() ()
- Hrepresentation()#
Return a list of names of facets and possibly some equations.
EXAMPLES:
sage: P = polytopes.permutahedron(3) sage: C = CombinatorialPolyhedron(P) sage: C.Hrepresentation() (An inequality (1, 1, 0) x - 3 >= 0, An inequality (-1, -1, 0) x + 5 >= 0, An inequality (0, 1, 0) x - 1 >= 0, An inequality (-1, 0, 0) x + 3 >= 0, An inequality (1, 0, 0) x - 1 >= 0, An inequality (0, -1, 0) x + 3 >= 0, An equation (1, 1, 1) x - 6 == 0) sage: points = [(1,0,0), (0,1,0), (0,0,1), ....: (-1,0,0), (0,-1,0), (0,0,-1)] sage: L = LatticePolytope(points) sage: C = CombinatorialPolyhedron(L) sage: C.Hrepresentation() (N(1, -1, -1), N(1, 1, -1), N(1, 1, 1), N(1, -1, 1), N(-1, -1, 1), N(-1, -1, -1), N(-1, 1, -1), N(-1, 1, 1)) sage: M = Cone([(1,0), (0,1)]) sage: CombinatorialPolyhedron(M).Hrepresentation() (M(0, 1), M(1, 0))
- Vrepresentation()#
Return a list of names of
[vertices, rays, lines]
.EXAMPLES:
sage: P = Polyhedron(rays=[[1,0,0], [0,1,0], \ ....: [0,0,1],[0,0,-1]]) sage: C = CombinatorialPolyhedron(P) sage: C.Vrepresentation() (A line in the direction (0, 0, 1), A ray in the direction (1, 0, 0), A vertex at (0, 0, 0), A ray in the direction (0, 1, 0)) sage: points = [(1,0,0), (0,1,0), (0,0,1), ....: (-1,0,0), (0,-1,0), (0,0,-1)] sage: L = LatticePolytope(points) sage: C = CombinatorialPolyhedron(L) sage: C.Vrepresentation() (M(1, 0, 0), M(0, 1, 0), M(0, 0, 1), M(-1, 0, 0), M(0, -1, 0), M(0, 0, -1)) sage: M = Cone([(1,0), (0,1)]) sage: CombinatorialPolyhedron(M).Vrepresentation() (N(1, 0), N(0, 1), N(0, 0))
- a_maximal_chain(Vindex=None, Hindex=None)#
Return a maximal chain of the face lattice in increasing order without empty face and whole polyhedron/maximal face.
INPUT:
Vindex
– integer (default:None
); prescribe the index of the vertex in the chainHindex
– integer (default:None
); prescribe the index of the facet in the chain
Each face is given as
CombinatorialFace
.EXAMPLES:
sage: P = polytopes.cross_polytope(4) sage: C = P.combinatorial_polyhedron() sage: chain = C.a_maximal_chain(); chain [A 0-dimensional face of a 4-dimensional combinatorial polyhedron, A 1-dimensional face of a 4-dimensional combinatorial polyhedron, A 2-dimensional face of a 4-dimensional combinatorial polyhedron, A 3-dimensional face of a 4-dimensional combinatorial polyhedron] sage: [face.ambient_V_indices() for face in chain] [(7,), (6, 7), (5, 6, 7), (4, 5, 6, 7)] sage: P = polytopes.hypercube(4) sage: C = P.combinatorial_polyhedron() sage: chain = C.a_maximal_chain(); chain [A 0-dimensional face of a 4-dimensional combinatorial polyhedron, A 1-dimensional face of a 4-dimensional combinatorial polyhedron, A 2-dimensional face of a 4-dimensional combinatorial polyhedron, A 3-dimensional face of a 4-dimensional combinatorial polyhedron] sage: [face.ambient_V_indices() for face in chain] [(15,), (6, 15), (5, 6, 14, 15), (0, 5, 6, 7, 8, 9, 14, 15)] sage: # needs sage.combinat sage: P = polytopes.permutahedron(4) sage: C = P.combinatorial_polyhedron() sage: chain = C.a_maximal_chain(); chain [A 0-dimensional face of a 3-dimensional combinatorial polyhedron, A 1-dimensional face of a 3-dimensional combinatorial polyhedron, A 2-dimensional face of a 3-dimensional combinatorial polyhedron] sage: [face.ambient_V_indices() for face in chain] [(16,), (15, 16), (8, 9, 14, 15, 16, 17)] sage: P = Polyhedron(rays=[[1,0]], lines=[[0,1]]) sage: C = P.combinatorial_polyhedron() sage: chain = C.a_maximal_chain() sage: [face.ambient_V_indices() for face in chain] [(0, 1)] sage: P = Polyhedron(rays=[[1,0,0],[0,0,1]], lines=[[0,1,0]]) sage: C = P.combinatorial_polyhedron() sage: chain = C.a_maximal_chain() sage: [face.ambient_V_indices() for face in chain] [(0, 1), (0, 1, 3)] sage: P = Polyhedron(rays=[[1,0,0]], lines=[[0,1,0],[0,0,1]]) sage: C = P.combinatorial_polyhedron() sage: chain = C.a_maximal_chain() sage: [face.ambient_V_indices() for face in chain] [(0, 1, 2)]
Specify an index for the vertex of the chain:
sage: P = polytopes.cube() sage: C = P.combinatorial_polyhedron() sage: [face.ambient_V_indices() for face in C.a_maximal_chain()] [(5,), (0, 5), (0, 3, 4, 5)] sage: [face.ambient_V_indices() for face in C.a_maximal_chain(Vindex=2)] [(2,), (2, 7), (2, 3, 4, 7)]
Specify an index for the facet of the chain:
sage: [face.ambient_H_indices() for face in C.a_maximal_chain()] [(3, 4, 5), (4, 5), (5,)] sage: [face.ambient_H_indices() for face in C.a_maximal_chain(Hindex=3)] [(3, 4, 5), (3, 4), (3,)] sage: [face.ambient_H_indices() for face in C.a_maximal_chain(Hindex=2)] [(2, 3, 5), (2, 3), (2,)]
If the specified vertex is not contained in the specified facet an error is raised:
sage: C.a_maximal_chain(Vindex=0, Hindex=3) Traceback (most recent call last): ... ValueError: the given Vindex is not compatible with the given Hindex
An error is raised, if the specified index does not correspond to a facet:
sage: C.a_maximal_chain(Hindex=40) Traceback (most recent call last): ... ValueError: the given Hindex does not correspond to a facet
An error is raised, if the specified index does not correspond to a vertex:
sage: C.a_maximal_chain(Vindex=40) Traceback (most recent call last): ... ValueError: the given Vindex does not correspond to a vertex
sage: P = Polyhedron(rays=[[1,0,0],[0,0,1]], lines=[[0,1,0]]) sage: C = P.combinatorial_polyhedron() sage: C.a_maximal_chain(Vindex=0) Traceback (most recent call last): ... ValueError: the given Vindex does not correspond to a vertex
sage: P = Polyhedron(rays=[[1,0,0],[0,0,1]]) sage: C = P.combinatorial_polyhedron() sage: C.a_maximal_chain(Vindex=0) [A 0-dimensional face of a 2-dimensional combinatorial polyhedron, A 1-dimensional face of a 2-dimensional combinatorial polyhedron] sage: C.a_maximal_chain(Vindex=1) Traceback (most recent call last): ... ValueError: the given Vindex does not correspond to a vertex
- choose_algorithm_to_compute_edges_or_ridges(edges_or_ridges)#
Use some heuristics to pick primal or dual algorithm for computation of edges resp. ridges.
We estimate how long it takes to compute a face using the primal and the dual algorithm. This may differ significantly, so that e.g. visiting all faces with the primal algorithm is faster than using the dual algorithm to just visit vertices and edges.
We guess the number of edges and ridges and do a wild estimate on the total number of faces.
INPUT:
edges_or_ridges
– string; one of: *'edges'
*'ridges'
OUTPUT:
Either
'primal'
or'dual'
.EXAMPLES:
sage: C = polytopes.permutahedron(5).combinatorial_polyhedron() sage: C.choose_algorithm_to_compute_edges_or_ridges("edges") 'primal' sage: C.choose_algorithm_to_compute_edges_or_ridges("ridges") 'primal'
sage: C = polytopes.cross_polytope(5).combinatorial_polyhedron() sage: C.choose_algorithm_to_compute_edges_or_ridges("edges") 'dual' sage: C.choose_algorithm_to_compute_edges_or_ridges("ridges") 'dual'
sage: C = polytopes.Birkhoff_polytope(5).combinatorial_polyhedron() sage: C.choose_algorithm_to_compute_edges_or_ridges("edges") 'dual' sage: C.choose_algorithm_to_compute_edges_or_ridges("ridges") 'primal' sage: C.choose_algorithm_to_compute_edges_or_ridges("something_else") Traceback (most recent call last): ... ValueError: unknown computation goal something_else
- dim()#
Return the dimension of the polyhedron.
EXAMPLES:
sage: C = CombinatorialPolyhedron([(1,2,3), (1,2,4), ....: (1,3,4), (2,3,4)]) sage: C.dimension() 3 sage: P = Polyhedron(rays=[[1,0,0],[0,1,0],[0,0,1],[0,0,-1]]) sage: CombinatorialPolyhedron(P).dimension() 3
dim
is an alias:sage: CombinatorialPolyhedron(P).dim() 3
- dimension()#
Return the dimension of the polyhedron.
EXAMPLES:
sage: C = CombinatorialPolyhedron([(1,2,3), (1,2,4), ....: (1,3,4), (2,3,4)]) sage: C.dimension() 3 sage: P = Polyhedron(rays=[[1,0,0],[0,1,0],[0,0,1],[0,0,-1]]) sage: CombinatorialPolyhedron(P).dimension() 3
dim
is an alias:sage: CombinatorialPolyhedron(P).dim() 3
- dual()#
Return the dual/polar of self.
Only defined for bounded polyhedra.
See also
polar()
.EXAMPLES:
sage: P = polytopes.cube() sage: C = P.combinatorial_polyhedron() sage: D = C.dual() sage: D.f_vector() (1, 6, 12, 8, 1) sage: D1 = P.polar().combinatorial_polyhedron() sage: D1.face_lattice().is_isomorphic(D.face_lattice()) # needs sage.combinat True
Polar is an alias to be consistent with
Polyhedron_base
:sage: C.polar().f_vector() (1, 6, 12, 8, 1)
For unbounded polyhedra, an error is raised:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.dual() Traceback (most recent call last): ... ValueError: self must be bounded
- edges(names=True, algorithm=None)#
Return the edges of the polyhedron, i.e. the rank 1 faces.
INPUT:
names
– boolean (default:True
); ifFalse
, then the Vrepresentatives in the edges are given by their indices in the Vrepresentationalgorithm
– string (optional); specify whether the face generator starts with facets or vertices: *'primal'
– start with the facets *'dual'
– start with the vertices *None
– choose automatically
Note
To compute edges and f_vector, first compute the edges. This might be faster.
EXAMPLES:
sage: P = polytopes.cyclic_polytope(3,5) sage: C = CombinatorialPolyhedron(P) sage: C.edges() ((A vertex at (3, 9, 27), A vertex at (4, 16, 64)), (A vertex at (2, 4, 8), A vertex at (4, 16, 64)), (A vertex at (1, 1, 1), A vertex at (4, 16, 64)), (A vertex at (0, 0, 0), A vertex at (4, 16, 64)), (A vertex at (2, 4, 8), A vertex at (3, 9, 27)), (A vertex at (0, 0, 0), A vertex at (3, 9, 27)), (A vertex at (1, 1, 1), A vertex at (2, 4, 8)), (A vertex at (0, 0, 0), A vertex at (2, 4, 8)), (A vertex at (0, 0, 0), A vertex at (1, 1, 1))) sage: C.edges(names=False) ((3, 4), (2, 4), (1, 4), (0, 4), (2, 3), (0, 3), (1, 2), (0, 2), (0, 1)) sage: P = Polyhedron(rays=[[-1,0],[1,0]]) sage: C = CombinatorialPolyhedron(P) sage: C.edges() ((A line in the direction (1, 0), A vertex at (0, 0)),) sage: P = Polyhedron(vertices=[[0,0],[1,0]]) sage: C = CombinatorialPolyhedron(P) sage: C.edges() ((A vertex at (0, 0), A vertex at (1, 0)),) sage: from itertools import combinations sage: N = combinations(['a','b','c','d','e'], 4) sage: C = CombinatorialPolyhedron(N) sage: C.edges() (('d', 'e'), ('c', 'e'), ('b', 'e'), ('a', 'e'), ('c', 'd'), ('b', 'd'), ('a', 'd'), ('b', 'c'), ('a', 'c'), ('a', 'b'))
- f_vector(num_threads=None, parallelization_depth=None, algorithm=None)#
Compute the
f_vector
of the polyhedron.The
f_vector
contains the number of faces of dimension \(k\) for each \(k\) inrange(-1, self.dimension() + 1)
.INPUT:
num_threads
– integer (optional); specify the number of threadsparallelization_depth
– integer (optional); specify how deep in the lattice the parallelization is donealgorithm
– string (optional); specify whether the face generator starts with facets or vertices:'primal'
– start with the facets'dual'
– start with the verticesNone
– choose automatically
Note
To obtain edges and/or ridges as well, first do so. This might already compute the
f_vector
.EXAMPLES:
sage: P = polytopes.permutahedron(5) sage: C = CombinatorialPolyhedron(P) sage: C.f_vector() (1, 120, 240, 150, 30, 1) sage: P = polytopes.cyclic_polytope(6,10) sage: C = CombinatorialPolyhedron(P) sage: C.f_vector() (1, 10, 45, 120, 185, 150, 50, 1)
Using two threads:
sage: P = polytopes.permutahedron(5) sage: C = CombinatorialPolyhedron(P) sage: C.f_vector(num_threads=2) (1, 120, 240, 150, 30, 1)
- face_by_face_lattice_index(index)#
Return the element of
CombinatorialPolyhedron.face_lattice()
with corresponding index.The element will be returned as
CombinatorialFace
.EXAMPLES:
sage: # needs sage.combinat sage: P = polytopes.cube() sage: C = CombinatorialPolyhedron(P) sage: F = C.face_lattice() sage: F Finite lattice containing 28 elements sage: G = F.relabel(C.face_by_face_lattice_index) sage: G.level_sets()[0] [A -1-dimensional face of a 3-dimensional combinatorial polyhedron] sage: G.level_sets()[3] [A 2-dimensional face of a 3-dimensional combinatorial polyhedron, A 2-dimensional face of a 3-dimensional combinatorial polyhedron, A 2-dimensional face of a 3-dimensional combinatorial polyhedron, A 2-dimensional face of a 3-dimensional combinatorial polyhedron, A 2-dimensional face of a 3-dimensional combinatorial polyhedron, A 2-dimensional face of a 3-dimensional combinatorial polyhedron] sage: P = Polyhedron(rays=[[0,1], [1,0]]) sage: C = CombinatorialPolyhedron(P) sage: F = C.face_lattice() # needs sage.combinat sage: G = F.relabel(C.face_by_face_lattice_index) # needs sage.combinat sage: G._elements # needs sage.combinat (A -1-dimensional face of a 2-dimensional combinatorial polyhedron, A 0-dimensional face of a 2-dimensional combinatorial polyhedron, A 1-dimensional face of a 2-dimensional combinatorial polyhedron, A 1-dimensional face of a 2-dimensional combinatorial polyhedron, A 2-dimensional face of a 2-dimensional combinatorial polyhedron) sage: def f(i): return C.face_by_face_lattice_index(i).ambient_V_indices() sage: G = F.relabel(f) # needs sage.combinat sage: G._elements # needs sage.combinat ((), (0,), (0, 1), (0, 2), (0, 1, 2))
- face_generator(dimension=None, algorithm=None, **kwds)#
Iterator over all proper faces of specified dimension.
INPUT:
dimension
– if specified, then iterate over only this dimensionalgorithm
– string (optional); specify whether the face generator starts with facets or vertices:'primal'
– start with the facets'dual'
– start with the verticesNone
– choose automatically
OUTPUT:
Note
FaceIterator
can ignore subfaces or supfaces of the current face.EXAMPLES:
sage: # needs sage.combinat sage: P = polytopes.permutahedron(5) sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(dimension=2) sage: face = next(it); face A 2-dimensional face of a 4-dimensional combinatorial polyhedron sage: face.ambient_Vrepresentation() (A vertex at (1, 3, 2, 5, 4), A vertex at (2, 3, 1, 5, 4), A vertex at (3, 1, 2, 5, 4), A vertex at (3, 2, 1, 5, 4), A vertex at (2, 1, 3, 5, 4), A vertex at (1, 2, 3, 5, 4)) sage: face = next(it); face A 2-dimensional face of a 4-dimensional combinatorial polyhedron sage: face.ambient_Vrepresentation() (A vertex at (2, 1, 4, 5, 3), A vertex at (3, 2, 4, 5, 1), A vertex at (3, 1, 4, 5, 2), A vertex at (1, 3, 4, 5, 2), A vertex at (1, 2, 4, 5, 3), A vertex at (2, 3, 4, 5, 1)) sage: face.ambient_Hrepresentation() (An inequality (0, 0, -1, -1, 0) x + 9 >= 0, An inequality (0, 0, 0, -1, 0) x + 5 >= 0, An equation (1, 1, 1, 1, 1) x - 15 == 0) sage: face.ambient_H_indices() (25, 29, 30) sage: face = next(it); face A 2-dimensional face of a 4-dimensional combinatorial polyhedron sage: face.ambient_H_indices() (24, 29, 30) sage: face.ambient_V_indices() (32, 89, 90, 94) sage: C = CombinatorialPolyhedron([[0,1,2],[0,1,3],[0,2,3],[1,2,3]]) sage: it = C.face_generator() sage: for face in it: face.ambient_Vrepresentation() (1, 2, 3) (0, 2, 3) (0, 1, 3) (0, 1, 2) (2, 3) (1, 3) (1, 2) (3,) (2,) (1,) (0, 3) (0, 2) (0,) (0, 1) sage: P = Polyhedron(rays=[[1,0],[0,1]], vertices=[[1,0],[0,1]]) sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(1) sage: for face in it: face.ambient_Vrepresentation() (A vertex at (0, 1), A vertex at (1, 0)) (A ray in the direction (1, 0), A vertex at (1, 0)) (A ray in the direction (0, 1), A vertex at (0, 1))
See also
- face_iter(dimension=None, algorithm=None, **kwds)#
Iterator over all proper faces of specified dimension.
INPUT:
dimension
– if specified, then iterate over only this dimensionalgorithm
– string (optional); specify whether the face generator starts with facets or vertices:'primal'
– start with the facets'dual'
– start with the verticesNone
– choose automatically
OUTPUT:
Note
FaceIterator
can ignore subfaces or supfaces of the current face.EXAMPLES:
sage: # needs sage.combinat sage: P = polytopes.permutahedron(5) sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(dimension=2) sage: face = next(it); face A 2-dimensional face of a 4-dimensional combinatorial polyhedron sage: face.ambient_Vrepresentation() (A vertex at (1, 3, 2, 5, 4), A vertex at (2, 3, 1, 5, 4), A vertex at (3, 1, 2, 5, 4), A vertex at (3, 2, 1, 5, 4), A vertex at (2, 1, 3, 5, 4), A vertex at (1, 2, 3, 5, 4)) sage: face = next(it); face A 2-dimensional face of a 4-dimensional combinatorial polyhedron sage: face.ambient_Vrepresentation() (A vertex at (2, 1, 4, 5, 3), A vertex at (3, 2, 4, 5, 1), A vertex at (3, 1, 4, 5, 2), A vertex at (1, 3, 4, 5, 2), A vertex at (1, 2, 4, 5, 3), A vertex at (2, 3, 4, 5, 1)) sage: face.ambient_Hrepresentation() (An inequality (0, 0, -1, -1, 0) x + 9 >= 0, An inequality (0, 0, 0, -1, 0) x + 5 >= 0, An equation (1, 1, 1, 1, 1) x - 15 == 0) sage: face.ambient_H_indices() (25, 29, 30) sage: face = next(it); face A 2-dimensional face of a 4-dimensional combinatorial polyhedron sage: face.ambient_H_indices() (24, 29, 30) sage: face.ambient_V_indices() (32, 89, 90, 94) sage: C = CombinatorialPolyhedron([[0,1,2],[0,1,3],[0,2,3],[1,2,3]]) sage: it = C.face_generator() sage: for face in it: face.ambient_Vrepresentation() (1, 2, 3) (0, 2, 3) (0, 1, 3) (0, 1, 2) (2, 3) (1, 3) (1, 2) (3,) (2,) (1,) (0, 3) (0, 2) (0,) (0, 1) sage: P = Polyhedron(rays=[[1,0],[0,1]], vertices=[[1,0],[0,1]]) sage: C = CombinatorialPolyhedron(P) sage: it = C.face_generator(1) sage: for face in it: face.ambient_Vrepresentation() (A vertex at (0, 1), A vertex at (1, 0)) (A ray in the direction (1, 0), A vertex at (1, 0)) (A ray in the direction (0, 1), A vertex at (0, 1))
See also
- face_lattice()#
Generate the face-lattice.
OUTPUT:
Note
Use
CombinatorialPolyhedron.face_by_face_lattice_index()
to get the face for each index.Warning
The labeling of the face lattice might depend on architecture and implementation. Relabeling the face lattice with
CombinatorialPolyhedron.face_by_face_lattice_index()
or the properties obtained from this face will be platform independent.EXAMPLES:
sage: P = Polyhedron(rays=[[1,0],[0,1]]) sage: C = CombinatorialPolyhedron(P) sage: C.face_lattice() # needs sage.combinat Finite lattice containing 5 elements sage: P = Polyhedron(rays=[[1,0,0], [-1,0,0], [0,-1,0], [0,1,0]]) sage: C = CombinatorialPolyhedron(P) sage: P1 = Polyhedron(rays=[[1,0], [-1,0]]) sage: C1 = CombinatorialPolyhedron(P1) sage: C.face_lattice().is_isomorphic(C1.face_lattice()) # needs sage.combinat True sage: P = polytopes.permutahedron(5) sage: C = CombinatorialPolyhedron(P) sage: C.face_lattice() # needs sage.combinat Finite lattice containing 542 elements
- facet_adjacency_matrix(algorithm=None)#
Return the binary matrix of facet adjacencies.
INPUT:
algorithm
– string (optional); specify whether the face generator starts with facets or vertices: *'primal'
– start with the facets *'dual'
– start with the vertices *None
– choose automatically
See also
vertex_adjacency_matrix()
.EXAMPLES:
sage: P = polytopes.cube() sage: C = P.combinatorial_polyhedron() sage: C.facet_adjacency_matrix() [0 1 1 0 1 1] [1 0 1 1 1 0] [1 1 0 1 0 1] [0 1 1 0 1 1] [1 1 0 1 0 1] [1 0 1 1 1 0]
- facet_graph(names=True, algorithm=None)#
Return the facet graph.
The facet graph of a polyhedron consists of ridges as edges and facets as vertices.
INPUT:
algorithm
– string (optional); specify whether the face generator starts with facets or vertices:'primal'
– start with the facets'dual'
– start with the verticesNone
– choose automatically
If
names
isFalse
, thevertices
of the graph will be the indices of the facets in the Hrepresentation.EXAMPLES:
sage: P = polytopes.cyclic_polytope(4,6) sage: C = CombinatorialPolyhedron(P) sage: C.facet_graph() # needs sage.graphs Graph on 9 vertices
- facets(names=True)#
Return the facets as lists of
[vertices, rays, lines]
.If
names
isFalse
, then the Vrepresentatives in the facets are given by their indices in the Vrepresentation.The facets are the maximal nontrivial faces.
EXAMPLES:
sage: P = polytopes.cube() sage: C = CombinatorialPolyhedron(P) sage: C.facets() ((A vertex at (1, -1, -1), A vertex at (1, 1, -1), A vertex at (1, 1, 1), A vertex at (1, -1, 1)), (A vertex at (1, 1, -1), A vertex at (1, 1, 1), A vertex at (-1, 1, -1), A vertex at (-1, 1, 1)), (A vertex at (1, 1, 1), A vertex at (1, -1, 1), A vertex at (-1, -1, 1), A vertex at (-1, 1, 1)), (A vertex at (-1, -1, 1), A vertex at (-1, -1, -1), A vertex at (-1, 1, -1), A vertex at (-1, 1, 1)), (A vertex at (1, -1, -1), A vertex at (1, 1, -1), A vertex at (-1, -1, -1), A vertex at (-1, 1, -1)), (A vertex at (1, -1, -1), A vertex at (1, -1, 1), A vertex at (-1, -1, 1), A vertex at (-1, -1, -1))) sage: C.facets(names=False) ((0, 1, 2, 3), (1, 2, 6, 7), (2, 3, 4, 7), (4, 5, 6, 7), (0, 1, 5, 6), (0, 3, 4, 5))
The empty face is trivial and hence the
0
-dimensional polyhedron does not have facets:sage: C = CombinatorialPolyhedron(0) sage: C.facets() ()
- flag_f_vector(*args)#
Return the flag f-vector.
For each \(-1 < i_0 < \dots < i_n < d\) the flag f-vector counts the number of flags \(F_0 \subset \dots \subset F_n\) with \(F_j\) of dimension \(i_j\) for each \(0 \leq j \leq n\), where \(d\) is the dimension of the polyhedron.
INPUT:
args
– integers (optional); specify an entry of the flag-f-vector; must be an increasing sequence of integers
OUTPUT:
a dictionary, if no arguments were given
an Integer, if arguments were given
EXAMPLES:
Obtain the entire flag-f-vector:
sage: C = polytopes.hypercube(4).combinatorial_polyhedron() sage: C.flag_f_vector() # needs sage.combinat {(-1,): 1, (0,): 16, (0, 1): 64, (0, 1, 2): 192, (0, 1, 2, 3): 384, (0, 1, 3): 192, (0, 2): 96, (0, 2, 3): 192, (0, 3): 64, (1,): 32, (1, 2): 96, (1, 2, 3): 192, (1, 3): 96, (2,): 24, (2, 3): 48, (3,): 8, (4,): 1}
Specify an entry:
sage: C.flag_f_vector(0,3) # needs sage.combinat 64 sage: C.flag_f_vector(2) # needs sage.combinat 24
Leading
-1
and trailing entry of dimension are allowed:sage: C.flag_f_vector(-1,0,3) # needs sage.combinat 64 sage: C.flag_f_vector(-1,0,3,4) # needs sage.combinat 64
One can get the number of trivial faces:
sage: C.flag_f_vector(-1) # needs sage.combinat 1 sage: C.flag_f_vector(4) # needs sage.combinat 1
Polyhedra with lines, have
0
entries accordingly:sage: C = (Polyhedron(lines=[[1]]) * polytopes.hypercube(2)).combinatorial_polyhedron() sage: C.flag_f_vector() # needs sage.combinat {(-1,): 1, (0, 1): 0, (0, 2): 0, (0,): 0, (1, 2): 8, (1,): 4, (2,): 4, 3: 1}
If the arguments are not stricly increasing or out of range, a key error is raised:
sage: C.flag_f_vector(-1,0,3,5) # needs sage.combinat Traceback (most recent call last): ... KeyError: (0, 3, 5) sage: C.flag_f_vector(-1,3,0) # needs sage.combinat Traceback (most recent call last): ... KeyError: (3, 0)
- graph(names=True, algorithm=None)#
Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to bounded rank 1 faces.
INPUT:
names
– boolean (default:True
); ifFalse
, then the nodes of the graph are labeld by the indices of the Vrepresentationalgorithm
– string (optional); specify whether the face generator starts with facets or vertices: *'primal'
– start with the facets *'dual'
– start with the vertices *None
– choose automatically
EXAMPLES:
sage: P = polytopes.cyclic_polytope(3,5) sage: C = CombinatorialPolyhedron(P) sage: G = C.vertex_graph(); G # needs sage.graphs Graph on 5 vertices sage: sorted(G.degree()) # needs sage.graphs [3, 3, 4, 4, 4] sage: P = Polyhedron(rays=[[1]]) sage: C = CombinatorialPolyhedron(P) sage: C.graph() # needs sage.graphs Graph on 1 vertex
- hasse_diagram()#
Return the Hasse diagram of
self
.This is the Hasse diagram of the poset of the faces of
self
: A directed graph consisting of a vertex for each face and an edge for each minimal inclusion of faces.Note
The vertices of the Hasse diagram are given by indices. Use
CombinatorialPolyhedron.face_by_face_lattice_index()
to relabel.Warning
The indices of the Hasse diagram might depend on architecture and implementation. Relabeling the face lattice with
CombinatorialPolyhedron.face_by_face_lattice_index()
or the properties obtained from this face will be platform independentEXAMPLES:
sage: # needs sage.graphs sage.rings.number_field sage: P = polytopes.regular_polygon(4).pyramid() sage: C = CombinatorialPolyhedron(P) sage: D = C.hasse_diagram(); D Digraph on 20 vertices sage: D.average_degree() 21/5 sage: D.relabel(C.face_by_face_lattice_index) sage: dim_0_vert = D.vertices(sort=True)[1:6]; dim_0_vert [A 0-dimensional face of a 3-dimensional combinatorial polyhedron, A 0-dimensional face of a 3-dimensional combinatorial polyhedron, A 0-dimensional face of a 3-dimensional combinatorial polyhedron, A 0-dimensional face of a 3-dimensional combinatorial polyhedron, A 0-dimensional face of a 3-dimensional combinatorial polyhedron] sage: sorted(D.out_degree(vertices=dim_0_vert)) [3, 3, 3, 3, 4]
- incidence_matrix()#
Return the incidence matrix.
Note
The columns correspond to inequalities/equations in the order
Hrepresentation()
, the rows correspond to vertices/rays/lines in the orderVrepresentation()
.See also
incidence_matrix()
.EXAMPLES:
sage: P = polytopes.cube() sage: C = P.combinatorial_polyhedron() sage: C.incidence_matrix() [1 0 0 0 1 1] [1 1 0 0 1 0] [1 1 1 0 0 0] [1 0 1 0 0 1] [0 0 1 1 0 1] [0 0 0 1 1 1] [0 1 0 1 1 0] [0 1 1 1 0 0]
In this case the incidence matrix is only computed once:
sage: P.incidence_matrix() is C.incidence_matrix() True sage: C.incidence_matrix.clear_cache() sage: C.incidence_matrix() is P.incidence_matrix() False sage: C.incidence_matrix() == P.incidence_matrix() True
sage: # needs sage.combinat sage: P = polytopes.permutahedron(5, backend='field') sage: C = P.combinatorial_polyhedron() sage: C.incidence_matrix.clear_cache() sage: C.incidence_matrix() == P.incidence_matrix() True
The incidence matrix is consistent with
incidence_matrix()
:sage: P = Polyhedron([[0,0]]) sage: P.incidence_matrix() [1 1] sage: C = P.combinatorial_polyhedron() sage: C.incidence_matrix.clear_cache() sage: P.combinatorial_polyhedron().incidence_matrix() [1 1]
- is_bipyramid(certificate=False)#
Test whether the polytope is a bipyramid over some other polytope.
INPUT:
certificate
– boolean (default:False
); specifies whether to return a vertex of the polytope which is the apex of a pyramid, if found
INPUT:
certificate
– boolean (default:False
); specifies whether to return two vertices of the polytope which are the apices of a bipyramid, if found
OUTPUT:
If
certificate
isTrue
, returns a tuple containing:Boolean.
None
or a tuple containing:The first apex.
The second apex.
If
certificate
isFalse
returns a boolean.EXAMPLES:
sage: C = polytopes.hypercube(4).combinatorial_polyhedron() sage: C.is_bipyramid() False sage: C.is_bipyramid(certificate=True) (False, None) sage: C = polytopes.cross_polytope(4).combinatorial_polyhedron() sage: C.is_bipyramid() True sage: C.is_bipyramid(certificate=True) (True, [A vertex at (1, 0, 0, 0), A vertex at (-1, 0, 0, 0)])
For unbounded polyhedra, an error is raised:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.is_pyramid() Traceback (most recent call last): ... ValueError: polyhedron has to be compact
ALGORITHM:
Assume all faces of a polyhedron to be given as lists of vertices.
A polytope is a bipyramid with apexes \(v\), \(w\) if and only if for each proper face \(v \in F\) there exists a face \(G\) with \(G \setminus \{w\} = F \setminus \{v\}\) and vice versa (for each proper face \(w \in F\) there exists …).
To check this property it suffices to check for all facets of the polyhedron.
- is_compact()#
Return whether the polyhedron is compact
EXAMPLES:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.is_compact() False sage: C = CombinatorialPolyhedron([[0,1], [0,2], [1,2]]) sage: C.is_compact() True sage: P = polytopes.simplex() sage: P.combinatorial_polyhedron().is_compact() True sage: P = Polyhedron(rays=P.vertices()) sage: P.combinatorial_polyhedron().is_compact() False
- is_lawrence_polytope()#
Return
True
ifself
is a Lawrence polytope.A polytope is called a Lawrence polytope if it has a centrally symmetric (normalized) Gale diagram.
Equivalently, there exists a partition \(P_1,\dots,P_k\) of the vertices \(V\) such that each part \(P_i\) has size \(2\) or \(1\) and for each part there exists a facet with vertices exactly \(V \setminus P_i\).
EXAMPLES:
sage: C = polytopes.simplex(5).combinatorial_polyhedron() sage: C.is_lawrence_polytope() True sage: P = polytopes.hypercube(4).lawrence_polytope() sage: C = P.combinatorial_polyhedron() sage: C.is_lawrence_polytope() True sage: P = polytopes.hypercube(4) sage: C = P.combinatorial_polyhedron() sage: C.is_lawrence_polytope() False
For unbounded polyhedra, an error is raised:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.is_lawrence_polytope() Traceback (most recent call last): ... NotImplementedError: this function is implemented for polytopes only
AUTHORS:
Laith Rastanawi
Jonathan Kliem
REFERENCES:
For more information, see [BaSt1990].
- is_neighborly(k=None)#
Return whether the polyhedron is neighborly.
If the input \(k\) is provided, then return whether the polyhedron is \(k\)-neighborly.
A polyhedron is neighborly if every set of \(n\) vertices forms a face for \(n\) up to floor of half the dimension of the polyhedron. It is \(k\)-neighborly if this is true for \(n\) up to \(k\).
INPUT:
k
– the dimension up to which to check if every set ofk
vertices forms a face. If nok
is provided, check up to floor of half the dimension of the polyhedron.
OUTPUT:
True
if the every set of up tok
vertices forms a face,False
otherwise
See also
EXAMPLES:
sage: P = polytopes.cyclic_polytope(8,12) sage: C = P.combinatorial_polyhedron() sage: C.is_neighborly() True sage: P = polytopes.simplex(6) sage: C = P.combinatorial_polyhedron() sage: C.is_neighborly() True sage: P = polytopes.cyclic_polytope(4,10) sage: P = P.join(P) sage: C = P.combinatorial_polyhedron() sage: C.is_neighborly() False sage: C.is_neighborly(k=2) True
- is_prism(certificate=False)#
Test whether the polytope is a prism of some polytope.
INPUT:
certificate
– boolean (default:False
); specifies whether to return two facets of the polytope which are the bases of a prism, if found
OUTPUT:
If
certificate
isTrue
, returns a tuple containing:Boolean.
None
or a tuple containing:List of the vertices of the first base facet.
List of the vertices of the second base facet.
If
certificate
isFalse
returns a boolean.
- is_pyramid(certificate=False)#
Test whether the polytope is a pyramid over one of its facets.
INPUT:
certificate
– boolean (default:False
); specifies whether to return a vertex of the polytope which is the apex of a pyramid, if found
OUTPUT:
If
certificate
isTrue
, returns a tuple containing:Boolean.
The apex of the pyramid or
None
.
If
certificate
isFalse
returns a boolean.AUTHORS:
Laith Rastanawi
Jonathan Kliem
EXAMPLES:
sage: C = polytopes.cross_polytope(4).combinatorial_polyhedron() sage: C.is_pyramid() False sage: C.is_pyramid(certificate=True) (False, None) sage: C = polytopes.cross_polytope(4).pyramid().combinatorial_polyhedron() sage: C.is_pyramid() True sage: C.is_pyramid(certificate=True) (True, A vertex at (1, 0, 0, 0, 0)) sage: C = polytopes.simplex(5).combinatorial_polyhedron() sage: C.is_pyramid(certificate=True) (True, A vertex at (1, 0, 0, 0, 0, 0))
For unbounded polyhedra, an error is raised:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.is_pyramid() Traceback (most recent call last): ... ValueError: polyhedron has to be compact
- is_simple()#
Test whether the polytope is simple.
If the polyhedron is unbounded, return
False
.A polytope is simple, if each vertex is contained in exactly \(d\) facets, where \(d\) is the dimension of the polytope.
EXAMPLES:
sage: P = polytopes.cyclic_polytope(4,10) sage: C = P.combinatorial_polyhedron() sage: C.is_simple() False sage: P = polytopes.hypercube(4) sage: C = P.combinatorial_polyhedron() sage: C.is_simple() True
Return
False
for unbounded polyhedra:sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.is_simple() False
- is_simplex()#
Return whether the polyhedron is a simplex.
A simplex is a bounded polyhedron with \(d+1\) vertices, where \(d\) is the dimension.
EXAMPLES:
sage: CombinatorialPolyhedron(2).is_simplex() False sage: CombinatorialPolyhedron([[0,1],[0,2],[1,2]]).is_simplex() True
- is_simplicial()#
Test whether the polytope is simplicial.
This method is not implemented for unbounded polyhedra.
A polytope is simplicial, if each facet contains exactly \(d\) vertices, where \(d\) is the dimension of the polytope.
EXAMPLES:
sage: P = polytopes.cyclic_polytope(4,10) sage: C = P.combinatorial_polyhedron() sage: C.is_simplicial() True sage: P = polytopes.hypercube(4) sage: C = P.combinatorial_polyhedron() sage: C.is_simplicial() False
For unbounded polyhedra, an error is raised:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.is_simplicial() Traceback (most recent call last): ... NotImplementedError: this function is implemented for polytopes only
- join_of_Vrep(*indices)#
Return the smallest face containing all Vrepresentatives indicated by the indices.
See also
join_of_Vrep()
.EXAMPLES:
sage: # needs sage.combinat sage: P = polytopes.permutahedron(4) sage: C = CombinatorialPolyhedron(P) sage: C.join_of_Vrep(0,1) A 1-dimensional face of a 3-dimensional combinatorial polyhedron sage: C.join_of_Vrep(0,11).ambient_V_indices() (0, 1, 10, 11, 12, 13) sage: C.join_of_Vrep(8).ambient_V_indices() (8,) sage: C.join_of_Vrep().ambient_V_indices() ()
- meet_of_Hrep(*indices)#
Return the largest face contained in all facets indicated by the indices.
See also
meet_of_Hrep()
.EXAMPLES:
sage: # needs sage.rings.number_field sage: P = polytopes.dodecahedron() sage: C = CombinatorialPolyhedron(P) sage: C.meet_of_Hrep(0) A 2-dimensional face of a 3-dimensional combinatorial polyhedron sage: C.meet_of_Hrep(0).ambient_H_indices() (0,) sage: C.meet_of_Hrep(0,1).ambient_H_indices() (0, 1) sage: C.meet_of_Hrep(0,2).ambient_H_indices() (0, 2) sage: C.meet_of_Hrep(0,2,3).ambient_H_indices() (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) sage: C.meet_of_Hrep().ambient_H_indices() ()
- n_facets()#
Return the number of facets.
Is equivalent to
len(self.facets())
.EXAMPLES:
sage: P = polytopes.cube() sage: C = CombinatorialPolyhedron(P) sage: C.n_facets() 6 sage: P = polytopes.cyclic_polytope(4,20) sage: C = CombinatorialPolyhedron(P) sage: C.n_facets() 170 sage: P = Polyhedron(lines=[[0,1]], vertices=[[1,0], [-1,0]]) sage: C = CombinatorialPolyhedron(P) sage: C.n_facets() 2 sage: P = Polyhedron(rays=[[1,0], [-1,0], [0,1]]) sage: C = CombinatorialPolyhedron(P) sage: C.n_facets() 1 sage: C = CombinatorialPolyhedron(-1) sage: C.f_vector() (1) sage: C.n_facets() 0
Facets are defined to be the maximal nontrivial faces. The
0
-dimensional polyhedron does not have nontrivial faces:sage: C = CombinatorialPolyhedron(0) sage: C.f_vector() (1, 1) sage: C.n_facets() 0
- n_vertices()#
Return the number of vertices.
Is equivalent to
len(self.vertices())
.EXAMPLES:
sage: P = polytopes.cube() sage: C = CombinatorialPolyhedron(P) sage: C.n_vertices() 8 sage: P = polytopes.cyclic_polytope(4,20) sage: C = CombinatorialPolyhedron(P) sage: C.n_vertices() 20 sage: P = Polyhedron(lines=[[0,1]], vertices=[[1,0], [-1,0]]) sage: C = CombinatorialPolyhedron(P) sage: C.n_vertices() 0 sage: P = Polyhedron(rays=[[1,0,0], [0,1,0]], lines=[[0,0,1]]) sage: C = CombinatorialPolyhedron(P) sage: C.n_vertices() 0 sage: C = CombinatorialPolyhedron(4) sage: C.f_vector() (1, 0, 0, 0, 0, 1) sage: C.n_vertices() 0 sage: C = CombinatorialPolyhedron(0) sage: C.f_vector() (1, 1) sage: C.n_vertices() 1
- neighborliness()#
Return the largest
k
, such that the polyhedron isk
-neighborly.A polyhedron is \(k\)-neighborly if every set of \(n\) vertices forms a face for \(n\) up to \(k\).
In case of the \(d\)-dimensional simplex, it returns \(d + 1\).
See also
EXAMPLES:
sage: P = polytopes.cyclic_polytope(8,12) sage: C = P.combinatorial_polyhedron() sage: C.neighborliness() 4 sage: P = polytopes.simplex(6) sage: C = P.combinatorial_polyhedron() sage: C.neighborliness() 7 sage: P = polytopes.cyclic_polytope(4,10) sage: P = P.join(P) sage: C = P.combinatorial_polyhedron() sage: C.neighborliness() 2
- polar()#
Return the dual/polar of self.
Only defined for bounded polyhedra.
See also
polar()
.EXAMPLES:
sage: P = polytopes.cube() sage: C = P.combinatorial_polyhedron() sage: D = C.dual() sage: D.f_vector() (1, 6, 12, 8, 1) sage: D1 = P.polar().combinatorial_polyhedron() sage: D1.face_lattice().is_isomorphic(D.face_lattice()) # needs sage.combinat True
Polar is an alias to be consistent with
Polyhedron_base
:sage: C.polar().f_vector() (1, 6, 12, 8, 1)
For unbounded polyhedra, an error is raised:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.dual() Traceback (most recent call last): ... ValueError: self must be bounded
- pyramid(new_vertex=None, new_facet=None)#
Return the pyramid of
self
.INPUT:
new_vertex
– (optional); specify a new vertex name to set up the pyramid with vertex namesnew_facet
– (optional); specify a new facet name to set up the pyramid with facet names
EXAMPLES:
sage: C = CombinatorialPolyhedron(((1,2,3),(1,2,4),(1,3,4),(2,3,4))) sage: C1 = C.pyramid() sage: C1.facets() ((0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), (1, 2, 3, 4), (0, 1, 2, 3))
sage: P = polytopes.cube() sage: C = CombinatorialPolyhedron(P) sage: C1 = C.pyramid() sage: P1 = P.pyramid() sage: C2 = P1.combinatorial_polyhedron() sage: C2.vertex_facet_graph().is_isomorphic(C1.vertex_facet_graph()) # needs sage.combinat True
One can specify a name for the new vertex:
sage: P = polytopes.cyclic_polytope(4,10) sage: C = P.combinatorial_polyhedron() sage: C1 = C.pyramid(new_vertex='apex') sage: C1.is_pyramid(certificate=True) (True, 'apex') sage: C1.facets()[0] (A vertex at (0, 0, 0, 0), A vertex at (1, 1, 1, 1), A vertex at (2, 4, 8, 16), A vertex at (3, 9, 27, 81), 'apex')
One can specify a name for the new facets:
sage: # needs sage.rings.number_field sage: P = polytopes.regular_polygon(4) sage: C = P.combinatorial_polyhedron() sage: C1 = C.pyramid(new_facet='base') sage: C1.Hrepresentation() (An inequality (-1/2, 1/2) x + 1/2 >= 0, An inequality (-1/2, -1/2) x + 1/2 >= 0, An inequality (1/2, 0.50000000000000000?) x + 1/2 >= 0, An inequality (1/2, -1/2) x + 1/2 >= 0, 'base')
For unbounded polyhedra, an error is raised:
sage: C = CombinatorialPolyhedron([[0,1], [0,2]], far_face=[1,2], unbounded=True) sage: C.pyramid() Traceback (most recent call last): ... ValueError: self must be bounded
- ridges(add_equations=False, names=True, add_equalities=False, algorithm=None)#
Return the ridges.
The ridges of a polyhedron are the faces contained in exactly two facets.
To obtain all faces of codimension 1 use
CombinatorialPolyhedron.face_generator()
instead.The ridges will be given by the facets, they are contained in.
INPUT:
add_equations
– ifTrue
, then equations of the polyhedron will be added (only applicable whennames
isTrue
)names
– boolean (default: \(True\)); ifFalse
, then the facets are given by their indicesalgorithm
– string (optional); specify whether the face generator starts with facets or vertices: *'primal'
– start with the facets *'dual'
– start with the vertices *None
– choose automatically
Note
To compute ridges and f_vector, compute the ridges first. This might be faster.
EXAMPLES:
sage: # needs sage.combinat sage: P = polytopes.permutahedron(2) sage: C = CombinatorialPolyhedron(P) sage: C.ridges() ((An inequality (1, 0) x - 1 >= 0, An inequality (-1, 0) x + 2 >= 0),) sage: C.ridges(add_equations=True) (((An inequality (1, 0) x - 1 >= 0, An equation (1, 1) x - 3 == 0), (An inequality (-1, 0) x + 2 >= 0, An equation (1, 1) x - 3 == 0)),) sage: P = polytopes.cyclic_polytope(4,5) sage: C = CombinatorialPolyhedron(P) sage: C.ridges() ((An inequality (24, -26, 9, -1) x + 0 >= 0, An inequality (-50, 35, -10, 1) x + 24 >= 0), (An inequality (-12, 19, -8, 1) x + 0 >= 0, An inequality (-50, 35, -10, 1) x + 24 >= 0), (An inequality (8, -14, 7, -1) x + 0 >= 0, An inequality (-50, 35, -10, 1) x + 24 >= 0), (An inequality (-6, 11, -6, 1) x + 0 >= 0, An inequality (-50, 35, -10, 1) x + 24 >= 0), (An inequality (-12, 19, -8, 1) x + 0 >= 0, An inequality (24, -26, 9, -1) x + 0 >= 0), (An inequality (8, -14, 7, -1) x + 0 >= 0, An inequality (24, -26, 9, -1) x + 0 >= 0), (An inequality (-6, 11, -6, 1) x + 0 >= 0, An inequality (24, -26, 9, -1) x + 0 >= 0), (An inequality (8, -14, 7, -1) x + 0 >= 0, An inequality (-12, 19, -8, 1) x + 0 >= 0), (An inequality (-6, 11, -6, 1) x + 0 >= 0, An inequality (-12, 19, -8, 1) x + 0 >= 0), (An inequality (-6, 11, -6, 1) x + 0 >= 0, An inequality (8, -14, 7, -1) x + 0 >= 0)) sage: C.ridges(names=False) ((3, 4), (2, 4), (1, 4), (0, 4), (2, 3), (1, 3), (0, 3), (1, 2), (0, 2), (0, 1)) sage: P = Polyhedron(rays=[[1,0]]) sage: C = CombinatorialPolyhedron(P) sage: C A 1-dimensional combinatorial polyhedron with 1 facet sage: C.ridges() () sage: it = C.face_generator(0) sage: for face in it: face.ambient_Hrepresentation() (An inequality (1, 0) x + 0 >= 0, An equation (0, 1) x + 0 == 0)
- simpliciality()#
Return the largest \(k\) such that the polytope is \(k\)-simplicial.
Return the dimension in case of a simplex.
A polytope is \(k\)-simplicial, if every \(k\)-face is a simplex.
EXAMPLES:
sage: cyclic = polytopes.cyclic_polytope(10,4) sage: CombinatorialPolyhedron(cyclic).simpliciality() 3 sage: hypersimplex = polytopes.hypersimplex(5,2) sage: CombinatorialPolyhedron(hypersimplex).simpliciality() 2 sage: cross = polytopes.cross_polytope(4) sage: P = cross.join(cross) sage: CombinatorialPolyhedron(P).simpliciality() 3 sage: P = polytopes.simplex(3) sage: CombinatorialPolyhedron(P).simpliciality() 3 sage: P = polytopes.simplex(1) sage: CombinatorialPolyhedron(P).simpliciality() 1
- simplicity()#
Return the largest \(k\) such that the polytope is \(k\)-simple.
Return the dimension in case of a simplex.
A polytope \(P\) is \(k\)-simple, if every \((d-1-k)\)-face is contained in exactly \(k+1\) facets of \(P\) for \(1 \leq k \leq d-1\).
Equivalently it is \(k\)-simple if the polar/dual polytope is \(k\)-simplicial.
EXAMPLES:
sage: hyper4 = polytopes.hypersimplex(4,2) sage: CombinatorialPolyhedron(hyper4).simplicity() 1 sage: hyper5 = polytopes.hypersimplex(5,2) sage: CombinatorialPolyhedron(hyper5).simplicity() 2 sage: hyper6 = polytopes.hypersimplex(6,2) sage: CombinatorialPolyhedron(hyper6).simplicity() 3 sage: P = polytopes.simplex(3) sage: CombinatorialPolyhedron(P).simplicity() 3 sage: P = polytopes.simplex(1) sage: CombinatorialPolyhedron(P).simplicity() 1
- vertex_adjacency_matrix(algorithm=None)#
Return the binary matrix of vertex adjacencies.
INPUT:
algorithm
– string (optional); specify whether the face generator starts with facets or vertices: *'primal'
– start with the facets *'dual'
– start with the vertices *None
– choose automatically
See also
vertex_adjacency_matrix()
.EXAMPLES:
sage: P = polytopes.cube() sage: C = P.combinatorial_polyhedron() sage: C.vertex_adjacency_matrix() [0 1 0 1 0 1 0 0] [1 0 1 0 0 0 1 0] [0 1 0 1 0 0 0 1] [1 0 1 0 1 0 0 0] [0 0 0 1 0 1 0 1] [1 0 0 0 1 0 1 0] [0 1 0 0 0 1 0 1] [0 0 1 0 1 0 1 0]
- vertex_facet_graph(names=True)#
Return the vertex-facet graph.
This method constructs a directed bipartite graph. The nodes of the graph correspond to elements of the Vrepresentation and facets. There is a directed edge from Vrepresentation to facets for each incidence.
If
names
is set toFalse
, then the vertices (of the graph) are given by integers.INPUT:
names
– boolean (default:True
); ifTrue
label the vertices of the graph by the corresponding names of the Vrepresentation resp. Hrepresentation; ifFalse
label the vertices of the graph by integers
EXAMPLES:
sage: P = polytopes.hypercube(2).pyramid() sage: C = CombinatorialPolyhedron(P) sage: G = C.vertex_facet_graph(); G # needs sage.graphs Digraph on 10 vertices sage: C.Vrepresentation() (A vertex at (0, -1, -1), A vertex at (0, -1, 1), A vertex at (0, 1, -1), A vertex at (0, 1, 1), A vertex at (1, 0, 0)) sage: sorted(G.neighbors_out(C.Vrepresentation()[4])) # needs sage.graphs [An inequality (-1, -1, 0) x + 1 >= 0, An inequality (-1, 0, -1) x + 1 >= 0, An inequality (-1, 0, 1) x + 1 >= 0, An inequality (-1, 1, 0) x + 1 >= 0]
If
names
isTrue
(the default) but the combinatorial polyhedron has been initialized without specifying names toVrepresentation
andHrepresentation
, then indices of the Vrepresentation and the facets will be used along with a string ‘H’ or ‘V’:sage: C = CombinatorialPolyhedron(P.incidence_matrix()) sage: C.vertex_facet_graph().vertices(sort=True) # needs sage.graphs [('H', 0), ('H', 1), ('H', 2), ('H', 3), ('H', 4), ('V', 0), ('V', 1), ('V', 2), ('V', 3), ('V', 4)]
If
names
isFalse
then the vertices of the graph are given by integers:sage: C.vertex_facet_graph(names=False).vertices(sort=True) # needs sage.graphs [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
- vertex_graph(names=True, algorithm=None)#
Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to bounded rank 1 faces.
INPUT:
names
– boolean (default:True
); ifFalse
, then the nodes of the graph are labeld by the indices of the Vrepresentationalgorithm
– string (optional); specify whether the face generator starts with facets or vertices: *'primal'
– start with the facets *'dual'
– start with the vertices *None
– choose automatically
EXAMPLES:
sage: P = polytopes.cyclic_polytope(3,5) sage: C = CombinatorialPolyhedron(P) sage: G = C.vertex_graph(); G # needs sage.graphs Graph on 5 vertices sage: sorted(G.degree()) # needs sage.graphs [3, 3, 4, 4, 4] sage: P = Polyhedron(rays=[[1]]) sage: C = CombinatorialPolyhedron(P) sage: C.graph() # needs sage.graphs Graph on 1 vertex
- vertices(names=True)#
Return the elements in the Vrepresentation that are vertices.
In case of an unbounded polyhedron, there might be lines and rays in the Vrepresentation.
If
names
is set toFalse
, then the vertices are given by their indices in the Vrepresentation.EXAMPLES:
sage: P = Polyhedron(rays=[[1,0,0],[0,1,0],[0,0,1]]) sage: C = CombinatorialPolyhedron(P) sage: C.vertices() (A vertex at (0, 0, 0),) sage: C.Vrepresentation() (A vertex at (0, 0, 0), A ray in the direction (0, 0, 1), A ray in the direction (0, 1, 0), A ray in the direction (1, 0, 0)) sage: P = polytopes.cross_polytope(3) sage: C = CombinatorialPolyhedron(P) sage: C.vertices() (A vertex at (-1, 0, 0), A vertex at (0, -1, 0), A vertex at (0, 0, -1), A vertex at (0, 0, 1), A vertex at (0, 1, 0), A vertex at (1, 0, 0)) sage: C.vertices(names=False) (0, 1, 2, 3, 4, 5) sage: points = [(1,0,0), (0,1,0), (0,0,1), ....: (-1,0,0), (0,-1,0), (0,0,-1)] sage: L = LatticePolytope(points) sage: C = CombinatorialPolyhedron(L) sage: C.vertices() (M(1, 0, 0), M(0, 1, 0), M(0, 0, 1), M(-1, 0, 0), M(0, -1, 0), M(0, 0, -1)) sage: C.vertices(names=False) (0, 1, 2, 3, 4, 5) sage: P = Polyhedron(vertices=[[0,0]]) sage: C = CombinatorialPolyhedron(P) sage: C.vertices() (A vertex at (0, 0),)