Navigation

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: common, graph, polytope
uses: group, ideal, topaz

Objects

User Functions

  •  

    Consistency check

    These clients provide consistency checks, e.g. whether a given list of rays and cones defines a polyhedral fan.

  •  

    Finite metric spaces

    All around Tight spans of finite metric spaces and their conections to polyhedral geometry

    •  
      max_metric (n) → Matrix

      Compute a metric such that the f-vector of its tight span is maximal among all metrics with n points.

      See Herrmann and Joswig: Bounds on the f-vectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)
      Parameters
      Intn
      the number of points
      Returns
      Matrix

      Example:
      • To compute the max-metric of five points and display the f-vector of its tight span, do this:> $M = max_metric(5);> $PC = metric_tight_span($M,extended=>1);> print $PC->POLYTOPAL_SUBDIVISION->TIGHT_SPAN->F_VECTOR; 16 20 5
    •  
      metric_extended_tight_span (M) → PolyhedralComplex

      Computes a extended tight span which is a PolyhedralComplex with induced from a mertic.

      Parameters
      Matrix<Rational>M
      a metric
      Returns
      PolyhedralComplex

      Example:
      • To compute the thrackle-metric of five points and display the f-vector 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 (M) → SubdivisionOfPoints

      Computes a SubdivisionOfPoints with a weight function which is induced from a mertic.

      Parameters
      Matrix<Rational>M
      a metric
      Options
      Boolextended
      If true, the extended tight span is computed.
      Returns
      SubdivisionOfPoints

      Example:
      • To compute the thrackle-metric of five points and display the f-vector 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 (n) → Matrix

      Compute a metric such that the f-vector of its tight span is minimal among all metrics with n points.

      See Herrmann and Joswig: Bounds on the f-vectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)
      Parameters
      Intn
      the number of points
      Returns
      Matrix

      Example:
      • To compute the min-metric of five points and display the f-vector of its tight span, do this:> $M = min_metric(5);> $PC = metric_tight_span($M,extended=>1);> print $PC->POLYTOPAL_SUBDIVISION->TIGHT_SPAN->F_VECTOR; 16 20 5
    •  
      thrackle_metric (n) → Matrix

      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)
      Parameters
      Intn
      the number of points
      Returns
      Matrix

      Example:
      • To compute the thrackle-metric of five points and display the f-vector of its tight span, do this:> $M = thrackle_metric(5);> $PC = metric_extended_tight_span($M);> print $PC->F_VECTOR; 16 20 5
    •  
      tight_span_max_metric (n) → SubdivisionOfPoints

      Compute a SubdivisionOfPoints with a tight span of a metric such that the f-vector is maximal among all metrics with n points.

      See Herrmann and Joswig: Bounds on the f-vectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)
      Parameters
      Intn
      the number of points
      Returns
      SubdivisionOfPoints

      Example:
      • To compute the f-vector of the tight span with maximal f-vector, do this:> print tight_span_max_metric(5)->POLYTOPAL_SUBDIVISION->TIGHT_SPAN->F_VECTOR; 11 15 5
    •  
      tight_span_min_metric (n) → SubdivisionOfPoints

      Compute a SubdivisionOfPoints with a tight span of a metric such that the f-vector is minimal among all metrics with n points.

      See Herrmann and Joswig: Bounds on the f-vectors of tight spans, Contrib. Discrete Math., Vol.2, (2007)
      Parameters
      Intn
      the number of points
      Returns
      SubdivisionOfPoints

      Example:
      • To compute the f-vector of the tight span with minimal f-vector, do this:> print tight_span_min_metric(5)->POLYTOPAL_SUBDIVISION->TIGHT_SPAN->F_VECTOR; 11 15 5
    •  
      tight_span_thrackle_metric (n) → SubdivisionOfPoints

      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)
      Parameters
      Intn
      the number of points
      Returns
      SubdivisionOfPoints

      Example:
      • To compute the $f$-vector, do this:> print tight_span_min_metric(5)->POLYTOPAL_SUBDIVISION->TIGHT_SPAN->F_VECTOR; 11 15 5
  •  

    Geometry

    These functions capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.

    •  
      generating_polyhedron_facets (P) → Matrix<Scalar>

      The facets of a polyhedron that has the fan P as its normal fan, or the empty matrix if no such polyhedron exists.

      Parameters
      PolyhedralFanP
      Returns
      Matrix<Scalar>
    •  
      induced_subdivision <Scalar> (pc, R, I) → Set<Set>

      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 configuration
      Matrix<Scalar>R
      a matrix such that R->cols() == pc->N_VECTORS
      SetI
      (or ARRAY) a set of indices that select rows from R
      Options
      Boolverbose
      print the final height function used=? Default 0
      Returns
      Set<Set>
      the subdivision induced on the configuration by the final height function
    •  
      induced_subdivision ()

      Calculate the subdivision induced on a polytope by a height function h.

  •  

    Other

    Special purpose functions.

    •  
      building_set (generators, n) → PowerSet

      Produce a building set from a family of sets.

      Parameters
      Array<Set>generators
      the generators of the building set
      Intn
      the size of the ground set
      Returns
      PowerSet
      the induced building set
    •  
      cone_of_tubing (G, T) → Cone

      Output the cone of a tubing

      Parameters
      GraphG
      the input graph
      GraphT
      the input tubing
      Returns
      Cone
    •  
      flip_tube (G, T, t) → Graph

      Flip a tubing in a tube

      Parameters
      GraphG
      the input graph
      GraphT
      the input tubing
      Intt
      the tube to flip, identified by its root
      Returns
      Graph
    •  
      is_building_set (check_me, n) → Bool

      Check if a family of sets is a building set.

      Parameters
      PowerSetcheck_me
      the would-be building set
      Intn
      the size of the ground set
      Returns
      Bool
      is check_me really a building set?
    •  
      is_B_nested (check_me, B) → Bool

      Check if a family of sets is nested wrt a given building set.

      Parameters
      Set<Set>check_me
      the would-be nested sets
      PowerSetB
      the building set
      Returns
      Bool
      is the family of sets really nested wrt B?
    •  
      tubes_of_graph (G) → Set<Set>

      Output the set of all tubes of a graph

      Parameters
      GraphG
      the input graph
      Returns
      Set<Set>
    •  
      tubes_of_tubing (G, T) → Set<Set>

      Output the tubes of a tubing

      Parameters
      GraphG
      the input graph
      GraphT
      the input tubing
      Returns
      Set<Set>
    •  
      tubing_of_graph (G) → Set<Set>

      Output one tubing of a graph

      Parameters
      GraphG
      the input graph
      Returns
      Set<Set>
  •  

    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).

  •  

    Producing a polyhedral complex

    These clients provide constructions for PolyhedralComplex objects.

    •  
      mixed_subdivision (P_0, P_1, VIF, t_0, t_1) → PolyhedralComplex

      Create a weighted mixed subdivision of the 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
      PolytopeP_0
      the first polytope
      PolytopeP_1
      the second polytope
      Array<Set>VIF
      the indices of the vertices of the mixed cells
      Scalart_0
      the weight for the vertices of P_0; default 1
      Scalart_1
      the weight for the vertices of P_1; default 1
      Options
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytopes. default: 0
      Returns
      PolyhedralComplex
    •  
      mixed_subdivision (m, C, a) → PolyhedralComplex

      Create a weighted mixed subdivision of a Cayley embedding of a sequence of polytopes. Each vertex v of the i-th polytope is weighted with t_i, the i-th entry of the optional array t.

      Parameters
      Intm
      the number of polytopes giving rise to the Cayley embedding
      PolytopeC
      the Cayley embedding of the input polytopes
      Array<Set>a
      triangulation of C
      Options
      Vector<Scalar>t
      scaling for the Cayley embedding; defaults to the all-1 vector
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytopes. default: 0
      Returns
      PolyhedralComplex
    •  
      mixed_subdivision (A) → PolyhedralComplex

      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 i-th polytope is weighted with t_i, the i-th entry of the optional array t.

      Parameters
      Array<Polytope>A
      the input polytopes
      Options
      Vector<Scalar>t
      scaling for the Cayley embedding; defaults to the all-1 vector
      Boolno_labels
      Do not copy VERTEX_LABELS from the original polytopes. default: 0
      Returns
      PolyhedralComplex
    •  
      tiling_quotient <Coord> (P, Q) → PolyhedralComplex

      Calculates the quotient of P by Q+L, where Q+L is a lattice tiling. The result is a polytopal complex inside Q.

      Type Parameters
      Coord
      Parameters
      PolytopeP
      a polytope
      PolytopeQ
      a polytope that tiles space
      Returns
      PolyhedralComplex
  •  

    Symmetry

    These functions capture information of the object that is concerned with the action of permutation groups.

    •  
      combinatorial_symmetries (f) → group::PermutationAction

      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
      PolyhedralFanf
      Returns
      group::PermutationAction
      the action of the combinatorial symmetry group on the rays

      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 (f, k) → group::PermutationAction

      Returns the permutation action induced by the symmetry group of the fan f on the set of k-dimensional 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 k-dimensional cones itself is $f->CONES->[$k-1].

      Parameters
      fan::PolyhedralFanf
      the input fan
      Intk
      the dimension of the cones to induce the action on
      Returns
      group::PermutationAction
      a the action induced by Aut(f) on the set of k-dimensional cones

      Example:
      • Consider a 3-cube c. To calculate the induced action of Aut(c) on the set of 2-dimensional 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 2-dimensional 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 (input_complex, gens) → fan::PolyhedralComplex

      Constructs the orbit complex of a given polyhedral complex input_complex with respect to a given set of generators gens.

      Parameters
      fan::PolyhedralComplexinput_complex
      the generating complex of the orbit complex
      Array<Array<Int>>gens
      the generators of a permutation group that acts on the coordinates of the ambient space
      Returns
      fan::PolyhedralComplex
      the orbit complex of input_complex w.r.t. the coordinate action generated by gens

      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 and MAXIMAL_POLYTOPES of the orbit fan. IMPORTANT: You must ask for $oc->VERTICES before $oc->MAXIMAL_POLYTOPES. > print $oc->VERTICES; 1 1 1 1 1 0 1 -1 -1 1 0 1> print $oc->N_MAXIMAL_POLYTOPES; 4
    •  
      orbit_complex (input_fan, a) → Polytope

      Constructs the orbit fan of a given fan input_fan with respect to a given group action a.

      Parameters
      fan::PolyhedralFaninput_fan
      the generating fan of the orbit fan
      group::PermutationActiona
      the action of a permutation group on the coordinates of the ambient space
      Returns
      Polytope
      the orbit fan of input_fan w.r.t. the action a

      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: type: Group as PolyhedralComplex<Rational>::GROUP MATRIX_ACTION_ON_COMPLEX type: MatrixActionOnVectors<Rational> as PolyhedralComplex<Rational>::GROUP::MATRIX_ACTION_ON_COMPLEX MAXIMAL_POLYTOPES_ACTION type: PermutationAction<Int, Rational> as PolyhedralComplex<Rational>::GROUP::MAXIMAL_POLYTOPES_ACTION Now you can calculate the VERTICES and MAXIMAL_POLYTOPES of the orbit fan. IMPORTANT: You must ask for $oc->VERTICES before $oc->MAXIMAL_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 (input_fan, gens) → fan::PolyhedralFan

      Constructs the orbit fan of a given fan input_fan with respect to a given set of generators gens.

      Parameters
      fan::PolyhedralFaninput_fan
      the generating fan of the orbit fan
      Array<Array<Int>>gens
      the generators of a permutation group that acts on the coordinates of the ambient space
      Returns
      fan::PolyhedralFan
      the orbit fan of input_fan w.r.t. the coordinate action generated by gens

      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 and MAXIMAL_CONES of the orbit fan. IMPORTANT: You must ask for $of->RAYS before $of->MAXIMAL_CONES. > print $of->RAYS; 1 1 1 0 -1 -1 0 1> print $of->N_MAXIMAL_CONES; 4
    •  
      orbit_fan <Scalar> (input_fan, gens) → fan::PolyhedralFan

      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
      fan::PolyhedralFaninput_fan
      the generating fan of the orbit fan
      Array<Matrix<Scalar>>gens
      the generators of a matrix group that acts on the ambient space
      Returns
      fan::PolyhedralFan
      the orbit fan of input_fan w.r.t. the matrix action generated by gens

      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 and MAXIMAL_CONES of the orbit fan. IMPORTANT: You must ask for $of->RAYS before $of->MAXIMAL_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 (V) → PolyhedralFan<Scalar>

      Calculate the secondary fan of a point or vector configuration, or polytope.

      Parameters
      polytope::VectorConfigurationV
      (or polytope) the input configuration
      Options
      Array<Set>initial_subdivision
      a seed subdivision of V
      Matrixrestrict_to
      the equations defining a subspace that the secondary fan should be restricted to
      Intseed
      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 (vis_obj ...)

      Call wiki:external_software#SplitsTree with the given visual objects.

      Parameters
      Visual::Objectvis_obj ...
      objects to display
      Options
      StringFile
      "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 the open function, including "-" for terminal output, "&HANDLE" for an already opened file handle, or "| program" for a pipe.
    •  
      visual_splitstree (M) → Visual::Object

      Visualize the splits of a finite metric space (that is, a planar image of a tight span). Calls SplitsTree.

      Parameters
      Matrix<Rational>M
      Matrix defining a metric
      Options
      Array<String>taxa
      Labels for the taxa
      Stringname
      Name of the file
      Returns
      Visual::Object

Common Option Lists

  •  

    Geometry

    These options capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.

    •  
      secondary_cone_options

      Parameters for user method secondary_cone.

      Options
      Matrixequations
      system of linear equation the cone is cut with
      Set<Int>lift_to_zero
      restrict lifting function to zero at points designated
      Boollift_face_to_zero
      restrict lifting functions to zero at the entire face spanned by points designated
      Booltest_regularity
      throws an exception if subdivision is not regular
  •  

    Visualization

    These options are for visualization.