Tropical polyhedra

Introduction

A tropical polytope $\mathrm{tconv}(V)$ is the tropical convex hull of finitely many points $V$ which is defined as the set of tropical linear combinations of the points $v_i\in V$ with coefficients in $\mathbb{R}$. The point set may be taken from either the tropical projective torus $\mathbb{R}^d/\mathbb{R}\mathbf{1}$ or the tropical projective space $\mathbb{TP}^{d-1} := (\mathbb{T}^d\setminus\{\mathbf{\infty}\})/\mathbb{R}\mathbf{1}.$ Likewise, $\mathrm{tconv}(V)$ may be considered in either $\mathbb{R}^d/\mathbb{R}\mathbf{1}$ or $\mathbb{TP}^{d-1}$.

For more details see

Chapter 5.2 in [MS15]
Chapter 5 in [Jos21]

Note:

We offer two types with slightly different semantics, TropicalPolyhedron and TropicalPointConfiguration.
- The TropicalPointConfiguration type represents the information of the covector decomposition of the tropical projective torus induced by $V$.
- A TropicalPolyhedron refers to the actual tropical convex hull of the point set $V$ which carries an induced covector decomposition, which is a polyhedral subcomplex of the covector decomposition for the corresponding TropicalPointConfiguration.
Currently, OSCAR supports
- point sets $V$ with entirely finite coordinates
- point sets $V$ with infinite coordinates and $\mathrm{tconv}(V)$ inside the tropical projective torus
Functionality for tropical polytopes over the entire tropical projective space is planned for a future version

Constructors

Both TropicalPolyhedron and TropicalPointConfiguration can be constructed from the following data:

a rational matrix and specifying min- or max-convention
a matrix over a tropical semiring
a vector of points with coordinates in a tropical semiring

Additionally, one can convert between TropicalPolyhedron and TropicalPointConfiguration. This way, the underlying low-level object in polymake and already computed information is preserved.

tropical_convex_hull — Function

tropical_convex_hull(V::MatElem{TropicalSemiringElem{M}}) where M<:MinOrMax

Construct the tropical convex hull of the vertices V in the tropical projective torus with M as tropical addition.

Examples

Defines a tropical unit ball in the 2-dimensional tropical projective torus with max as addition:

julia> T = tropical_semiring(max);

julia> A = T.(identity_matrix(QQ, 3));

julia> P = tropical_convex_hull(A)
Max tropical polyhedron in tropical projective torus of dimension 2

The vertices of a tropical convex hull may also be given by the rows of a tropical matrix:

julia> A = T[0 -4 -1; 0 -1 0];

julia> P = tropical_convex_hull(A)
Max tropical polyhedron in tropical projective torus of dimension 2

tropical_convex_hull(V::QQMatrix[,convention::MinOrMax=min])

Construct the tropical convex hull of the vertices V in the tropical projective torus with convention as tropical addition.

Examples

Define a point configuration containing a tropical unit ball in the 2-dimensional tropical projective torus with max as addition:

julia> A = identity_matrix(QQ, 3);

julia> P = tropical_convex_hull(A,max)
Max tropical polyhedron in tropical projective torus of dimension 2

tropical_point_configuration — Function

tropical_point_configuration(V::MatElem{TropicalSemiringElem{M}}) where M<:MinOrMax

Construct the tropical point configuration of the vertices V in the tropical projective torus with M as tropical addition.

Examples

Defines a point configuration containing a tropical unit ball in the 2-dimensional tropical projective torus with max as addition:

julia> T = tropical_semiring(max);

julia> A = T.(identity_matrix(QQ, 3));

julia> P = tropical_point_configuration(A)
Max tropical point configuration in tropical projective torus of dimension 2

The tropical point configuration may also be given by the rows of a tropical matrix:

julia> A = T[0 -4 -1; 0 -1 0];

julia> P = tropical_point_configuration(A)
Max tropical point configuration in tropical projective torus of dimension 2

tropical_point_configuration(V::QQMatrix[, convention::MinOrMax=min])

Construct the tropical point configuration of the vertices V in the tropical projective torus with convention as tropical addition.

Examples

Define a point configuration containing a tropical unit ball in the 2-dimensional tropical projective torus with max as addition:

julia> A = identity_matrix(QQ, 3);

julia> P = tropical_point_configuration(A,max)
Max tropical point configuration in tropical projective torus of dimension 2

Properties

TropicalPolyhedron and TropicalPointConfiguration are closely related as being given by a finite set of points, but refer to different interpretations of this point configuration. In general, the properties of a TropicalPolyhedron refer to the tropical convex hull of these points while TropicalPointConfiguration refers to the covector decomposition of the entire tropical projective torus.

ambient_dim — Method

ambient_dim(P::TropicalPolyhedron)
ambient_dim(P::TropicalPointConfiguration)

Return the ambient dimension of P.

Examples

julia> P = tropical_convex_hull(QQ[0 -1 0; 0 -4 -1]);

julia> ambient_dim(P)
2

Tropical polyhedra

vertices — Method

vertices([as::Type{T} = PointVector,] P::TropicalPolyhedron)

Return an iterator over the vertices of P, that is, a minimal generating set V such that P equals tropical_convex_hull(V).

Examples

The following computes retrieves the vertices of a tropical polytope with redundant generating set:

julia> P = tropical_convex_hull(QQ[0 -1 0; 0 -4 -1]);

julia> vertices(P)
2-element SubObjectIterator{PointVector{TropicalSemiringElem{typeof(min)}}}:
 [(0), (-1), (0)]
 [(0), (-4), (-1)]

julia> T = tropical_semiring();

julia> Q = tropical_convex_hull(T[0 1 2; inf 0 3; inf inf 0; 0 1 0]);

julia> vertices(Q)
3-element SubObjectIterator{PointVector{TropicalSemiringElem{typeof(min)}}}:
 [(0), (1), (2)]
 [infty, (0), (3)]
 [infty, infty, (0)]

n_vertices — Method

n_vertices(P::TropicalPolyhedron)

Return the number of vertices of P.

dim — Method

dim(P::TropicalPolyhedron)

Return the dimension of P.

Examples

julia> P = tropical_convex_hull(QQ[0 -1 0; 0 -4 -1]);

julia> dim(P)
1

maximal_covectors — Method

maximal_covectors([as::Type{T} = PointVector,] P::TropicalPolyhedron)

Return an iterator over the maximal covectors of P.

Examples

The following computes retrieves the vertices of a tropical polytope:

julia> P = tropical_convex_hull(QQ[0 -1 0; 0 -4 -1]);

julia> maximal_covectors(P)
2-element SubObjectIterator{IncidenceMatrix}:
 3×2 IncidenceMatrix
 [1]
 [2]
 [1]
 3×2 IncidenceMatrix
 [1]
 [2]
 [2]

covector_decomposition — Method

covector_decomposition(P::TropicalPolyhedon; dehomogenize_by=1)

Get the covector decomposition of the tropical polytope P inside the tropical projective torus as a PolyhedralComplex.

Examples

The following retrieves the covector decomposition of a non-convex tropical polytope:

julia> TT = tropical_semiring();

julia> P = tropical_convex_hull(TT[0 1 4; inf 0 2; inf inf 0]);

julia> CD = covector_decomposition(P)
Polyhedral complex in ambient dimension 2

julia> CD |> maximal_polyhedra
2-element SubObjectIterator{Polyhedron{QQFieldElem}}:
 Polytope in ambient dimension 2
 Polyhedron in ambient dimension 2

is_bounded — Method

is_bounded(P::TropicalPolyhedron)

Checks whether P is bounded in the tropical projective torus.

Tropical point configurations

points — Method

points([as::Type{T} = PointVector,] P::TropicalPointConfiguration)

Return an iterator over the points of tropical point configuration P.

Examples

The following retrievs the pseudovertices of a bounded tropical polytope:

julia> P = tropical_point_configuration(QQ[0 -1 0; 0 -4 -1]);

julia> points(P)
2-element SubObjectIterator{PointVector{TropicalSemiringElem{typeof(min)}}}:
 [(0), (-1), (0)]
 [(0), (-4), (-1)]

n_points — Method

n_points(P::TropicalPointConfiguration)

Return the number of points of P.

Examples

The 3-cube's number of vertices can be obtained with this input:

julia> P = tropical_point_configuration(QQ[0 -1 0; 0 -4 -1]);

julia> n_points(P)
2

maximal_covectors — Method

maximal_covectors([as::Type{T} = PointVector,] P::TropicalPointConfiguration)

Return an iterator over the maximal covectors with respect to P.

Examples

The following computes retrieves the vertices of a covector decomposition:

julia> P = tropical_point_configuration(QQ[0 -1 0; 0 -4 -1]);

julia> maximal_covectors(P)
6-element SubObjectIterator{IncidenceMatrix}:
 3×2 IncidenceMatrix
 []
 [1, 2]
 []
 3×2 IncidenceMatrix
 [1, 2]
 []
 []
 3×2 IncidenceMatrix
 [1]
 [2]
 []
 3×2 IncidenceMatrix
 []
 []
 [1, 2]
 3×2 IncidenceMatrix
 []
 [2]
 [1]
 3×2 IncidenceMatrix
 [1]
 []
 [2]

covector_decomposition — Method

covector_decomposition(P::TropicalPointConfiguration; dehomogenize_by=1)

Get the covector decomposition of the tropical projective torus induced by P as a PolyhedralComplex.

Examples

The following retrieves the covector decomposition induced by a tropical point configuration:

julia> TT = tropical_semiring();

julia> P = tropical_point_configuration(TT[0 1 4; inf 0 2; inf inf 0]);

julia> CD = covector_decomposition(P)
Polyhedral complex in ambient dimension 2

julia> CD |> maximal_polyhedra
5-element SubObjectIterator{Polyhedron{QQFieldElem}}:
 Polyhedron in ambient dimension 2
 Polyhedron in ambient dimension 2
 Polyhedron in ambient dimension 2
 Polyhedron in ambient dimension 2
 Polyhedron in ambient dimension 2