Base class for polyhedra: Graph-theoretic methods¶

Define methods relying on sage.graphs.

class sage.geometry.polyhedron.base4.Polyhedron_base4(parent, Vrep, Hrep, Vrep_minimal=None, Hrep_minimal=None, pref_rep=None, mutable=False, **kwds)[source]¶

Bases: Polyhedron_base3

Methods relying on sage.graphs.

See sage.geometry.polyhedron.base.Polyhedron_base.

combinatorial_automorphism_group(vertex_graph_only=False)[source]¶

Compute the combinatorial automorphism group.

If vertex_graph_only is True, the automorphism group of the vertex-edge graph of the polyhedron is returned. Otherwise the automorphism group of the vertex-facet graph, which is isomorphic to the automorphism group of the face lattice is returned.

INPUT:

vertex_graph_only – boolean (default: False); whether to return the automorphism group of the vertex edges graph or of the lattice

OUTPUT:

A PermutationGroup that is isomorphic to the combinatorial automorphism group is returned.

if vertex_graph_only is True: The automorphism group of the vertex-edge graph of the polyhedron
if vertex_graph_only is False (default): The automorphism group of the vertex-facet graph of the polyhedron, see vertex_facet_graph(). This group is isomorphic to the automorphism group of the face lattice of the polyhedron.

NOTE:

Depending on vertex_graph_only, this method returns groups that are not necessarily isomorphic, see the examples below.

EXAMPLES:

Sage

sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)])
sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(          # needs sage.groups
....:     groups.permutation.Dihedral(4))
True
sage: quadrangle.restricted_automorphism_group()                            # needs sage.groups
Permutation Group with generators [()]

Python

>>> from sage.all import *
>>> quadrangle = Polyhedron(vertices=[(Integer(0),Integer(0)),(Integer(1),Integer(0)),(Integer(0),Integer(1)),(Integer(2),Integer(3))])
>>> quadrangle.combinatorial_automorphism_group().is_isomorphic(          # needs sage.groups
...     groups.permutation.Dihedral(Integer(4)))
True
>>> quadrangle.restricted_automorphism_group()                            # needs sage.groups
Permutation Group with generators [()]

Sage Live

quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)])
quadrangle.combinatorial_automorphism_group().is_isomorphic(          # needs sage.groups
    groups.permutation.Dihedral(4))
quadrangle.restricted_automorphism_group()                            # needs sage.groups

Permutations of the vertex graph only exchange vertices with vertices:

Sage

sage: P = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)])
sage: P.combinatorial_automorphism_group(vertex_graph_only=True)            # needs sage.groups
Permutation Group with generators [(A vertex at (1,0),A vertex at (1,1))]

Python

>>> from sage.all import *
>>> P = Polyhedron(vertices=[(Integer(1),Integer(0)), (Integer(1),Integer(1))], rays=[(Integer(1),Integer(0))])
>>> P.combinatorial_automorphism_group(vertex_graph_only=True)            # needs sage.groups
Permutation Group with generators [(A vertex at (1,0),A vertex at (1,1))]

Sage Live

P = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)])
P.combinatorial_automorphism_group(vertex_graph_only=True)            # needs sage.groups

This shows an example of two polytopes whose vertex-edge graphs are isomorphic, but their face lattices are not isomorphic:

Sage

sage: # needs sage.groups
sage: Q = Polyhedron([[-123984206864/2768850730773, -101701330976/922950243591, -64154618668/2768850730773, -2748446474675/2768850730773],
....:                 [-11083969050/98314591817, -4717557075/98314591817, -32618537490/98314591817, -91960210208/98314591817],
....:                 [-9690950/554883199, -73651220/554883199, 1823050/554883199, -549885101/554883199],
....:                 [-5174928/72012097, 5436288/72012097, -37977984/72012097, 60721345/72012097],
....:                 [-19184/902877, 26136/300959, -21472/902877, 899005/902877],
....:                 [53511524/1167061933, 88410344/1167061933, 621795064/1167061933, 982203941/1167061933],
....:                 [4674489456/83665171433, -4026061312/83665171433, 28596876672/83665171433, -78383796375/83665171433],
....:                 [857794884940/98972360190089, -10910202223200/98972360190089, 2974263671400/98972360190089, -98320463346111/98972360190089]])
sage: C = polytopes.cyclic_polytope(4,8)
sage: C.is_combinatorially_isomorphic(Q)
False
sage: C.combinatorial_automorphism_group(vertex_graph_only=True).is_isomorphic(
....:     Q.combinatorial_automorphism_group(vertex_graph_only=True))
True
sage: C.combinatorial_automorphism_group(vertex_graph_only=False).is_isomorphic(
....:     Q.combinatorial_automorphism_group(vertex_graph_only=False))
False

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> Q = Polyhedron([[-Integer(123984206864)/Integer(2768850730773), -Integer(101701330976)/Integer(922950243591), -Integer(64154618668)/Integer(2768850730773), -Integer(2748446474675)/Integer(2768850730773)],
...                 [-Integer(11083969050)/Integer(98314591817), -Integer(4717557075)/Integer(98314591817), -Integer(32618537490)/Integer(98314591817), -Integer(91960210208)/Integer(98314591817)],
...                 [-Integer(9690950)/Integer(554883199), -Integer(73651220)/Integer(554883199), Integer(1823050)/Integer(554883199), -Integer(549885101)/Integer(554883199)],
...                 [-Integer(5174928)/Integer(72012097), Integer(5436288)/Integer(72012097), -Integer(37977984)/Integer(72012097), Integer(60721345)/Integer(72012097)],
...                 [-Integer(19184)/Integer(902877), Integer(26136)/Integer(300959), -Integer(21472)/Integer(902877), Integer(899005)/Integer(902877)],
...                 [Integer(53511524)/Integer(1167061933), Integer(88410344)/Integer(1167061933), Integer(621795064)/Integer(1167061933), Integer(982203941)/Integer(1167061933)],
...                 [Integer(4674489456)/Integer(83665171433), -Integer(4026061312)/Integer(83665171433), Integer(28596876672)/Integer(83665171433), -Integer(78383796375)/Integer(83665171433)],
...                 [Integer(857794884940)/Integer(98972360190089), -Integer(10910202223200)/Integer(98972360190089), Integer(2974263671400)/Integer(98972360190089), -Integer(98320463346111)/Integer(98972360190089)]])
>>> C = polytopes.cyclic_polytope(Integer(4),Integer(8))
>>> C.is_combinatorially_isomorphic(Q)
False
>>> C.combinatorial_automorphism_group(vertex_graph_only=True).is_isomorphic(
...     Q.combinatorial_automorphism_group(vertex_graph_only=True))
True
>>> C.combinatorial_automorphism_group(vertex_graph_only=False).is_isomorphic(
...     Q.combinatorial_automorphism_group(vertex_graph_only=False))
False

Sage Live

# needs sage.groups
Q = Polyhedron([[-123984206864/2768850730773, -101701330976/922950243591, -64154618668/2768850730773, -2748446474675/2768850730773],
                [-11083969050/98314591817, -4717557075/98314591817, -32618537490/98314591817, -91960210208/98314591817],
                [-9690950/554883199, -73651220/554883199, 1823050/554883199, -549885101/554883199],
                [-5174928/72012097, 5436288/72012097, -37977984/72012097, 60721345/72012097],
                [-19184/902877, 26136/300959, -21472/902877, 899005/902877],
                [53511524/1167061933, 88410344/1167061933, 621795064/1167061933, 982203941/1167061933],
                [4674489456/83665171433, -4026061312/83665171433, 28596876672/83665171433, -78383796375/83665171433],
                [857794884940/98972360190089, -10910202223200/98972360190089, 2974263671400/98972360190089, -98320463346111/98972360190089]])
C = polytopes.cyclic_polytope(4,8)
C.is_combinatorially_isomorphic(Q)
C.combinatorial_automorphism_group(vertex_graph_only=True).is_isomorphic(
    Q.combinatorial_automorphism_group(vertex_graph_only=True))
C.combinatorial_automorphism_group(vertex_graph_only=False).is_isomorphic(
    Q.combinatorial_automorphism_group(vertex_graph_only=False))

The automorphism group of the face lattice is isomorphic to the combinatorial automorphism group:

Sage

sage: # needs sage.groups
sage: CG = C.hasse_diagram().automorphism_group()
sage: C.combinatorial_automorphism_group().is_isomorphic(CG)
True
sage: QG = Q.hasse_diagram().automorphism_group()
sage: Q.combinatorial_automorphism_group().is_isomorphic(QG)
True

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> CG = C.hasse_diagram().automorphism_group()
>>> C.combinatorial_automorphism_group().is_isomorphic(CG)
True
>>> QG = Q.hasse_diagram().automorphism_group()
>>> Q.combinatorial_automorphism_group().is_isomorphic(QG)
True

Sage Live

# needs sage.groups
CG = C.hasse_diagram().automorphism_group()
C.combinatorial_automorphism_group().is_isomorphic(CG)
QG = Q.hasse_diagram().automorphism_group()
Q.combinatorial_automorphism_group().is_isomorphic(QG)

face_lattice()[source]¶

Return the face-lattice poset.

OUTPUT:

A FinitePoset. Elements are given as PolyhedronFace.

In the case of a full-dimensional polytope, the faces are pairs (vertices, inequalities) of the spanning vertices and corresponding saturated inequalities. In general, a face is defined by a pair (V-rep. objects, H-rep. objects). The V-representation objects span the face, and the corresponding H-representation objects are those inequalities and equations that are saturated on the face.

The bottom-most element of the face lattice is the “empty face”. It contains no V-representation object. All H-representation objects are incident.

The top-most element is the “full face”. It is spanned by all V-representation objects. The incident H-representation objects are all equations and no inequalities.

In the case of a full-dimensional polytope, the “empty face” and the “full face” are the empty set (no vertices, all inequalities) and the full polytope (all vertices, no inequalities), respectively.

ALGORITHM:

See sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.

Note

The face lattice is not cached, as long as this creates a memory leak, see Issue #28982.

EXAMPLES:

Sage

sage: square = polytopes.hypercube(2)
sage: fl = square.face_lattice();fl
Finite lattice containing 10 elements
sage: list(f.ambient_V_indices() for f in fl)
[(), (0,), (1,), (0, 1), (2,), (1, 2), (3,), (0, 3), (2, 3), (0, 1, 2, 3)]
sage: poset_element = fl[5]
sage: a_face = poset_element
sage: a_face
A 1-dimensional face of a Polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: a_face.ambient_V_indices()
(1, 2)
sage: set(a_face.ambient_Vrepresentation()) ==             ....: set([square.Vrepresentation(1), square.Vrepresentation(2)])
True
sage: a_face.ambient_Vrepresentation()
(A vertex at (1, 1), A vertex at (-1, 1))
sage: a_face.ambient_Hrepresentation()
(An inequality (0, -1) x + 1 >= 0,)

Python

>>> from sage.all import *
>>> square = polytopes.hypercube(Integer(2))
>>> fl = square.face_lattice();fl
Finite lattice containing 10 elements
>>> list(f.ambient_V_indices() for f in fl)
[(), (0,), (1,), (0, 1), (2,), (1, 2), (3,), (0, 3), (2, 3), (0, 1, 2, 3)]
>>> poset_element = fl[Integer(5)]
>>> a_face = poset_element
>>> a_face
A 1-dimensional face of a Polyhedron in ZZ^2 defined as the convex hull of 2 vertices
>>> a_face.ambient_V_indices()
(1, 2)
>>> set(a_face.ambient_Vrepresentation()) ==             Ellipsis.: set([square.Vrepresentation(Integer(1)), square.Vrepresentation(Integer(2))])
True
>>> a_face.ambient_Vrepresentation()
(A vertex at (1, 1), A vertex at (-1, 1))
>>> a_face.ambient_Hrepresentation()
(An inequality (0, -1) x + 1 >= 0,)

Sage Live

square = polytopes.hypercube(2)
fl = square.face_lattice();fl
list(f.ambient_V_indices() for f in fl)
poset_element = fl[5]
a_face = poset_element
a_face
a_face.ambient_V_indices()
set(a_face.ambient_Vrepresentation()) ==             ....: set([square.Vrepresentation(1), square.Vrepresentation(2)])
a_face.ambient_Vrepresentation()
a_face.ambient_Hrepresentation()

A more complicated example:

Sage

sage: c5_10 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5] for i in range(1,11)])
sage: c5_10_fl = c5_10.face_lattice()
sage: [len(x) for x in c5_10_fl.level_sets()]
[1, 10, 45, 100, 105, 42, 1]

Python

>>> from sage.all import *
>>> c5_10 = Polyhedron(vertices = [[i,i**Integer(2),i**Integer(3),i**Integer(4),i**Integer(5)] for i in range(Integer(1),Integer(11))])
>>> c5_10_fl = c5_10.face_lattice()
>>> [len(x) for x in c5_10_fl.level_sets()]
[1, 10, 45, 100, 105, 42, 1]

Sage Live

c5_10 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5] for i in range(1,11)])
c5_10_fl = c5_10.face_lattice()
[len(x) for x in c5_10_fl.level_sets()]

Note that if the polyhedron contains lines then there is a dimension gap between the empty face and the first non-empty face in the face lattice:

Sage

sage: line = Polyhedron(vertices=[(0,)], lines=[(1,)])
sage: [ fl.dim() for fl in line.face_lattice() ]
[-1, 1]

Python

>>> from sage.all import *
>>> line = Polyhedron(vertices=[(Integer(0),)], lines=[(Integer(1),)])
>>> [ fl.dim() for fl in line.face_lattice() ]
[-1, 1]

Sage Live

line = Polyhedron(vertices=[(0,)], lines=[(1,)])
[ fl.dim() for fl in line.face_lattice() ]

flag_f_vector(*args)[source]¶

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 – integer (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

sage: P = polytopes.twenty_four_cell()
sage: P.flag_f_vector()
    {(-1,): 1,
     (0,): 24,
     (0, 1): 192,
     (0, 1, 2): 576,
     (0, 1, 2, 3): 1152,
     (0, 1, 3): 576,
     (0, 2): 288,
     (0, 2, 3): 576,
     (0, 3): 144,
     (1,): 96,
     (1, 2): 288,
     (1, 2, 3): 576,
     (1, 3): 288,
     (2,): 96,
     (2, 3): 192,
     (3,): 24,
     (4,): 1}

Python

>>> from sage.all import *
>>> P = polytopes.twenty_four_cell()
>>> P.flag_f_vector()
    {(-1,): 1,
     (0,): 24,
     (0, 1): 192,
     (0, 1, 2): 576,
     (0, 1, 2, 3): 1152,
     (0, 1, 3): 576,
     (0, 2): 288,
     (0, 2, 3): 576,
     (0, 3): 144,
     (1,): 96,
     (1, 2): 288,
     (1, 2, 3): 576,
     (1, 3): 288,
     (2,): 96,
     (2, 3): 192,
     (3,): 24,
     (4,): 1}

Sage Live

P = polytopes.twenty_four_cell()
P.flag_f_vector()

Specify an entry:

Sage

sage: P.flag_f_vector(0,3)
144
sage: P.flag_f_vector(2)
96

Python

>>> from sage.all import *
>>> P.flag_f_vector(Integer(0),Integer(3))
144
>>> P.flag_f_vector(Integer(2))
96

Sage Live

P.flag_f_vector(0,3)
P.flag_f_vector(2)

Leading -1 and trailing entry of dimension are allowed:

Sage

sage: P.flag_f_vector(-1,0,3)
144
sage: P.flag_f_vector(-1,0,3,4)
144

Python

>>> from sage.all import *
>>> P.flag_f_vector(-Integer(1),Integer(0),Integer(3))
144
>>> P.flag_f_vector(-Integer(1),Integer(0),Integer(3),Integer(4))
144

Sage Live

P.flag_f_vector(-1,0,3)
P.flag_f_vector(-1,0,3,4)

One can get the number of trivial faces:

Sage

sage: P.flag_f_vector(-1)
1
sage: P.flag_f_vector(4)
1

Python

>>> from sage.all import *
>>> P.flag_f_vector(-Integer(1))
1
>>> P.flag_f_vector(Integer(4))
1

Sage Live

P.flag_f_vector(-1)
P.flag_f_vector(4)

Polyhedra with lines, have 0 entries accordingly:

Sage

sage: P = (Polyhedron(lines=[[1]]) * polytopes.cross_polytope(3))
sage: P.flag_f_vector()
{(-1,): 1,
 (0, 1): 0,
 (0, 1, 2): 0,
 (0, 1, 3): 0,
 (0, 2): 0,
 (0, 2, 3): 0,
 (0, 3): 0,
 (0,): 0,
 (1, 2): 24,
 (1, 2, 3): 48,
 (1, 3): 24,
 (1,): 6,
 (2, 3): 24,
 (2,): 12,
 (3,): 8,
 4: 1}

Python

>>> from sage.all import *
>>> P = (Polyhedron(lines=[[Integer(1)]]) * polytopes.cross_polytope(Integer(3)))
>>> P.flag_f_vector()
{(-1,): 1,
 (0, 1): 0,
 (0, 1, 2): 0,
 (0, 1, 3): 0,
 (0, 2): 0,
 (0, 2, 3): 0,
 (0, 3): 0,
 (0,): 0,
 (1, 2): 24,
 (1, 2, 3): 48,
 (1, 3): 24,
 (1,): 6,
 (2, 3): 24,
 (2,): 12,
 (3,): 8,
 4: 1}

Sage Live

P = (Polyhedron(lines=[[1]]) * polytopes.cross_polytope(3))
P.flag_f_vector()

If the arguments are not stricly increasing or out of range, a key error is raised:

Sage

sage: P.flag_f_vector(-1,0,3,6)
Traceback (most recent call last):
...
KeyError: (0, 3, 6)
sage: P.flag_f_vector(-1,3,0)
Traceback (most recent call last):
...
KeyError: (3, 0)

Python

>>> from sage.all import *
>>> P.flag_f_vector(-Integer(1),Integer(0),Integer(3),Integer(6))
Traceback (most recent call last):
...
KeyError: (0, 3, 6)
>>> P.flag_f_vector(-Integer(1),Integer(3),Integer(0))
Traceback (most recent call last):
...
KeyError: (3, 0)

Sage Live

P.flag_f_vector(-1,0,3,6)
P.flag_f_vector(-1,3,0)

graph(**kwds)[source]¶

Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.

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

Note

The graph of a polyhedron with lines has no vertices, as the polyhedron has no vertices (\(0\)-faces).

The method vertices() returns the defining points in this case.

EXAMPLES:

Sage

sage: g3 = polytopes.hypercube(3).vertex_graph(); g3
Graph on 8 vertices
sage: g3.automorphism_group().cardinality()                                             # needs sage.groups
48
sage: s4 = polytopes.simplex(4).vertex_graph(); s4
Graph on 5 vertices
sage: s4.is_eulerian()
True

Python

>>> from sage.all import *
>>> g3 = polytopes.hypercube(Integer(3)).vertex_graph(); g3
Graph on 8 vertices
>>> g3.automorphism_group().cardinality()                                             # needs sage.groups
48
>>> s4 = polytopes.simplex(Integer(4)).vertex_graph(); s4
Graph on 5 vertices
>>> s4.is_eulerian()
True

Sage Live

g3 = polytopes.hypercube(3).vertex_graph(); g3
g3.automorphism_group().cardinality()                                             # needs sage.groups
s4 = polytopes.simplex(4).vertex_graph(); s4
s4.is_eulerian()

The graph of an unbounded polyhedron is the graph of the bounded complex:

Sage

sage: open_triangle = Polyhedron(vertices=[[1,0], [0,1]],
....:                            rays    =[[1,1]])
sage: open_triangle.vertex_graph()
Graph on 2 vertices

Python

>>> from sage.all import *
>>> open_triangle = Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]],
...                            rays    =[[Integer(1),Integer(1)]])
>>> open_triangle.vertex_graph()
Graph on 2 vertices

Sage Live

open_triangle = Polyhedron(vertices=[[1,0], [0,1]],
                           rays    =[[1,1]])
open_triangle.vertex_graph()

The graph of a polyhedron with lines has no vertices:

Sage

sage: line = Polyhedron(lines=[[0,1]])
sage: line.vertex_graph()
Graph on 0 vertices

Python

>>> from sage.all import *
>>> line = Polyhedron(lines=[[Integer(0),Integer(1)]])
>>> line.vertex_graph()
Graph on 0 vertices

Sage Live

line = Polyhedron(lines=[[0,1]])
line.vertex_graph()

hasse_diagram()[source]¶

Return the Hasse diagram of the face lattice of self.

This is the Hasse diagram of the poset of the faces of self.

OUTPUT: a directed graph

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: P = polytopes.regular_polygon(4).pyramid()
sage: D = P.hasse_diagram(); D
Digraph on 20 vertices
sage: D.degree_polynomial()
x^5 + x^4*y + x*y^4 + y^5 + 4*x^3*y + 8*x^2*y^2 + 4*x*y^3

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = polytopes.regular_polygon(Integer(4)).pyramid()
>>> D = P.hasse_diagram(); D
Digraph on 20 vertices
>>> D.degree_polynomial()
x^5 + x^4*y + x*y^4 + y^5 + 4*x^3*y + 8*x^2*y^2 + 4*x*y^3

Sage Live

# needs sage.rings.number_field
P = polytopes.regular_polygon(4).pyramid()
D = P.hasse_diagram(); D
D.degree_polynomial()

Faces of a mutable polyhedron are not hashable. Hence those are not suitable as vertices of the hasse diagram. Use the combinatorial polyhedron instead:

Sage

sage: # needs sage.rings.number_field
sage: P = polytopes.regular_polygon(4).pyramid()
sage: parent = P.parent()
sage: parent = parent.change_ring(QQ, backend='ppl')
sage: Q = parent._element_constructor_(P, mutable=True)
sage: Q.hasse_diagram()
Traceback (most recent call last):
...
TypeError: mutable polyhedra are unhashable
sage: C = Q.combinatorial_polyhedron()
sage: D = C.hasse_diagram()
sage: set(D.vertices(sort=False)) == set(range(20))
True
sage: def index_to_combinatorial_face(n):
....:     return C.face_by_face_lattice_index(n)
sage: D.relabel(index_to_combinatorial_face, inplace=True)
sage: D.vertices(sort=True)
[A -1-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,
 A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-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,
 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 3-dimensional face of a 3-dimensional combinatorial polyhedron]
sage: D.degree_polynomial()
x^5 + x^4*y + x*y^4 + y^5 + 4*x^3*y + 8*x^2*y^2 + 4*x*y^3

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = polytopes.regular_polygon(Integer(4)).pyramid()
>>> parent = P.parent()
>>> parent = parent.change_ring(QQ, backend='ppl')
>>> Q = parent._element_constructor_(P, mutable=True)
>>> Q.hasse_diagram()
Traceback (most recent call last):
...
TypeError: mutable polyhedra are unhashable
>>> C = Q.combinatorial_polyhedron()
>>> D = C.hasse_diagram()
>>> set(D.vertices(sort=False)) == set(range(Integer(20)))
True
>>> def index_to_combinatorial_face(n):
...     return C.face_by_face_lattice_index(n)
>>> D.relabel(index_to_combinatorial_face, inplace=True)
>>> D.vertices(sort=True)
[A -1-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,
 A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-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,
 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 3-dimensional face of a 3-dimensional combinatorial polyhedron]
>>> D.degree_polynomial()
x^5 + x^4*y + x*y^4 + y^5 + 4*x^3*y + 8*x^2*y^2 + 4*x*y^3

Sage Live

# needs sage.rings.number_field
P = polytopes.regular_polygon(4).pyramid()
parent = P.parent()
parent = parent.change_ring(QQ, backend='ppl')
Q = parent._element_constructor_(P, mutable=True)
Q.hasse_diagram()
C = Q.combinatorial_polyhedron()
D = C.hasse_diagram()
set(D.vertices(sort=False)) == set(range(20))
def index_to_combinatorial_face(n):
    return C.face_by_face_lattice_index(n)
D.relabel(index_to_combinatorial_face, inplace=True)
D.vertices(sort=True)
D.degree_polynomial()

is_combinatorially_isomorphic(other, algorithm='bipartite_graph')[source]¶

Return whether the polyhedron is combinatorially isomorphic to another polyhedron.

We only consider bounded polyhedra. By definition, they are combinatorially isomorphic if their face lattices are isomorphic.

INPUT:

other – a polyhedron object
algorithm – (default: 'bipartite_graph') the algorithm to use; the other possible value is 'face_lattice'

OUTPUT:

True if the two polyhedra are combinatorially isomorphic
False otherwise

REFERENCES:

For the equivalence of the two algorithms see [KK1995], p. 877-878

EXAMPLES:

The square is combinatorially isomorphic to the 2-dimensional cube:

Sage

sage: polytopes.hypercube(2).is_combinatorially_isomorphic(polytopes.regular_polygon(4))
True

Python

>>> from sage.all import *
>>> polytopes.hypercube(Integer(2)).is_combinatorially_isomorphic(polytopes.regular_polygon(Integer(4)))
True

Sage Live

polytopes.hypercube(2).is_combinatorially_isomorphic(polytopes.regular_polygon(4))

All the faces of the 3-dimensional permutahedron are either combinatorially isomorphic to a square or a hexagon:

Sage

sage: H = polytopes.regular_polygon(6)                                      # needs sage.rings.number_field
sage: S = polytopes.hypercube(2)
sage: P = polytopes.permutahedron(4)
sage: all(F.as_polyhedron().is_combinatorially_isomorphic(S)                # needs sage.rings.number_field
....:       or F.as_polyhedron().is_combinatorially_isomorphic(H)
....:     for F in P.faces(2))
True

Python

>>> from sage.all import *
>>> H = polytopes.regular_polygon(Integer(6))                                      # needs sage.rings.number_field
>>> S = polytopes.hypercube(Integer(2))
>>> P = polytopes.permutahedron(Integer(4))
>>> all(F.as_polyhedron().is_combinatorially_isomorphic(S)                # needs sage.rings.number_field
...       or F.as_polyhedron().is_combinatorially_isomorphic(H)
...     for F in P.faces(Integer(2)))
True

Sage Live

H = polytopes.regular_polygon(6)                                      # needs sage.rings.number_field
S = polytopes.hypercube(2)
P = polytopes.permutahedron(4)
all(F.as_polyhedron().is_combinatorially_isomorphic(S)                # needs sage.rings.number_field
      or F.as_polyhedron().is_combinatorially_isomorphic(H)
    for F in P.faces(2))

Checking that a regular simplex intersected with its reflection through the origin is combinatorially isomorphic to the intersection of a cube with a hyperplane perpendicular to its long diagonal:

Sage

sage: def simplex_intersection(k):
....:   S1 = Polyhedron([vector(v)-vector(polytopes.simplex(k).center()) for v in polytopes.simplex(k).vertices_list()])
....:   S2 = Polyhedron([-vector(v) for v in S1.vertices_list()])
....:   return S1.intersection(S2)
sage: def cube_intersection(k):
....:    C = polytopes.hypercube(k+1)
....:    H = Polyhedron(eqns=[[0]+[1 for i in range(k+1)]])
....:    return C.intersection(H)
sage: [simplex_intersection(k).is_combinatorially_isomorphic(cube_intersection(k)) for k in range(2,5)]
[True, True, True]
sage: simplex_intersection(2).is_combinatorially_isomorphic(polytopes.regular_polygon(6))                   # needs sage.rings.number_field
True
sage: simplex_intersection(3).is_combinatorially_isomorphic(polytopes.octahedron())
True

Python

>>> from sage.all import *
>>> def simplex_intersection(k):
...   S1 = Polyhedron([vector(v)-vector(polytopes.simplex(k).center()) for v in polytopes.simplex(k).vertices_list()])
...   S2 = Polyhedron([-vector(v) for v in S1.vertices_list()])
...   return S1.intersection(S2)
>>> def cube_intersection(k):
...    C = polytopes.hypercube(k+Integer(1))
...    H = Polyhedron(eqns=[[Integer(0)]+[Integer(1) for i in range(k+Integer(1))]])
...    return C.intersection(H)
>>> [simplex_intersection(k).is_combinatorially_isomorphic(cube_intersection(k)) for k in range(Integer(2),Integer(5))]
[True, True, True]
>>> simplex_intersection(Integer(2)).is_combinatorially_isomorphic(polytopes.regular_polygon(Integer(6)))                   # needs sage.rings.number_field
True
>>> simplex_intersection(Integer(3)).is_combinatorially_isomorphic(polytopes.octahedron())
True

Sage Live

def simplex_intersection(k):
  S1 = Polyhedron([vector(v)-vector(polytopes.simplex(k).center()) for v in polytopes.simplex(k).vertices_list()])
  S2 = Polyhedron([-vector(v) for v in S1.vertices_list()])
  return S1.intersection(S2)
def cube_intersection(k):
   C = polytopes.hypercube(k+1)
   H = Polyhedron(eqns=[[0]+[1 for i in range(k+1)]])
   return C.intersection(H)
[simplex_intersection(k).is_combinatorially_isomorphic(cube_intersection(k)) for k in range(2,5)]
simplex_intersection(2).is_combinatorially_isomorphic(polytopes.regular_polygon(6))                   # needs sage.rings.number_field
simplex_intersection(3).is_combinatorially_isomorphic(polytopes.octahedron())

Two polytopes with the same \(f\)-vector, but different combinatorial types:

Sage

sage: P = Polyhedron([[-605520/1525633, -605520/1525633, -1261500/1525633, -52200/1525633, 11833/1525633],\
 [-720/1769, -600/1769, 1500/1769, 0, -31/1769], [-216/749, 240/749, -240/749, -432/749, 461/749], \
 [-50/181, 50/181, 60/181, -100/181, -119/181], [-32/51, -16/51, -4/51, 12/17, 1/17],\
 [1, 0, 0, 0, 0], [16/129, 128/129, 0, 0, 1/129], [64/267, -128/267, 24/89, -128/267, 57/89],\
 [1200/3953, -1200/3953, -1440/3953, -360/3953, -3247/3953], [1512/5597, 1512/5597, 588/5597, 4704/5597, 2069/5597]])
sage: C = polytopes.cyclic_polytope(5,10)
sage: C.f_vector() == P.f_vector(); C.f_vector()
True
(1, 10, 45, 100, 105, 42, 1)
sage: C.is_combinatorially_isomorphic(P)
False

sage: S = polytopes.simplex(3)
sage: S = S.face_truncation(S.faces(0)[3])
sage: S = S.face_truncation(S.faces(0)[4])
sage: S = S.face_truncation(S.faces(0)[5])
sage: T = polytopes.simplex(3)
sage: T = T.face_truncation(T.faces(0)[3])
sage: T = T.face_truncation(T.faces(0)[4])
sage: T = T.face_truncation(T.faces(0)[4])
sage: T.is_combinatorially_isomorphic(S)
False
sage: T.f_vector(), S.f_vector()
((1, 10, 15, 7, 1), (1, 10, 15, 7, 1))

sage: C = polytopes.hypercube(5)
sage: C.is_combinatorially_isomorphic(C)
True
sage: C.is_combinatorially_isomorphic(C, algorithm='magic')
Traceback (most recent call last):
...
AssertionError: `algorithm` must be 'bipartite graph' or 'face_lattice'

sage: G = Graph()
sage: C.is_combinatorially_isomorphic(G)
Traceback (most recent call last):
...
AssertionError: input `other` must be a polyhedron

sage: H = Polyhedron(eqns=[[0,1,1,1,1]]); H
A 3-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex and 3 lines
sage: C.is_combinatorially_isomorphic(H)
Traceback (most recent call last):
...
AssertionError: polyhedron `other` must be bounded

Python

>>> from sage.all import *
>>> P = Polyhedron([[-Integer(605520)/Integer(1525633), -Integer(605520)/Integer(1525633), -Integer(1261500)/Integer(1525633), -Integer(52200)/Integer(1525633), Integer(11833)/Integer(1525633)],\
 [-720/1769, -600/1769, 1500/1769, 0, -31/1769], [-216/749, 240/749, -240/749, -432/749, 461/749], \
 [-50/181, 50/181, 60/181, -100/181, -119/181], [-32/51, -16/51, -4/51, 12/17, 1/17],\
 [1, 0, 0, 0, 0], [16/129, 128/129, 0, 0, 1/129], [64/267, -128/267, 24/89, -128/267, 57/89],\
 [1200/3953, -1200/3953, -1440/3953, -360/3953, -3247/3953], [1512/5597, 1512/5597, 588/5597, 4704/5597, 2069/5597]])
>>> C = polytopes.cyclic_polytope(Integer(5),Integer(10))
>>> C.f_vector() == P.f_vector(); C.f_vector()
True
(1, 10, 45, 100, 105, 42, 1)
>>> C.is_combinatorially_isomorphic(P)
False

>>> S = polytopes.simplex(Integer(3))
>>> S = S.face_truncation(S.faces(Integer(0))[Integer(3)])
>>> S = S.face_truncation(S.faces(Integer(0))[Integer(4)])
>>> S = S.face_truncation(S.faces(Integer(0))[Integer(5)])
>>> T = polytopes.simplex(Integer(3))
>>> T = T.face_truncation(T.faces(Integer(0))[Integer(3)])
>>> T = T.face_truncation(T.faces(Integer(0))[Integer(4)])
>>> T = T.face_truncation(T.faces(Integer(0))[Integer(4)])
>>> T.is_combinatorially_isomorphic(S)
False
>>> T.f_vector(), S.f_vector()
((1, 10, 15, 7, 1), (1, 10, 15, 7, 1))

>>> C = polytopes.hypercube(Integer(5))
>>> C.is_combinatorially_isomorphic(C)
True
>>> C.is_combinatorially_isomorphic(C, algorithm='magic')
Traceback (most recent call last):
...
AssertionError: `algorithm` must be 'bipartite graph' or 'face_lattice'

>>> G = Graph()
>>> C.is_combinatorially_isomorphic(G)
Traceback (most recent call last):
...
AssertionError: input `other` must be a polyhedron

>>> H = Polyhedron(eqns=[[Integer(0),Integer(1),Integer(1),Integer(1),Integer(1)]]); H
A 3-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex and 3 lines
>>> C.is_combinatorially_isomorphic(H)
Traceback (most recent call last):
...
AssertionError: polyhedron `other` must be bounded

Sage Live

P = Polyhedron([[-605520/1525633, -605520/1525633, -1261500/1525633, -52200/1525633, 11833/1525633],\
C = polytopes.cyclic_polytope(5,10)
C.f_vector() == P.f_vector(); C.f_vector()
C.is_combinatorially_isomorphic(P)
S = polytopes.simplex(3)
S = S.face_truncation(S.faces(0)[3])
S = S.face_truncation(S.faces(0)[4])
S = S.face_truncation(S.faces(0)[5])
T = polytopes.simplex(3)
T = T.face_truncation(T.faces(0)[3])
T = T.face_truncation(T.faces(0)[4])
T = T.face_truncation(T.faces(0)[4])
T.is_combinatorially_isomorphic(S)
T.f_vector(), S.f_vector()
C = polytopes.hypercube(5)
C.is_combinatorially_isomorphic(C)
C.is_combinatorially_isomorphic(C, algorithm='magic')
G = Graph()
C.is_combinatorially_isomorphic(G)
H = Polyhedron(eqns=[[0,1,1,1,1]]); H
C.is_combinatorially_isomorphic(H)

is_self_dual()[source]¶

Return whether the polytope is self-dual.

A polytope is self-dual if its face lattice is isomorphic to the face lattice of its dual polytope.

EXAMPLES:

Sage

sage: polytopes.simplex().is_self_dual()
True
sage: polytopes.twenty_four_cell().is_self_dual()
True
sage: polytopes.cube().is_self_dual()
False
sage: polytopes.hypersimplex(5,2).is_self_dual()                            # needs sage.combinat
False
sage: P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]]).is_self_dual()
Traceback (most recent call last):
...
ValueError: polyhedron has to be compact

Python

>>> from sage.all import *
>>> polytopes.simplex().is_self_dual()
True
>>> polytopes.twenty_four_cell().is_self_dual()
True
>>> polytopes.cube().is_self_dual()
False
>>> polytopes.hypersimplex(Integer(5),Integer(2)).is_self_dual()                            # needs sage.combinat
False
>>> P = Polyhedron(vertices=[[Integer(1)/Integer(2), Integer(1)/Integer(3)]], rays=[[Integer(1), Integer(1)]]).is_self_dual()
Traceback (most recent call last):
...
ValueError: polyhedron has to be compact

Sage Live

polytopes.simplex().is_self_dual()
polytopes.twenty_four_cell().is_self_dual()
polytopes.cube().is_self_dual()
polytopes.hypersimplex(5,2).is_self_dual()                            # needs sage.combinat
P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]]).is_self_dual()

restricted_automorphism_group(output='abstract')[source]¶

Return the restricted automorphism group.

First, let the linear automorphism group be the subgroup of the affine group \(AGL(d,\RR) = GL(d,\RR) \ltimes \RR^d\) preserving the \(d\)-dimensional polyhedron. The affine group acts in the usual way \(\vec{x}\mapsto A\vec{x}+b\) on the ambient space.

The restricted automorphism group is the subgroup of the linear automorphism group generated by permutations of the generators of the same type. That is, vertices can only be permuted with vertices, ray generators with ray generators, and line generators with line generators.

For example, take the first quadrant

\[Q = \Big\{ (x,y) \Big| x\geq 0,\; y\geq0 \Big\} \subset \QQ^2\]

Then the linear automorphism group is

\[\begin{split}\mathrm{Aut}(Q) = \left\{ \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} ,~ \begin{pmatrix} 0 & c \\ d & 0 \end{pmatrix} :~ a, b, c, d \in \QQ_{>0} \right\} \subset GL(2,\QQ) \subset E(d)\end{split}\]

Note that there are no translations that map the quadrant \(Q\) to itself, so the linear automorphism group is contained in the general linear group (the subgroup of transformations preserving the origin). The restricted automorphism group is

\[\begin{split}\mathrm{Aut}(Q) = \left\{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} ,~ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \right\} \simeq \ZZ_2\end{split}\]

INPUT:

output – how the group should be represented:
- 'abstract' – default; return an abstract permutation group without further meaning
- 'permutation' – return a permutation group on the indices of the polyhedron generators. For example, the permutation (0,1) would correspond to swapping self.Vrepresentation(0) and self.Vrepresentation(1).
- 'matrix' – return a matrix group representing affine transformations. When acting on affine vectors, you should append a \(1\) to every vector. If the polyhedron is not full dimensional, the returned matrices act as the identity on the orthogonal complement of the affine space spanned by the polyhedron.
- 'matrixlist' – like matrix, but return the list of elements of the matrix group. Useful for fields without a good implementation of matrix groups or to avoid the overhead of creating the group.

OUTPUT:

For output="abstract" and output="permutation": a PermutationGroup.
For output="matrix": a MatrixGroup().
For output="matrixlist": a list of matrices.

REFERENCES:

[BSS2009]

EXAMPLES:

A cross-polytope example:

Sage

sage: # needs sage.groups
sage: P = polytopes.cross_polytope(3)
sage: P.restricted_automorphism_group() == PermutationGroup([[(3,4)], [(2,3),(4,5)],[(2,5)],[(1,2),(5,6)],[(1,6)]])
True
sage: P.restricted_automorphism_group(output='permutation') == PermutationGroup([[(2,3)],[(1,2),(3,4)],[(1,4)],[(0,1),(4,5)],[(0,5)]])
True
sage: mgens = [[[1,0,0,0],[0,1,0,0],[0,0,-1,0],[0,0,0,1]], [[1,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,1]], [[0,1,0,0],[1,0,0,0],[0,0,1,0],[0,0,0,1]]]

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> P = polytopes.cross_polytope(Integer(3))
>>> P.restricted_automorphism_group() == PermutationGroup([[(Integer(3),Integer(4))], [(Integer(2),Integer(3)),(Integer(4),Integer(5))],[(Integer(2),Integer(5))],[(Integer(1),Integer(2)),(Integer(5),Integer(6))],[(Integer(1),Integer(6))]])
True
>>> P.restricted_automorphism_group(output='permutation') == PermutationGroup([[(Integer(2),Integer(3))],[(Integer(1),Integer(2)),(Integer(3),Integer(4))],[(Integer(1),Integer(4))],[(Integer(0),Integer(1)),(Integer(4),Integer(5))],[(Integer(0),Integer(5))]])
True
>>> mgens = [[[Integer(1),Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(0),-Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(0),Integer(1)]], [[Integer(1),Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(0),Integer(0),Integer(1)]], [[Integer(0),Integer(1),Integer(0),Integer(0)],[Integer(1),Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(0),Integer(1)]]]

Sage Live

# needs sage.groups
P = polytopes.cross_polytope(3)
P.restricted_automorphism_group() == PermutationGroup([[(3,4)], [(2,3),(4,5)],[(2,5)],[(1,2),(5,6)],[(1,6)]])
P.restricted_automorphism_group(output='permutation') == PermutationGroup([[(2,3)],[(1,2),(3,4)],[(1,4)],[(0,1),(4,5)],[(0,5)]])
mgens = [[[1,0,0,0],[0,1,0,0],[0,0,-1,0],[0,0,0,1]], [[1,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,1]], [[0,1,0,0],[1,0,0,0],[0,0,1,0],[0,0,0,1]]]

We test groups for equality in a fool-proof way; they can have different generators, etc:

Sage

sage: # needs sage.groups
sage: poly_g = P.restricted_automorphism_group(output='matrix')
sage: matrix_g = MatrixGroup([matrix(QQ,t) for t in mgens])
sage: all(t.matrix() in poly_g for t in matrix_g.gens())
True
sage: all(t.matrix() in matrix_g for t in poly_g.gens())
True

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> poly_g = P.restricted_automorphism_group(output='matrix')
>>> matrix_g = MatrixGroup([matrix(QQ,t) for t in mgens])
>>> all(t.matrix() in poly_g for t in matrix_g.gens())
True
>>> all(t.matrix() in matrix_g for t in poly_g.gens())
True

Sage Live

# needs sage.groups
poly_g = P.restricted_automorphism_group(output='matrix')
matrix_g = MatrixGroup([matrix(QQ,t) for t in mgens])
all(t.matrix() in poly_g for t in matrix_g.gens())
all(t.matrix() in matrix_g for t in poly_g.gens())

24-cell example:

Sage

sage: # needs sage.groups
sage: P24 = polytopes.twenty_four_cell()
sage: AutP24 = P24.restricted_automorphism_group()
sage: PermutationGroup([
....:     '(1,20,2,24,5,23)(3,18,10,19,4,14)(6,21,11,22,7,15)(8,12,16,17,13,9)',
....:     '(1,21,8,24,4,17)(2,11,6,15,9,13)(3,20)(5,22)(10,16,12,23,14,19)'
....: ]).is_isomorphic(AutP24)
True
sage: AutP24.order()
1152

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> P24 = polytopes.twenty_four_cell()
>>> AutP24 = P24.restricted_automorphism_group()
>>> PermutationGroup([
...     '(1,20,2,24,5,23)(3,18,10,19,4,14)(6,21,11,22,7,15)(8,12,16,17,13,9)',
...     '(1,21,8,24,4,17)(2,11,6,15,9,13)(3,20)(5,22)(10,16,12,23,14,19)'
... ]).is_isomorphic(AutP24)
True
>>> AutP24.order()
1152

Sage Live

# needs sage.groups
P24 = polytopes.twenty_four_cell()
AutP24 = P24.restricted_automorphism_group()
PermutationGroup([
    '(1,20,2,24,5,23)(3,18,10,19,4,14)(6,21,11,22,7,15)(8,12,16,17,13,9)',
    '(1,21,8,24,4,17)(2,11,6,15,9,13)(3,20)(5,22)(10,16,12,23,14,19)'
]).is_isomorphic(AutP24)
AutP24.order()

Here is the quadrant example mentioned in the beginning:

Sage

sage: # needs sage.groups
sage: P = Polyhedron(rays=[(1,0),(0,1)])
sage: P.Vrepresentation()
(A vertex at (0, 0), A ray in the direction (0, 1), A ray in the direction (1, 0))
sage: P.restricted_automorphism_group(output='permutation')
Permutation Group with generators [(1,2)]

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> P = Polyhedron(rays=[(Integer(1),Integer(0)),(Integer(0),Integer(1))])
>>> P.Vrepresentation()
(A vertex at (0, 0), A ray in the direction (0, 1), A ray in the direction (1, 0))
>>> P.restricted_automorphism_group(output='permutation')
Permutation Group with generators [(1,2)]

Sage Live

# needs sage.groups
P = Polyhedron(rays=[(1,0),(0,1)])
P.Vrepresentation()
P.restricted_automorphism_group(output='permutation')

Also, the polyhedron need not be full-dimensional:

Sage

sage: # needs sage.groups
sage: P = Polyhedron(vertices=[(1,2,3,4,5),(7,8,9,10,11)])
sage: P.restricted_automorphism_group()
Permutation Group with generators [(1,2)]
sage: G = P.restricted_automorphism_group(output='matrixlist'); G
(
[1 0 0 0 0 0]  [ -87/55  -82/55    -2/5   38/55   98/55   12/11]
[0 1 0 0 0 0]  [-142/55  -27/55    -2/5   38/55   98/55   12/11]
[0 0 1 0 0 0]  [-142/55  -82/55     3/5   38/55   98/55   12/11]
[0 0 0 1 0 0]  [-142/55  -82/55    -2/5   93/55   98/55   12/11]
[0 0 0 0 1 0]  [-142/55  -82/55    -2/5   38/55  153/55   12/11]
[0 0 0 0 0 1], [      0       0       0       0       0       1]
)
sage: g = AffineGroup(5, QQ)(G[1]); g
      [ -87/55  -82/55    -2/5   38/55   98/55]     [12/11]
      [-142/55  -27/55    -2/5   38/55   98/55]     [12/11]
x |-> [-142/55  -82/55     3/5   38/55   98/55] x + [12/11]
      [-142/55  -82/55    -2/5   93/55   98/55]     [12/11]
      [-142/55  -82/55    -2/5   38/55  153/55]     [12/11]
sage: g^2
      [1 0 0 0 0]     [0]
      [0 1 0 0 0]     [0]
x |-> [0 0 1 0 0] x + [0]
      [0 0 0 1 0]     [0]
      [0 0 0 0 1]     [0]
sage: g(list(P.vertices()[0]))
(7, 8, 9, 10, 11)
sage: g(list(P.vertices()[1]))
(1, 2, 3, 4, 5)

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> P = Polyhedron(vertices=[(Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)),(Integer(7),Integer(8),Integer(9),Integer(10),Integer(11))])
>>> P.restricted_automorphism_group()
Permutation Group with generators [(1,2)]
>>> G = P.restricted_automorphism_group(output='matrixlist'); G
(
[1 0 0 0 0 0]  [ -87/55  -82/55    -2/5   38/55   98/55   12/11]
[0 1 0 0 0 0]  [-142/55  -27/55    -2/5   38/55   98/55   12/11]
[0 0 1 0 0 0]  [-142/55  -82/55     3/5   38/55   98/55   12/11]
[0 0 0 1 0 0]  [-142/55  -82/55    -2/5   93/55   98/55   12/11]
[0 0 0 0 1 0]  [-142/55  -82/55    -2/5   38/55  153/55   12/11]
[0 0 0 0 0 1], [      0       0       0       0       0       1]
)
>>> g = AffineGroup(Integer(5), QQ)(G[Integer(1)]); g
      [ -87/55  -82/55    -2/5   38/55   98/55]     [12/11]
      [-142/55  -27/55    -2/5   38/55   98/55]     [12/11]
x |-> [-142/55  -82/55     3/5   38/55   98/55] x + [12/11]
      [-142/55  -82/55    -2/5   93/55   98/55]     [12/11]
      [-142/55  -82/55    -2/5   38/55  153/55]     [12/11]
>>> g**Integer(2)
      [1 0 0 0 0]     [0]
      [0 1 0 0 0]     [0]
x |-> [0 0 1 0 0] x + [0]
      [0 0 0 1 0]     [0]
      [0 0 0 0 1]     [0]
>>> g(list(P.vertices()[Integer(0)]))
(7, 8, 9, 10, 11)
>>> g(list(P.vertices()[Integer(1)]))
(1, 2, 3, 4, 5)

Sage Live

# needs sage.groups
P = Polyhedron(vertices=[(1,2,3,4,5),(7,8,9,10,11)])
P.restricted_automorphism_group()
G = P.restricted_automorphism_group(output='matrixlist'); G
g = AffineGroup(5, QQ)(G[1]); g
g^2
g(list(P.vertices()[0]))
g(list(P.vertices()[1]))

Affine transformations do not change the restricted automorphism group. For example, any non-degenerate triangle has the dihedral group with 6 elements, \(D_6\), as its automorphism group:

Sage

sage: # needs sage.groups
sage: initial_points = [vector([1,0]), vector([0,1]), vector([-2,-1])]
sage: points = initial_points
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - initial_points[0] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - initial_points[1] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - 2*initial_points[1] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> initial_points = [vector([Integer(1),Integer(0)]), vector([Integer(0),Integer(1)]), vector([-Integer(2),-Integer(1)])]
>>> points = initial_points
>>> Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
>>> points = [pt - initial_points[Integer(0)] for pt in initial_points]
>>> Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
>>> points = [pt - initial_points[Integer(1)] for pt in initial_points]
>>> Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
>>> points = [pt - Integer(2)*initial_points[Integer(1)] for pt in initial_points]
>>> Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]

Sage Live

# needs sage.groups
initial_points = [vector([1,0]), vector([0,1]), vector([-2,-1])]
points = initial_points
Polyhedron(vertices=points).restricted_automorphism_group()
points = [pt - initial_points[0] for pt in initial_points]
Polyhedron(vertices=points).restricted_automorphism_group()
points = [pt - initial_points[1] for pt in initial_points]
Polyhedron(vertices=points).restricted_automorphism_group()
points = [pt - 2*initial_points[1] for pt in initial_points]
Polyhedron(vertices=points).restricted_automorphism_group()

The output="matrixlist" can be used over fields without a complete implementation of matrix groups:

Sage

sage: # needs sage.groups sage.rings.number_field
sage: P = polytopes.dodecahedron(); P
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining
 polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 20 vertices
sage: G = P.restricted_automorphism_group(output='matrixlist')
sage: len(G)
120

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.number_field
>>> P = polytopes.dodecahedron(); P
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining
 polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 20 vertices
>>> G = P.restricted_automorphism_group(output='matrixlist')
>>> len(G)
120

Sage Live

# needs sage.groups sage.rings.number_field
P = polytopes.dodecahedron(); P
G = P.restricted_automorphism_group(output='matrixlist')
len(G)

Floating-point computations are supported with a simple fuzzy zero implementation:

Sage

sage: P = Polyhedron(vertices=[(1/3,0,0,1),(0,1/4,0,1),(0,0,1/5,1)],
....:                base_ring=RDF)
sage: P.restricted_automorphism_group()                                     # needs sage.groups
Permutation Group with generators [(2,3), (1,2)]
sage: len(P.restricted_automorphism_group(output='matrixlist'))
6

Python

>>> from sage.all import *
>>> P = Polyhedron(vertices=[(Integer(1)/Integer(3),Integer(0),Integer(0),Integer(1)),(Integer(0),Integer(1)/Integer(4),Integer(0),Integer(1)),(Integer(0),Integer(0),Integer(1)/Integer(5),Integer(1))],
...                base_ring=RDF)
>>> P.restricted_automorphism_group()                                     # needs sage.groups
Permutation Group with generators [(2,3), (1,2)]
>>> len(P.restricted_automorphism_group(output='matrixlist'))
6

Sage Live

P = Polyhedron(vertices=[(1/3,0,0,1),(0,1/4,0,1),(0,0,1/5,1)],
               base_ring=RDF)
P.restricted_automorphism_group()                                     # needs sage.groups
len(P.restricted_automorphism_group(output='matrixlist'))

vertex_digraph(f, increasing=True)[source]¶

Return the directed graph of the polyhedron according to a linear form.

The underlying undirected graph is the graph of vertices and edges.

INPUT:

f – a linear form. The linear form can be provided as:
- a vector space morphism with one-dimensional codomain, (see sage.modules.vector_space_morphism.linear_transformation() and sage.modules.vector_space_morphism.VectorSpaceMorphism)
- a vector ; in this case the linear form is obtained by duality using the dot product: f(v) = v.dot_product(f).
increasing – boolean (default: True); whether to orient edges in the increasing or decreasing direction

By default, an edge is oriented from \(v\) to \(w\) if \(f(v) \leq f(w)\).

If \(f(v)=f(w)\), then two opposite edges are created.

EXAMPLES:

Sage

sage: penta = Polyhedron([[0,0],[1,0],[0,1],[1,2],[3,2]])
sage: G = penta.vertex_digraph(vector([1,1])); G
Digraph on 5 vertices
sage: G.sinks()
[A vertex at (3, 2)]

sage: A = matrix(ZZ, [[1], [-1]])
sage: f = linear_transformation(A)
sage: G = penta.vertex_digraph(f) ; G
Digraph on 5 vertices
sage: G.is_directed_acyclic()
False

Python

>>> from sage.all import *
>>> penta = Polyhedron([[Integer(0),Integer(0)],[Integer(1),Integer(0)],[Integer(0),Integer(1)],[Integer(1),Integer(2)],[Integer(3),Integer(2)]])
>>> G = penta.vertex_digraph(vector([Integer(1),Integer(1)])); G
Digraph on 5 vertices
>>> G.sinks()
[A vertex at (3, 2)]

>>> A = matrix(ZZ, [[Integer(1)], [-Integer(1)]])
>>> f = linear_transformation(A)
>>> G = penta.vertex_digraph(f) ; G
Digraph on 5 vertices
>>> G.is_directed_acyclic()
False

Sage Live

penta = Polyhedron([[0,0],[1,0],[0,1],[1,2],[3,2]])
G = penta.vertex_digraph(vector([1,1])); G
G.sinks()
A = matrix(ZZ, [[1], [-1]])
f = linear_transformation(A)
G = penta.vertex_digraph(f) ; G
G.is_directed_acyclic()

See also

vertex_graph()

vertex_facet_graph(labels=True)[source]¶

Return the vertex-facet graph.

This function constructs a directed bipartite graph. The nodes of the graph correspond to the vertices of the polyhedron and the facets of the polyhedron. There is a directed edge from a vertex to a face if and only if the vertex is incident to the face.

INPUT:

labels – boolean (default: True); decide how the nodes of the graph are labelled. Either with the original vertices/facets of the Polyhedron or with integers.

OUTPUT:

a bipartite DiGraph. If labels is True, then the nodes of the graph will actually be the vertices and facets of self, otherwise they will be integers.

EXAMPLES:

Sage

sage: P = polytopes.cube()
sage: G = P.vertex_facet_graph(); G
Digraph on 14 vertices
sage: G.vertices(sort=True, key=lambda v: str(v))
[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),
 An inequality (-1, 0, 0) x + 1 >= 0,
 An inequality (0, -1, 0) x + 1 >= 0,
 An inequality (0, 0, -1) x + 1 >= 0,
 An inequality (0, 0, 1) x + 1 >= 0,
 An inequality (0, 1, 0) x + 1 >= 0,
 An inequality (1, 0, 0) x + 1 >= 0]
sage: G.automorphism_group().is_isomorphic(P.hasse_diagram().automorphism_group())      # needs sage.groups
True
sage: O = polytopes.octahedron(); O
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices
sage: O.vertex_facet_graph()
Digraph on 14 vertices
sage: H = O.vertex_facet_graph()
sage: G.is_isomorphic(H)                                                                # needs sage.groups
False
sage: G2 = copy(G)
sage: G2.reverse_edges(G2.edges(sort=True))
sage: G2.is_isomorphic(H)                                                               # needs sage.groups
True

Python

>>> from sage.all import *
>>> P = polytopes.cube()
>>> G = P.vertex_facet_graph(); G
Digraph on 14 vertices
>>> G.vertices(sort=True, key=lambda v: str(v))
[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),
 An inequality (-1, 0, 0) x + 1 >= 0,
 An inequality (0, -1, 0) x + 1 >= 0,
 An inequality (0, 0, -1) x + 1 >= 0,
 An inequality (0, 0, 1) x + 1 >= 0,
 An inequality (0, 1, 0) x + 1 >= 0,
 An inequality (1, 0, 0) x + 1 >= 0]
>>> G.automorphism_group().is_isomorphic(P.hasse_diagram().automorphism_group())      # needs sage.groups
True
>>> O = polytopes.octahedron(); O
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices
>>> O.vertex_facet_graph()
Digraph on 14 vertices
>>> H = O.vertex_facet_graph()
>>> G.is_isomorphic(H)                                                                # needs sage.groups
False
>>> G2 = copy(G)
>>> G2.reverse_edges(G2.edges(sort=True))
>>> G2.is_isomorphic(H)                                                               # needs sage.groups
True

Sage Live

P = polytopes.cube()
G = P.vertex_facet_graph(); G
G.vertices(sort=True, key=lambda v: str(v))
G.automorphism_group().is_isomorphic(P.hasse_diagram().automorphism_group())      # needs sage.groups
O = polytopes.octahedron(); O
O.vertex_facet_graph()
H = O.vertex_facet_graph()
G.is_isomorphic(H)                                                                # needs sage.groups
G2 = copy(G)
G2.reverse_edges(G2.edges(sort=True))
G2.is_isomorphic(H)                                                               # needs sage.groups

vertex_graph(**kwds)[source]¶

Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.

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

Note

The graph of a polyhedron with lines has no vertices, as the polyhedron has no vertices (\(0\)-faces).

The method vertices() returns the defining points in this case.

EXAMPLES:

Sage

sage: g3 = polytopes.hypercube(3).vertex_graph(); g3
Graph on 8 vertices
sage: g3.automorphism_group().cardinality()                                             # needs sage.groups
48
sage: s4 = polytopes.simplex(4).vertex_graph(); s4
Graph on 5 vertices
sage: s4.is_eulerian()
True

Python

>>> from sage.all import *
>>> g3 = polytopes.hypercube(Integer(3)).vertex_graph(); g3
Graph on 8 vertices
>>> g3.automorphism_group().cardinality()                                             # needs sage.groups
48
>>> s4 = polytopes.simplex(Integer(4)).vertex_graph(); s4
Graph on 5 vertices
>>> s4.is_eulerian()
True

Sage Live

g3 = polytopes.hypercube(3).vertex_graph(); g3
g3.automorphism_group().cardinality()                                             # needs sage.groups
s4 = polytopes.simplex(4).vertex_graph(); s4
s4.is_eulerian()

The graph of an unbounded polyhedron is the graph of the bounded complex:

Sage

sage: open_triangle = Polyhedron(vertices=[[1,0], [0,1]],
....:                            rays    =[[1,1]])
sage: open_triangle.vertex_graph()
Graph on 2 vertices

Python

>>> from sage.all import *
>>> open_triangle = Polyhedron(vertices=[[Integer(1),Integer(0)], [Integer(0),Integer(1)]],
...                            rays    =[[Integer(1),Integer(1)]])
>>> open_triangle.vertex_graph()
Graph on 2 vertices

Sage Live

open_triangle = Polyhedron(vertices=[[1,0], [0,1]],
                           rays    =[[1,1]])
open_triangle.vertex_graph()

The graph of a polyhedron with lines has no vertices:

Sage

sage: line = Polyhedron(lines=[[0,1]])
sage: line.vertex_graph()
Graph on 0 vertices

Python

>>> from sage.all import *
>>> line = Polyhedron(lines=[[Integer(0),Integer(1)]])
>>> line.vertex_graph()
Graph on 0 vertices

Sage Live

line = Polyhedron(lines=[[0,1]])
line.vertex_graph()