Polytopes in OSCAR

Polymake is state-of-the-art software for all of your discrete geometry needs. Its functionality is partitioned into “applications”. Here are some:

  • polytope (polyhedra)

  • fan (fans)

  • fulton (toric varieties)

  • graph (graphs)

  • group (groups & their actions on polymake objects)

  • matroid (matroids)

  • topaz (topology)

  • tropical (tropical geometry)

Polymake in OSCAR works via the Julia package Polymake.jl. Anything Polymake can do, Polymake.jl can do too.

Note

Syntax for Polymake through Oscar = Syntax for Polymake.jl

(i.e. no polymake objects/functions are in Oscar itself yet)

Visualization note

I am loading Polymake instead of Oscar because there are some issues with visualization through jupyter notebooks right now, and I have a local version which fixes this.

Visualization of Polymake objects through Oscar works just fine in terminal

[1]:
# polymake version 4.2
using Polymake
polymake version 4.2
Copyright (c) 1997-2020
Ewgenij Gawrilow, Michael Joswig, and the polymake team
Technische Universität Berlin, Germany
https://polymake.org

This is free software licensed under GPL; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Some basic aspects of polyhedra

  • Polyhedra are one of the main types of objects in Polymake. Here are some basic things you can do with them.

[2]:
P=Polymake.polytope.cube(3) #create a 3-dimensional cube represented as [-1,1]^3
[2]:
type
Polytope
description
cube of dimension 3
AFFINE_HULL
BOUNDED
true
CONE_AMBIENT_DIM
4
CONE_DIM
4
FACETS
1 1 0 0
1 -1 0 0
1 0 1 0
1 0 -1 0
1 0 0 1
1 0 0 -1
VERTICES_IN_FACETS
{0 2 4 6}
{1 3 5 7}
{0 1 4 5}
{2 3 6 7}
{0 1 2 3}
{4 5 6 7}
[4]:
# There is some issue with visualization in a Juptyer notebook.
#If you are NOT working in a Juptyer notebook, you obtain an interactive 3D-visualization by the command
# Polymake.polytope.visual(P) #visualize the cube
# In a Juptyer notebook use this for a 2D-picture:
Polymake.display_svg(P)
../_images/OSCAR_OscarPolytopes_5_0.svg
polymake: used package SVG
   Generated using the Perl SVG Module
   by Ronan Oger

Polytopes are the convex hull of finitely many points (V-representation). The minimal set of points = “vertices”

Note! Polymake uses homogeneous coordinates.

Think: polytope is embedded one dimension higher at height (first coordinate)=1

or

Think: Polytopes are cones in one dimension higher sliced at (first coordinate)=1

[5]:
P.VERTICES
[5]:
pm::Matrix<pm::Rational>
1 -1 -1 -1
1 1 -1 -1
1 -1 1 -1
1 1 1 -1
1 -1 -1 1
1 1 -1 1
1 -1 1 1
1 1 1 1

Polytopes are also the intersection of finitely many half-spaces (H-representation). Minimal set of halfspaces = “facets”

[6]:
P.FACETS
[6]:
pm::SparseMatrix<pm::Rational, pm::NonSymmetric>
1 1 0 0
1 -1 0 0
1 0 1 0
1 0 -1 0
1 0 0 1
1 0 0 -1

Read first row as

\(1+1\cdot x+0 \cdot y + 0 \cdot z \geq 0\)

[7]:
# Just typing an object usually prints some info about it
P
[7]:
type
Polytope
description
cube of dimension 3
AFFINE_HULL
BOUNDED
true
COMBINATORIAL_DIM
3
CONE_AMBIENT_DIM
4
CONE_DIM
4
DUAL_GRAPH
type: Graph as Polytope::DUAL_GRAPH
FACETS
1 1 0 0
1 -1 0 0
1 0 1 0
1 0 -1 0
1 0 0 1
1 0 0 -1
FEASIBLE
true
GRAPH
type: Graph as Polytope::GRAPH
LINEALITY_DIM
0
LINEALITY_SPACE
NEIGHBOR_FACETS_CYCLIC_NORMAL
2 5 3 4
5 2 4 3
5 0 4 1
0 5 1 4
0 3 1 2
0 2 1 3
N_EDGES
12
POINTED
true
VERTICES
1 -1 -1 -1
1 1 -1 -1
1 -1 1 -1
1 1 1 -1
1 -1 -1 1
1 1 -1 1
1 -1 1 1
1 1 1 1
VERTICES_IN_FACETS
{0 2 4 6}
{1 3 5 7}
{0 1 4 5}
{2 3 6 7}
{0 1 2 3}
{4 5 6 7}
VIF_CYCLIC_NORMAL
0 4 6 2
7 5 1 3
5 4 0 1
2 6 7 3
0 2 3 1
6 4 5 7

Note that we have more properties (fieldnames) on this list than before. Let’s check some of them out!

[8]:
println("Bounded:")
println(P.BOUNDED)

println("\nCone ambient dimension:")
println(P.CONE_AMBIENT_DIM)

println("\nCone dimension:")
println(P.CONE_DIM)

println("\nFacets:")
println(P.FACETS)

println("\nConverting facets to a julia array:")
println(convert(Array{Int64,2},(P.FACETS)))

#Polymake indexes starting at zero.

println("\nVertices in facet incidence:")
println(P.VERTICES_IN_FACETS)

println("Combinatorial dimension:")
println(P.COMBINATORIAL_DIM)
Bounded:
true

Cone ambient dimension:
4

Cone dimension:
4

Facets:
pm::SparseMatrix<pm::Rational, pm::NonSymmetric>
1 1 0 0
1 -1 0 0
1 0 1 0
1 0 -1 0
1 0 0 1
1 0 0 -1


Converting facets to a julia array:
[1 1 0 0; 1 -1 0 0; 1 0 1 0; 1 0 -1 0; 1 0 0 1; 1 0 0 -1]

Vertices in facet incidence:
pm::IncidenceMatrix<pm::NonSymmetric>
{0 2 4 6}
{1 3 5 7}
{0 1 4 5}
{2 3 6 7}
{0 1 2 3}
{4 5 6 7}

Combinatorial dimension:
3
[5]:
# Some fun visualization
P.TRIANGULATION
[5]:
type
GeometricSimplicialComplex as Polytope::TRIANGULATION
FACETS
{0 1 2 4}
{1 2 3 4}
{1 3 4 5}
{2 3 4 6}
{3 4 5 6}
{3 5 6 7}
[6]:
# if not in a Juptyer notebook: Polymake.polytope.visual(P.TRIANGULATION)
Polymake.display_svg(P.TRIANGULATION)
../_images/OSCAR_OscarPolytopes_15_0.svg
[11]:
P.TRIANGULATION.FACETS
[11]:
pm::Array<pm::Set<long, pm::operations::cmp>>
{0 1 2 4}
{1 2 3 4}
{1 3 4 5}
{2 3 4 6}
{3 4 5 6}
{3 5 6 7}

[10]:
# You can subdivide the polytope yourself using a lifting function
A = Polymake.polytope.lattice_points(P)
λ = [1,0,2,1,0,3,3,2,2,1,3,2,4,2,3,1,5,2,0,2,0,3,3,4,2,1,0];
F = Polymake.polytope.regular_subdivision(A, λ)
TT = Polymake.fan.SubdivisionOfPoints(POINTS = A, MAXIMAL_CELLS = F);
# if you are not working in a Jupyter notebook, you can visualize via Polymake.polytope.visual(TT)
Polymake.display_svg(TT)

../_images/OSCAR_OscarPolytopes_17_0.svg

Making your own polytopes!

[11]:
Q=Polymake.polytope.Polytope(POINTS=[[1,0,0,0] [1,4,0,0] [1,0,4,0] [1,0,0,4] [1,1,1,1] [1,1,1,5]]')
[11]:
type
Polytope
POINTS
1 0 0 0
1 4 0 0
1 0 4 0
1 0 0 4
1 1 1 1
1 1 1 5

Note: if you don’t know already the points are vertices, use POINTS, not VERTICES. (Same later with INEQUALITIES versus FACETS)

[15]:
Q.VERTICES
[15]:
pm::Matrix<pm::Rational>
1 0 0 0
1 4 0 0
1 0 4 0
1 0 0 4
1 1 1 5

[12]:
# if not in a Jupyter notebook: Polymake.polytope.visual(Q)
Polymake.display_svg(Q)
../_images/OSCAR_OscarPolytopes_22_0.svg

Defining polyhedra via halfspaces

[13]:
MyHPolytope=Polymake.polytope.Polytope(INEQUALITIES =
    [[1,1,1,1] [1, 2, 2,-2] [1,-1,-1,1] [1,2,2,-1]])
[13]:
type
Polytope
INEQUALITIES
1 1 1 1
1 2 -1 2
1 2 -1 2
1 -2 1 -1
1 0 0 0
[14]:
#Notice the different color here. Red = unbounded region
# if not in a Jupyter notebook: Polymake.polytope.visual(MyHPolytope)
Polymake.display_svg(MyHPolytope)
../_images/OSCAR_OscarPolytopes_25_0.svg
[19]:
MyHPolytope.BOUNDED
[19]:
false
[15]:
MyPolytope=Polymake.polytope.intersection(MyHPolytope,Polymake.polytope.cross(3))
MyPolytope.VERTICES
[15]:
pm::Matrix<pm::Rational>
1 0 1 0
1 0 -1 0
1 2/3 1/3 0
1 2/3 0 -1/3
1 0 0 1
1 -3/4 0 1/4
1 1/4 0 -3/4
1 -2/3 -1/3 0
1 0 -1/3 -2/3

[16]:
# Polymake.polytope.visual(MyPolytope)
Polymake.display_svg(MyPolytope)
../_images/OSCAR_OscarPolytopes_28_0.svg
[22]:
MyPolytope.F_VECTOR
[22]:
pm::Vector<pm::Integer>
9 15 8
[22]:
MyPolytope.VOLUME
[22]:
17/18
[17]:
F=Polymake.fan.normal_fan(MyPolytope)
[17]:
type
PolyhedralFan
COMPLETE
true
FAN_AMBIENT_DIM
3
FAN_DIM
3
LINEALITY_SPACE
MAXIMAL_CONES
{1 3 4 6}
{0 2 5 7}
{2 3 6}
{2 6 7}
{2 3 4 5}
{1 4 5}
{1 6 7}
{0 1 5}
{0 1 7}
PSEUDO_REGULAR
true
RAYS
1 1 1
1 -1/2 1
-1 1/2 -1/2
-1 -1 -1
1 -1 -1
1 1 -1
-1 -1 1
-1 1 1
REGULAR
true
[24]:
F.RAYS
[24]:
pm::Matrix<pm::Rational>
1 1 1
1 -1/2 1
-1 1/2 -1/2
-1 -1 -1
1 -1 -1
1 1 -1
-1 -1 1
-1 1 1

[25]:
F.MAXIMAL_CONES
[25]:
pm::IncidenceMatrix<pm::NonSymmetric>
{1 3 4 6}
{0 2 5 7}
{2 3 6}
{2 6 7}
{2 3 4 5}
{1 4 5}
{1 6 7}
{0 1 5}
{0 1 7}

[20]:
# Polymake.fan.visual(F)
Polymake.display_svg(F)
../_images/OSCAR_OscarPolytopes_34_0.svg
[19]:
MS=Polymake.polytope.minkowski_sum(MyPolytope,Polymake.polytope.cross(3))
[19]:
type
Polytope
description
Minkowski sum of 1* and 1*
CONE_AMBIENT_DIM
4
INPUT_LINEALITY
POINTS
1 1 1 0
1 -1 1 0
1 0 2 0
1 0 0 0
1 0 1 1
1 0 1 -1
1 1 -1 0
1 -1 -1 0
1 0 0 0
1 0 -2 0
1 0 -1 1
1 0 -1 -1
1 5/3 1/3 0
1 -1/3 1/3 0
1 2/3 4/3 0
1 2/3 -2/3 0
1 2/3 1/3 1
1 2/3 1/3 -1
1 5/3 0 -1/3
1 -1/3 0 -1/3
1 2/3 1 -1/3
1 2/3 -1 -1/3
1 2/3 0 2/3
1 2/3 0 -4/3
1 1 0 1
1 -1 0 1
1 0 1 1
1 0 -1 1
1 0 0 2
1 0 0 0
1 1/4 0 1/4
1 -7/4 0 1/4
1 -3/4 1 1/4
1 -3/4 -1 1/4
1 -3/4 0 5/4
1 -3/4 0 -3/4
1 5/4 0 -3/4
1 -3/4 0 -3/4
1 1/4 1 -3/4
1 1/4 -1 -3/4
1 1/4 0 1/4
1 1/4 0 -7/4
1 1/3 -1/3 0
1 -5/3 -1/3 0
1 -2/3 2/3 0
1 -2/3 -4/3 0
1 -2/3 -1/3 1
1 -2/3 -1/3 -1
1 1 -1/3 -2/3
1 -1 -1/3 -2/3
1 0 2/3 -2/3
1 0 -4/3 -2/3
1 0 -1/3 1/3
1 0 -1/3 -5/3
[21]:
# it not in a Juptyer notebook: Polymake.polytope.visual(MS)
Polymake.display_svg(MS)
../_images/OSCAR_OscarPolytopes_36_0.svg
[29]:
MS.VOLUME
[29]:
179/18