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 of

    • Polyhedron_base

    • or a LatticePolytopeClass

    • or a ConvexRationalPolyhedralCone

    • or an incidence_matrix as in incidence_matrix() In this case you should also specify the Vrep and facets arguments

    • or 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 argument nr_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 see Polyhedron_base on how to use rays and lines

    • or 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) when data is an incidence matrix, it should be the list of [vertices, rays, lines], if the rows in the incidence_matrix should correspond to names

  • facets – (optional) when data 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 if data is a polyhedron; if unbounded and data is incidence matrix or a list of facets, need to specify far_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 unless data is an instance of Polyhedron_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 to False:

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 chain

  • Hindex – 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); if False, then the Vrepresentatives in the edges are given by their indices in the Vrepresentation

  • 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

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\) in range(-1, self.dimension() + 1).

INPUT:

  • num_threads – integer (optional); specify the number of threads

  • parallelization_depth – integer (optional); specify how deep in the lattice the parallelization is done

  • 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

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 dimension

  • 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

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

FaceIterator, CombinatorialFace.

face_iter(dimension=None, algorithm=None, **kwds)#

Iterator over all proper faces of specified dimension.

INPUT:

  • dimension – if specified, then iterate over only this dimension

  • 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

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

FaceIterator, CombinatorialFace.

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 vertices

    • None – choose automatically

If names is False, the vertices 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 is False, 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); if False, then the nodes of the graph are labeld by the indices of the Vrepresentation

  • 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

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 independent

EXAMPLES:

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 order Vrepresentation().

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 is True, returns a tuple containing:

  1. Boolean.

  2. None or a tuple containing:

    1. The first apex.

    2. The second apex.

If certificate is False 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 if self 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 of k vertices forms a face. If no k is provided, check up to floor of half the dimension of the polyhedron.

OUTPUT:

  • True if the every set of up to k vertices forms a face,

  • False otherwise

See also

neighborliness()

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 is True, returns a tuple containing:

  1. Boolean.

  2. None or a tuple containing:

    1. List of the vertices of the first base facet.

    2. List of the vertices of the second base facet.

If certificate is False 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 is True, returns a tuple containing:

  1. Boolean.

  2. The apex of the pyramid or None.

If certificate is False 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 is k-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

is_neighborly()

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 names

  • new_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 – if True, then equations of the polyhedron will be added (only applicable when names is True)

  • names – boolean (default: \(True\)); if False, then the facets are given by their indices

  • 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

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 to False, then the vertices (of the graph) are given by integers.

INPUT:

  • names – boolean (default: True); if True label the vertices of the graph by the corresponding names of the Vrepresentation resp. Hrepresentation; if False 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 is True (the default) but the combinatorial polyhedron has been initialized without specifying names to Vrepresentation and Hrepresentation, 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 is False 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); if False, then the nodes of the graph are labeld by the indices of the Vrepresentation

  • 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

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 to False, 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),)