Available versions of this document: latest release, release 4.1, release 4.0, release 3.6, release 3.5, nightly master
Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2
application fan
This application deals with polyhedral fans. You can define a fan, e.g. via its RAYS
and MAXIMAL_CONES
and compute several properties like HASSE_DIAGRAM
and F_VECTOR
.
imports from:
uses:
Objects
HyperplaneArrangement
:
A hyperplane arrangement. The hyperplane arrangement is given by a matrixHYPERPLANES
whose rows are the linear equations of the hyperplanes and an optional support cone. The support cone defaults to being the whole space. Duplicate hyperplanes are ignored, as well as hyperplanes that intersect the support cone trivially. The support cone is subdivided by the hyperplanes resulting in a fanCELL_DECOMPOSITION
.PlanarNet
:
A special big object class devoted to planar unfoldings of 3polytopes. Its main functionality is the visualization.PolyhedralComplex
:
A polyhedral complex. The derivation fromPolyhedralFan
works like the derivation ofPolytope
fromCone
.PolyhedralFan
:
A polyhedral fan. The current restriction is that each cone in the fan has to be pointed. This will be relaxed later. If a fan is specified viaINPUT_RAYS
andINPUT_CONES
each input cone must list all the input rays incident. Once nontrivial linealities are allowed the following will apply: TheRAYS
always lie in a linear subspace which is complementary to theLINEALITY_SPACE
.SubdivisionOfPoints
:
The inhomogeneous variant ofSubdivisionOfVectors
, similar to the derivation ofPointConfiguration
fromVectorConfiguration
.SubdivisionOfVectors
:
A subdivision of vectors, in contrast toPolyhedralFan
this allows cells with interior points. Similar to the distinction betweenCone
andVectorConfiguration
.Visual::PlanarNet
:
Visualization of a 3polytope as a planar net.Visual::PolyhedralFan
:
Visualization of a polyhedral fan as a graph
Functions
Consistency check
These clients provide consistency checks, e.g. whether a given list of rays and cones defines a polyhedral fan.

check_fan(Matrix rays, IncidenceMatrix cones)
Checks whether a given set of rays together with a list cones defines a polyhedral fan. If this is the case, the ouput is the
PolyhedralFan
defined by rays asINPUT_RAYS
, cones asINPUT_CONES
, lineality_space asLINEALITY_SPACE
if this option is given. Parameters:
Matrix
rays
IncidenceMatrix
cones
 Options:
Matrix
lineality_space
: Common lineality space for the cones.Bool
verbose
: prints information about the check. Returns:

check_fan_objects(Array<Cone> cones)
Checks whether the
Cone
objects form a polyhedral fan. If this is the case, returns thatPolyhedralFan
. Parameters:
 Options:
Bool
verbose
: prints information about the check. Returns:
Finite metric spaces
All around Tight spans of finite metric spaces and their conections to polyhedral geometry

max_metric(Int n)
Compute a metric such that the fvector of its tight span is maximal among all metrics with n points.
See Herrmann and Joswig: Bounds on the fvectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)

metric_extended_tight_span(Matrix<Rational> M)
Computes a extended tight span which is a
PolyhedralComplex
with induced from a mertic. Parameters:
 Returns:
 Example:
To compute the thracklemetric of five points and display the fvector of its tight span, do this:
> $M = thrackle_metric(5); > $PC = metric_extended_tight_span($M); > print $PC>F_VECTOR; 16 20 5

metric_tight_span(Matrix<Rational> M)
Computes a
SubdivisionOfPoints
with a weight function which is induced from a mertic. Parameters:
 Options:
Bool
extended
: If true, the extended tight span is computed. Returns:
 Example:
To compute the thracklemetric of five points and display the fvector of its tight span, do this:
> $M = thrackle_metric(5); > $PC = metric_tight_span($M,extended=>1); > print $PC>POLYTOPAL_SUBDIVISION>TIGHT_SPAN>F_VECTOR; 16 20 5

min_metric(Int n)
Compute a metric such that the fvector of its tight span is minimal among all metrics with n points.
See Herrmann and Joswig: Bounds on the fvectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)

thrackle_metric(Int n)
Compute a thrackle metric on n points. This metric can be interpreted as a lifting function for the thrackle triangulation.
See De Loera, Sturmfels and Thomas: Gröbner bases and triangulations of the second hypersimplex, Combinatorica 15 (1995)

tight_span_max_metric(Int n)
Compute a
SubdivisionOfPoints
with a tight span of a metric such that the fvector is maximal among all metrics with n points.See Herrmann and Joswig: Bounds on the fvectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)

tight_span_min_metric(Int n)
Compute a
SubdivisionOfPoints
with a tight span of a metric such that the fvector is minimal among all metrics with n points.See Herrmann and Joswig: Bounds on the fvectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)

tight_span_thrackle_metric(Int n)
Compute
SubdivisionOfPoints
with a tight span of th thrackle metric on n points. This metric can be interpreted as a lifting function which induces the thrackle triangulation of the second hypersimplex.See De Loera, Sturmfels and Thomas: Gröbner bases and triangulations of the second hypersimplex, Combinatorica 15 (1995)
Geometry
These functions capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.

cell_decomposition_brute_force
This function computes the
CELL_DECOMPOSITION
of a given hyperplane arrangement in a brute force way, by just considering every possible signature. Since not every signature gives a valid cell, it is much cheaper to traverse the cells ofCELL_DECOMPOSITION
by flipping the walls. This method is here for verifying results of our other algorithms.

generating_polyhedron_facets(PolyhedralFan P)
The facets of a polyhedron that has the fan P as its normal fan, or the empty matrix if no such polyhedron exists.
 Parameters:
 Returns:
Matrix<Scalar>

induced_subdivision<Scalar>(VectorConfiguration<Scalar> pc, Matrix<Scalar> R, Set I)
Calculate the subdivision induced on a point configuration by a height function h. The height function is specified as the sum of a set of rows of a matrix. Using the RAYS of the secondary_fan of the configuration works well.
 Type Parameters:
Scalar
: the underlying number type Parameters:
VectorConfiguration<Scalar>
pc
: (or polytope/cone) the input configurationMatrix<Scalar>
R
: a matrix such that R→cols() == pc→N_VECTORSSet
I
: (or ARRAY) a set of indices that select rows from R Options:
Bool
verbose
: print the final height function used=? Default 0 Returns:

induced_subdivision
Calculate the subdivision induced on a polytope by a height function h.
Producing a fan
These clients provide standard constructions for PolyhedralFan
objects, e.g. from polytopes (face_fan
or normal_fan
) or from other fans (via projection, refinement or product).

cell_decomposition_rs
Produce the cell decomposition induced by a hyperplane arrangement

common_refinement(PolyhedralFan f1, PolyhedralFan f2)
Computes the common refinement of two fans.
 Parameters:
 Returns:

face_fan<Coord>(Polytope p, Vector v)
Computes the face fan of p.

face_fan<Coord>(Polytope p)
Computes the face fan of p. the polytope has to be CENTERED
 Type Parameters:
Coord
 Parameters:
Polytope
p
 Returns:

gfan_secondary_fan(Matrix M)
Call gfan to compute the secondary fan of a point configuration.
 Parameters:
Matrix
M
: a matrix whose rows are the vectors in the configuration Returns:

gfan_secondary_fan(PointConfiguration P)
Call gfan to compute the secondary fan of a point configuration.
 Parameters:
 Returns:

graph_associahedron_fan(Graph G)
Produce the dual fan of a graph associahedron.
 Parameters:
Graph
G
: the input graph Returns:

groebner_fan(Ideal I)
Call gfan to compute the greobner fan of an ideal.
 Parameters:
Ideal
I
: input ideal Returns:

intersection(PolyhedralFan F, Matrix H)
Construct a new fan as the intersection of given fan with a subspace.
 Parameters:
Matrix
H
: equations of subspace Returns:

k_skeleton<Coord>(PolyhedralFan F, Int k)
Computes the kskeleton of the polyhedral fan F, i.e. the subfan of F consisting of all cones of dimension ⇐k.
 Type Parameters:
Coord
 Parameters:
Int
k
: the desired top dimension Returns:

normal_fan<Coord>(Polytope p)
Computes the normal fan of p.
 Type Parameters:
Coord
 Parameters:
Polytope
p
 Returns:

planar_net(Polytope p)
Computes a planar net of the 3polytope p. Note that it is an open problem if such a planar net always exists.
 PROGRAM MIGHT TERMINATE WITH AN EXCEPTION *
If it does, please, notify the polymake team! Seriously.
 Parameters:
Polytope
p
 Returns:

product(PolyhedralFan F1, PolyhedralFan F2)
Construct a new polyhedral fan as the product of two given polyhedral fans F1 and F2.
 Parameters:
 Options:
Bool
no_coordinates
: only combinatorial information is handled Returns:

project_full(PolyhedralFan P)
Orthogonally project a fan to a coordinate subspace such that redundant columns are omitted, i.e., the affine hull of the support of the projection is fulldimensional, without changing the combinatorial type.
 Parameters:
 Options:
Bool
no_labels
: Do not copyVERTEX_LABELS
to the projection. default: 0 Returns:
 Example:
x and y axis in 3space
> $f = new PolyhedralFan(INPUT_RAYS=>[[1,0,0],[0,1,0]], INPUT_CONES=>[[0],[1]]); > $pf = project_full($f); > print $pf>RAYS; 1 0 0 1
> print $pf>MAXIMAL_CONES; {0} {1}
Producing a hyperplane arrangement
These clients provide constructions for HyperplaneArrangement
objects.

facet_arrangement

hypersimplex_vertex_splits(Int k, Int d)
Produce the arrangement of vertex splits of the hypersimplex $ Δ(k,d) $
 Parameters:
Int
k
: number of 1sInt
d
: ambient dimension Options:
Bool
group
Bool
no_vertices
: do not compute verticesBool
no_facets
: do not compute facetsBool
no_vif
: do not compute vertices in facets Returns:
 Example:
This corresponds to the hypersimplex in dimension 4 with vertices with exactly two 1entries and computes its symmetry group:
> $H = hypersimplex_vertex_splits(2,4,group=>1);
Producing a polyhedral complex
These clients provide constructions for PolyhedralComplex
objects.

mixed_subdivision(Polytope P_0, Polytope P_1, Array<Set> VIF, Scalar t_0, Scalar t_1)
Create a weighted mixed subdivision of the scaled Minkowski sum of two polytopes, using the Cayley trick. The polytopes must have the same dimension, at least one of them must be pointed. The vertices of the first polytope P_0 are weighted with t_0, and the vertices of the second polytope P_1 with t_1. Default values are t_0=t_1=1.
 Parameters:
Polytope
P_0
: the first polytopePolytope
P_1
: the second polytopeScalar
t_0
: the weight for the vertices of P_0; default 1Scalar
t_1
: the weight for the vertices of P_1; default 1 Options:
Bool
no_labels
: Do not copyVERTEX_LABELS
from the original polytopes. default: 0 Returns:

mixed_subdivision(Int m, Polytope C, Array<Set> a)
Create a weighted mixed subdivision of a Cayley embedding of a sequence of polytopes. Each vertex v of the ith polytope is weighted with t_i, the ith entry of the optional array t.
 Parameters:
Int
m
: the number of polytopes giving rise to the Cayley embeddingPolytope
C
: the Cayley embedding of the input polytopes Options:
Vector<Scalar>
t
: scaling for the Cayley embedding; defaults to the all1 vectorBool
no_labels
: Do not copyVERTEX_LABELS
from the original polytopes. default: 0 Returns:

mixed_subdivision(Array<Polytope> A, Array<Set> VIF)
Create a weighted mixed subdivision of a sequence (P1,…,Pm) of polytopes, using the Cayley trick. All polytopes must have the same dimension, at least one of them must be pointed. Each vertex v of the ith polytope is weighted with t_i, the ith entry of the optional array t.
 Parameters:
 Options:
Vector<Scalar>
t
: scaling for the Cayley embedding; defaults to the all1 vectorBool
no_labels
: Do not copyVERTEX_LABELS
from the original polytopes. default: 0 Returns:

tiling_quotient<Coord>(Polytope P, Polytope Q)
Calculates the quotient of P by Q+L, where Q+L is a lattice tiling. The result is a polytopal complex inside Q.
Symmetry
These functions capture information of the object that is concerned with the action of permutation groups.

combinatorial_symmetries(PolyhedralFan f)
Compute the combinatorial symmetries (i.e., automorphisms of the face lattice) of a given fan f. They are stored in terms of a GROUP.RAYS_ACTION and a GROUP.MAXIMAL_CONES_ACTION property in f, and the GROUP.MAXIMAL_CONES_ACTION is also returned.
 Parameters:
 Returns:
 Example:
To get the ray symmetry group of the square and print its generators, type the following:
> print combinatorial_symmetries(normal_fan(polytope::cube(2)))>GENERATORS; 2 3 0 1 1 0 3 2 0 2 1 3
> $f = normal_fan(polytope::cube(2)); combinatorial_symmetries($f); > print $f>GROUP>RAYS_ACTION>GENERATORS; 0 1 3 2 1 0 2 3 2 3 0 1
> print $f>GROUP>MAXIMAL_CONES_ACTION>GENERATORS; 2 3 0 1 1 0 3 2 0 2 1 3

cones_action(PolyhedralFan f, Int k)
Returns the permutation action induced by the symmetry group of the fan f on the set of kdimensional cones. This action is not stored as a property of f, because polymake doesn't support dynamic names of properties. Be aware that the set of kdimensional cones itself is
$f>CONES>[$k1]
. Parameters:
PolyhedralFan
f
: the input fanInt
k
: the dimension of the cones to induce the action on Returns:
 Example:
Consider a 3cube c. To calculate the induced action of Aut(c) on the set of 2dimensional cones of the normal fan, type
> $f = fan::normal_fan(polytope::cube(3, group=>1)); > print fan::cones_action($f,2)>properties(); name: CONES_ACTION(2) type: PermutationAction<Int, Rational> description: action induced on 2dimensional cones GENERATORS 0 3 4 1 2 5 7 6 8 10 9 11 1 0 2 5 6 3 4 7 9 8 11 10 0 2 1 4 3 8 9 10 5 6 7 11
> print $f>CONES>[1]; {2 4} {0 4} {0 2} {1 4} {1 2} {3 4} {0 3} {1 3} {2 5} {0 5} {1 5} {3 5}

orbit_complex(PolyhedralComplex input_complex, Array<Array<Int>> gens)
Constructs the orbit complex of a given polyhedral complex input_complex with respect to a given set of generators gens.
 Parameters:
PolyhedralComplex
input_complex
: the generating complex of the orbit complex Returns:
 Example:
To calculate an orbit complex with respect to a group of coordinate permutations, follow these steps: First specify a seed complex:
> $f=new PolyhedralComplex(VERTICES=>[[1,1,1],[1,1,0],[1,1,1]], MAXIMAL_POLYTOPES=>[[0,1],[1,2]]);
Then define the orbit complex by specifying a permutation action on coordinates:
> $oc = orbit_complex($f, [[1,0]]);
The only properties of $oc defined so far reside in GROUP:
> print $oc>GROUP>properties(); type: Group as PolyhedralComplex<Rational>::GROUP COORDINATE_ACTION type: PermutationAction<Int, Rational> as PolyhedralComplex<Rational>::GROUP::COORDINATE_ACTION MAXIMAL_POLYTOPES_ACTION type: PermutationAction<Int, Rational> as PolyhedralComplex<Rational>::GROUP::MAXIMAL_POLYTOPES_ACTION
Now you can calculate the
VERTICES
andMAXIMAL_POLYTOPES
of the orbit fan. IMPORTANT: You must ask forVERTICES
beforeMAXIMAL_POLYTOPES
.> print $oc>VERTICES; 1 1 1 1 1 0 1 1 1 1 0 1
> print $oc>N_MAXIMAL_POLYTOPES; 4

orbit_complex(PolyhedralFan input_fan, PermutationAction a)
Constructs the orbit fan of a given fan input_fan with respect to a given group action a.
 Parameters:
PolyhedralFan
input_fan
: the generating fan of the orbit fanPermutationAction
a
: the action of a permutation group on the coordinates of the ambient space Returns:
 Example:
To calculate an orbit complex with respect to a group of coordinate permutations, follow these steps: First specify a seed complex:
> $f=new PolyhedralComplex(VERTICES=>[[1,1,1],[1,1,0],[1,1/2,1/4]], MAXIMAL_POLYTOPES=>[[0,2],[1,2]]);
Then define the orbit complex by specifying a matrix group action on the coordinates:
> $oc = orbit_complex($f, polytope::cube(2,group=>1)>GROUP>MATRIX_ACTION);
The only properties of $oc defined so far reside in GROUP:
Now you can calculate the
VERTICES
andMAXIMAL_POLYTOPES
of the orbit fan. IMPORTANT: You must ask forVERTICES
beforeMAXIMAL_POLYTOPES
.> print $oc>VERTICES; 1 1 1 1 1 0 1 1/2 1/4 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1/2 1/4 1 1/2 1/4 1 1/4 1/2 1 1/4 1/2 1 1/4 1/2 1 1/4 1/2 1 1/2 1/4
> print $oc>N_MAXIMAL_POLYTOPES; 16

orbit_fan(PolyhedralFan input_fan, Array<Array<Int>> gens)
Constructs the orbit fan of a given fan input_fan with respect to a given set of generators gens.
 Parameters:
PolyhedralFan
input_fan
: the generating fan of the orbit fan Returns:
 Example:
To calculate an orbit fan, follow these steps: First specify a seed fan:
> $f=new PolyhedralFan(RAYS=>[[1,1],[1,0],[1,1]], MAXIMAL_CONES=>[[0,1],[1,2]]);
Then define the orbit fan by specifying coordinate permutations:
> $of = orbit_fan($f,[[1,0]]);
The only properties of $of defined so far reside in GROUP:
> print $of>GROUP>properties(); name: unnamed#0 type: Group as PolyhedralFan<Rational>::GROUP HOMOGENEOUS_COORDINATE_ACTION type: PermutationAction<Int, Rational> MAXIMAL_CONES_ACTION type: PermutationAction<Int, Rational> as PolyhedralFan<Rational>::GROUP::MAXIMAL_CONES_ACTION
Now you can calculate the
RAYS
andMAXIMAL_CONES
of the orbit fan. IMPORTANT: You must ask forRAYS
beforeMAXIMAL_CONES
.> print $of>RAYS; 1 1 1 0 1 1 0 1
> print $of>N_MAXIMAL_CONES; 4

orbit_fan<Scalar>(PolyhedralFan input_fan, Array<Matrix<Scalar>> gens)
Constructs the orbit fan of a given fan input_fan with respect to a given set of matrix group generators gens.
 Type Parameters:
Scalar
: underlying number type Parameters:
PolyhedralFan
input_fan
: the generating fan of the orbit fan Returns:
 Example:
To calculate an orbit fan, follow these steps: First specify a seed fan:
> $f=new PolyhedralFan(RAYS=>[[1,1,1],[1,1,0],[1,1/2,1/4]],MAXIMAL_CONES=>[[0,2],[1,2]]);
Then define the orbit fan by specifying a matrix group action:
> $of = orbit_fan($f,polytope::cube(2,group=>1)>GROUP>MATRIX_ACTION);
The only properties of $of defined so far reside in GROUP:
> print $of>GROUP>properties(); name: unnamed#0 type: Group as PolyhedralFan<Rational>::GROUP MATRIX_ACTION type: MatrixActionOnVectors<Rational> MAXIMAL_CONES_ACTION type: PermutationAction<Int, Rational> as PolyhedralFan<Rational>::GROUP::MAXIMAL_CONES_ACTION
Now you can calculate the
RAYS
andMAXIMAL_CONES
of the orbit fan. IMPORTANT: You must ask forRAYS
beforeMAXIMAL_CONES
.> print $of>RAYS; 1 1 1 1 1 0 1 1/2 1/4 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1/2 1/4 1 1/2 1/4 1 1/4 1/2 1 1/4 1/2 1 1/4 1/2 1 1/4 1/2 1 1/2 1/4
> print $of>N_MAXIMAL_CONES; 16
Triangulations, subdivisions and volume
These functions collect information about triangulations and other subdivisions of the object and properties usually computed from such, as the volume.

secondary_fan(VectorConfiguration V)
Calculate the secondary fan of a point or vector configuration, or polytope.
 Parameters:
VectorConfiguration
V
: (or polytope) the input configuration Options:
Matrix
restrict_to
: the equations defining a subspace that the secondary fan should be restricted toInt
seed
: controls the outcome of the random number generator for generating a randomized initial subdivision Returns:
PolyhedralFan<Scalar>

secondary_fan
Visualization
These functions are for visualization.

splitstree(Visual::Object vis_obj …)
Call SplitsTree with the given visual objects.
 Parameters:
Visual::Object
vis_obj …
: objects to display Options:
String
File
: “filename” or “AUTO” Only create a NEXUS format file, don't start the GUI. The.nex
suffix is automatically added to the file name. Specify AUTO if you want the filename be automatically derived from the drawing title. You can also use any expression allowed for theopen
function, including “” for terminal output, “&HANDLE” for an already opened file handle, or “ program” for a pipe.

visual_splitstree(Matrix<Rational> M)
Visualize the splits of a finite metric space (that is, a planar image of a tight span). Calls SplitsTree.
 Parameters:
 Options:
String
name
: Name of the drawing Returns:
Other
Special purpose functions.

building_set(Array<Set> generators, Int n)
Produce a building set from a family of sets.
 Parameters:
Int
n
: the size of the ground set Returns:

is_B_nested(Set<Set> check_me, PowerSet B)
Check if a family of sets is nested wrt a given building set.
 Parameters:
PowerSet
B
: the building set Returns:

tubes_of_graph(Graph G)
Output the set of all tubes of a graph
 Parameters:
Graph
G
: the input graph Returns: