Glossary

10.4 Tropical discrete convexity

8 min read•august 20, 2024

blends tropical geometry with optimization, providing tools for solving combinatorial problems. It studies convex sets and hulls in the , offering a fresh perspective on classical concepts like polytopes and linear programming.

This framework has wide-ranging applications, from phylogenetics to auction theory. By translating familiar ideas into the tropical setting, it reveals new insights and efficient algorithms for discrete optimization problems.

Basics of tropical discrete convexity

  • Tropical discrete convexity is a branch of tropical geometry that studies convex sets and optimization problems in the tropical semiring
  • It provides a framework for solving problems using techniques from tropical algebra and geometry
  • Tropical discrete convexity has applications in various fields such as phylogenetics, auction theory, scheduling, and network optimization

Tropical convex hulls

Construction of tropical convex hulls

Top images from around the web for Construction of tropical convex hulls

  • Frontiers | Pattern Formation and Tropical Geometry View original

    Is this image relevant?

  • Frontiers | Pattern Formation and Tropical Geometry View original

    Is this image relevant?

  • Frontiers | Pattern Formation and Tropical Geometry View original

    Is this image relevant?

1 of 3

Top images from around the web for Construction of tropical convex hulls

  • Frontiers | Pattern Formation and Tropical Geometry View original

    Is this image relevant?

  • Frontiers | Pattern Formation and Tropical Geometry View original

    Is this image relevant?

  • Frontiers | Pattern Formation and Tropical Geometry View original

    Is this image relevant?

1 of 3
  • The of a set of points is the smallest tropically convex set containing those points
  • It can be constructed by taking the tropical sum of all possible of the points
  • The tropical convex hull has a unique minimal generating set called the or tropical vertices
  • Example: The tropical convex hull of the points (1,2),(3,4),(5,6)(1, 2), (3, 4), (5, 6) is the set {(x,y):min⁡(x−1,x−3,x−5)+min⁡(y−2,y−4,y−6)≥0}\{(x, y) : \min(x-1, x-3, x-5) + \min(y-2, y-4, y-6) \geq 0\}

Properties of tropical convex hulls

  • Tropical convex hulls are closed under tropical addition and scalar multiplication
  • The tropical convex hull of a finite set of points is a
  • The tropical convex hull operator satisfies the : tconv⁡(A+B)=tconv⁡(A)+tconv⁡(B)\operatorname{tconv}(A + B) = \operatorname{tconv}(A) + \operatorname{tconv}(B)
  • Example: The tropical convex hull of a line segment is a tropical line segment, which is a concatenation of two classical line segments with a corner at their intersection

Tropical polytopes

Definition of tropical polytopes

  • A tropical polytope is the tropical convex hull of a finite set of points in the tropical space
  • It can be represented as the intersection of finitely many
  • Tropical polytopes are the tropical analogues of classical polytopes in Euclidean space
  • Example: The tropical polytope defined by the inequalities x⊕1≤y,y⊕2≤z,z⊕3≤xx \oplus 1 \leq y, y \oplus 2 \leq z, z \oplus 3 \leq x is the tropical convex hull of the points (1,2,3),(4,2,3),(1,5,3),(1,2,6)(1, 2, 3), (4, 2, 3), (1, 5, 3), (1, 2, 6)

Vertices and edges of tropical polytopes

  • The vertices of a tropical polytope are the tropical extreme points of the polytope
  • An edge of a tropical polytope is a tropical line segment connecting two vertices
  • The set of vertices and edges forms the 1-skeleton of the tropical polytope
  • Example: A tropical triangle has 3 vertices and 3 edges, which are tropical line segments connecting the vertices

Combinatorial structure of tropical polytopes

  • The combinatorial structure of a tropical polytope is determined by its face lattice
  • The faces of a tropical polytope are the tropical convex hulls of subsets of its vertices
  • The dimension of a face is the number of linearly independent points in its generating set minus one
  • Example: A tropical 3-dimensional cube has 8 vertices, 12 edges, and 6 facets (2-dimensional faces)

Tropical convex sets

Tropical halfspaces and hyperplanes

  • A tropical halfspace is the set of points satisfying a tropical linear inequality
  • A is the set of points satisfying a tropical linear equation
  • Tropical halfspaces and hyperplanes are the building blocks of tropical convex sets
  • Example: The tropical halfspace defined by x⊕2≤yx \oplus 2 \leq y is the set {(x,y):min⁡(x,2)≤y}\{(x, y) : \min(x, 2) \leq y\}

Intersection of tropical halfspaces

  • The intersection of finitely many tropical halfspaces is a tropical convex set
  • Every tropical convex set can be represented as the intersection of tropical halfspaces
  • The tropical analogue of the classical characterizes the feasibility of a system of tropical linear inequalities
  • Example: The intersection of the tropical halfspaces x⊕1≤y,y⊕2≤z,z⊕3≤xx \oplus 1 \leq y, y \oplus 2 \leq z, z \oplus 3 \leq x is a tropical polytope

Tropical cones and polyhedral complexes

  • A is a tropical convex set that is closed under tropical scalar multiplication
  • A is a collection of tropical polytopes that intersect nicely
  • Tropical cones and polyhedral complexes are used to study the local structure of tropical varieties
  • Example: The tropical convex hull of the rays (1,0),(0,1),(−1,−1)(1, 0), (0, 1), (-1, -1) is a tropical cone in the plane

Tropical linear programming

Formulation of tropical linear programs

  • A tropical linear program is an optimization problem with a tropical linear objective function and tropical linear constraints
  • The goal is to minimize or maximize the objective function subject to the constraints
  • Tropical linear programs can be used to model various combinatorial optimization problems
  • Example: Minimize x⊕y⊕zx \oplus y \oplus z subject to x⊕1≤y,y⊕2≤z,z⊕3≤xx \oplus 1 \leq y, y \oplus 2 \leq z, z \oplus 3 \leq x

Feasible solutions and optimality

  • A feasible solution to a tropical linear program is a point that satisfies all the constraints
  • An optimal solution is a feasible solution that achieves the minimum or maximum value of the objective function
  • The set of feasible solutions to a tropical linear program is a tropical convex set
  • Example: The point (1,2,3)(1, 2, 3) is a feasible solution to the above tropical linear program, and it is also optimal

Duality in tropical linear programming

  • Every tropical linear program has a dual program, which is another tropical linear program
  • The weak duality theorem states that the value of any feasible solution to the primal is greater than or equal to the value of any feasible solution to the dual
  • The strong duality theorem states that if either the primal or the dual has an optimal solution, then so does the other, and the optimal values coincide
  • Example: The dual of the above tropical linear program is: Maximize u⊕v⊕wu \oplus v \oplus w subject to u≤1,v≤2,w≤3,u⊕v⊕w≤0u \leq 1, v \leq 2, w \leq 3, u \oplus v \oplus w \leq 0

Tropical discrete optimization

Tropical shortest paths

  • The asks for the path of minimum tropical length between two vertices in a weighted directed graph
  • It can be solved using a tropical version of or the
  • The tropical distance matrix of a graph can be computed using tropical matrix multiplication
  • Example: In a graph with edge weights 1,2,31, 2, 3, the tropical shortest path from vertex ss to vertex tt has length min⁡(1+2,1+3,2+3)=3\min(1+2, 1+3, 2+3) = 3

Tropical minimum spanning trees

  • The problem asks for a spanning tree of minimum tropical length in a weighted undirected graph
  • It can be solved using a tropical version of or
  • The tropical minimum spanning tree is unique if the edge weights are distinct
  • Example: In a graph with edge weights 1,2,3,41, 2, 3, 4, the tropical minimum spanning tree has length min⁡(1+2,1+3,1+4,2+3,2+4,3+4)=3\min(1+2, 1+3, 1+4, 2+3, 2+4, 3+4) = 3

Tropical network flows

  • The tropical maximum flow problem asks for the maximum tropical flow that can be sent from a source vertex to a sink vertex in a capacitated directed graph
  • It can be solved using a tropical version of the or the
  • The tropical max-flow min-cut theorem relates the maximum flow value to the minimum tropical capacity of a cut separating the source and the sink
  • Example: In a graph with edge capacities 1,2,31, 2, 3, the tropical maximum flow from ss to tt is min⁡(1,2,3)=1\min(1, 2, 3) = 1

Applications of tropical discrete convexity

Phylogenetics and tree metrics

  • Tropical convexity can be used to study the space of and tree metrics
  • The parametrizes the set of phylogenetic trees with a fixed number of leaves
  • The space of tree metrics can be embedded into a tropical projective space using the tropical Plücker coordinates
  • Example: The tropical Grassmannian of lines in the plane is a tropical tree that represents the possible phylogenetic trees on 4 taxa

Auction theory and economics

  • Tropical convexity arises in the study of auctions and economic equilibria
  • The set of in an exchange economy can be characterized using tropical hypersurfaces
  • The tropical Jacobian matrix of the determines the stability of equilibrium prices
  • Example: In a two-good economy with , the set of equilibrium prices is a tropical line in the plane

Scheduling and project management

  • Tropical convexity can be applied to scheduling problems and project management
  • The of a project with precedence constraints can be computed using tropical matrix multiplication
  • The set of feasible schedules can be described as a tropical polytope in the space of start times
  • Example: In a project with 3 tasks and precedence constraints 1→2,1→31 \rightarrow 2, 1 \rightarrow 3, the completion time is max⁡(p1+p2,p1+p3)\max(p_1 + p_2, p_1 + p_3), where pip_i is the processing time of task ii

Connections to classical discrete convexity

Analogies between tropical and classical convexity

  • Many concepts and results in tropical convexity have classical analogues in discrete convexity
  • Tropical polytopes are analogous to classical polytopes, and tropical halfspaces are analogous to classical halfspaces
  • is analogous to classical linear programming, with the tropical semiring replacing the real field
  • Example: The is analogous to the classical Farkas lemma in linear programming

Differences in combinatorial properties

  • Despite the analogies, tropical convexity also exhibits some unique combinatorial properties that differ from classical convexity
  • Tropical polytopes can have non-convex topological realizations and exotic combinatorial types that do not arise in classical convexity
  • The number of vertices of a tropical polytope can be exponential in the dimension, unlike classical polytopes
  • Example: The tropical cyclic polytope tconv⁡({(i,i2,…,id):i=1,…,n})\operatorname{tconv}(\{(i, i^2, \ldots, i^d) : i = 1, \ldots, n\}) has Θ(n⌊d/2⌋)\Theta(n^{\lfloor d/2 \rfloor}) vertices

Limits of tropical discretization

  • Tropical convexity can be seen as a discretization of classical convexity, but this discretization has some limitations
  • Not every classical convex set can be approximated by a tropical convex set, and not every classical optimization problem can be tropicalized
  • Tropical convexity is most useful for studying piecewise linear objects and combinatorial optimization problems
  • Example: The tropical approximation of a smooth convex function is a piecewise linear function, which may not capture all the properties of the original function

Key Terms to Review (32)

Bellman-Ford Algorithm: The Bellman-Ford algorithm is a graph search algorithm that computes the shortest paths from a single source vertex to all other vertices in a weighted graph, accommodating negative weight edges. This algorithm is particularly significant because it can handle graphs with negative weight cycles and can help in optimization problems related to network flow and resource allocation.
Cobb-Douglas Utilities: Cobb-Douglas utilities are a type of utility function used in economics to represent consumer preferences, characterized by the form $U(x_1, x_2) = A x_1^{\alpha} x_2^{\beta}$, where $x_1$ and $x_2$ are quantities of two goods, and $A$, $\alpha$, and $\beta$ are positive constants. This function reflects the idea that consumers will allocate their resources in a way that maintains a consistent ratio of consumption between different goods, illustrating a form of homothetic preferences that can also be analyzed through tropical geometry when exploring discrete convexity.
Combinatorial Optimization: Combinatorial optimization is a field of optimization that focuses on finding the best solution from a finite set of discrete possibilities. It often deals with problems involving the arrangement, selection, and combination of elements to optimize certain criteria, like cost or efficiency. This concept is crucial in understanding structures and properties related to tropical geometry, as it intersects with various mathematical constructs and models.
Completion time: Completion time refers to the total time taken to finish a task or process in a given context. In the realm of tropical discrete convexity, it is particularly relevant in understanding the optimal paths and structures within tropical polytopes and how they can influence combinatorial optimization problems.
Dijkstra's Algorithm: Dijkstra's Algorithm is a popular method used in computer science to find the shortest path between nodes in a graph, which can represent, for example, a road map. It works by progressively exploring nodes and calculating the shortest distance from a starting point to all other nodes, making it particularly useful in optimization problems within discrete structures. This algorithm is connected to tropical discrete convexity as it provides insights into the minimal paths in graphs, where the usual operations of addition and multiplication are replaced with tropical addition and tropical multiplication.
Excess Demand Function: The excess demand function is a mathematical representation used to indicate the difference between the quantity demanded and the quantity supplied in a market, often depicted in terms of prices. It plays a crucial role in understanding market equilibria and can be analyzed through the lens of tropical discrete convexity to study its properties and behaviors in tropical geometry. This function helps to identify conditions under which supply and demand are equal, thereby indicating market stability or instability.
Farkas Lemma: Farkas Lemma is a fundamental result in linear inequalities and optimization, stating that for a given system of linear inequalities, either there exists a solution or a certain related system of inequalities has no solution. This lemma plays a crucial role in understanding the duality in optimization problems and is especially significant in the context of tropical discrete convexity, where it helps to establish the existence of certain tropical convex sets and their properties.
Ford-Fulkerson Algorithm: The Ford-Fulkerson Algorithm is a method used to compute the maximum flow in a flow network. This algorithm works by finding augmenting paths in the network and incrementally increasing the flow until no more augmenting paths can be found, ensuring that the flow is maximized while respecting capacity constraints. It connects to concepts of tropical network flows, where tropical mathematics provides a framework for optimizing flows, and tropical discrete convexity, where it helps to understand the geometry of feasible flows in a network.
Kruskal's Algorithm: Kruskal's Algorithm is a greedy algorithm used for finding the minimum spanning tree of a connected, undirected graph. It works by sorting all the edges of the graph and adding them one by one to the growing spanning tree, ensuring that no cycles are formed. This algorithm is particularly relevant in tropical discrete convexity, where it helps to analyze combinatorial structures and optimize connectivity within tropical geometric frameworks.
Minkowski Sum Property: The Minkowski Sum Property refers to a fundamental operation in geometry where the sum of two sets is defined as the set of all possible sums of elements from each set. In the context of tropical discrete convexity, this property helps in understanding how geometric structures behave under addition, particularly with respect to the tropical semiring, which modifies traditional concepts of addition and multiplication.
Phylogenetic trees: Phylogenetic trees are diagrammatic representations that illustrate the evolutionary relationships among various biological species or entities based on their genetic characteristics. These trees help visualize how different species have diverged from common ancestors over time, providing insights into their evolutionary history and lineage.
Prim's Algorithm: Prim's Algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It works by starting with a single vertex and growing the spanning tree one edge at a time, always choosing the smallest weight edge that connects a vertex in the tree to a vertex outside the tree. This method emphasizes tropical discrete convexity by exploring how edges can connect points while minimizing weights.
Primal-dual relationship: The primal-dual relationship refers to the connection between two optimization problems: the primal problem and its corresponding dual problem. In this context, solving one problem provides insights into the solution of the other, highlighting a fundamental symmetry in optimization theory. This relationship is essential for understanding how solutions can be interpreted and related within tropical linear programming and discrete convexity, revealing properties like strong duality and optimality conditions.
Push-relabel algorithm: The push-relabel algorithm is an efficient method for computing maximum flows in a flow network by maintaining a preflow and adjusting labels on vertices to manage excess flow. This technique uses local operations, allowing the flow to be adjusted incrementally without needing to recalculate the entire flow structure. It connects well with concepts of tropical discrete convexity by providing a framework for examining flows in directed graphs, especially when working with tropical semirings.
Tropical cone: A tropical cone is a fundamental structure in tropical geometry that represents a set of points defined by tropical linear inequalities. These cones can be thought of as the tropical analogs of classical convex cones, where the operations of addition and multiplication are replaced with tropical addition (taking the minimum) and tropical multiplication (adding values). This concept plays a crucial role in understanding the geometry and combinatorial properties of tropical polytopes and is essential for exploring tropical discrete convexity.
Tropical Convex Hull: The tropical convex hull of a set of points in tropical geometry is the smallest tropical convex set that contains all those points. This concept is vital for understanding the structure of tropical polytopes, which are formed by the tropical convex combinations of points, and it plays a critical role in topics like tropical discrete convexity and hyperplane arrangements. Essentially, it helps to generalize traditional notions of convexity into the tropical framework, where addition is replaced by the minimum operation and scalar multiplication is replaced by the operation of taking the maximum.
Tropical discrete convexity: Tropical discrete convexity refers to a concept in tropical geometry that studies the behavior of sets and functions using the tropical semiring. It extends traditional notions of convexity by incorporating tropical operations, such as maximizing or minimizing values, which leads to new interpretations of geometric structures. This concept plays a vital role in analyzing polytopes and their properties within the framework of tropical mathematics.
Tropical Extreme Points: Tropical extreme points refer to the vertices of a tropical convex set, which are defined using tropical geometry's unique operations. These points are crucial in understanding the structure of tropical convex hulls and tropical convexity, as they capture the essential combinatorial information of the set. The concept ties together various aspects of tropical geometry, revealing the connections between geometry and combinatorial optimization.
Tropical Farkas Lemma: The Tropical Farkas Lemma is a principle in tropical geometry that provides necessary and sufficient conditions for the existence of tropical solutions to systems of inequalities. This lemma draws parallels to classical Farkas Lemma in linear algebra, enabling the understanding of tropical linear inequalities and their feasible solutions, which are essential in various areas like discrete convexity and oriented matroids.
Tropical Grassmannian: The tropical Grassmannian is a combinatorial object that generalizes the classical Grassmannian to tropical geometry, capturing the essence of linear subspaces in a tropical setting. It arises naturally in various contexts, including the study of tropical polytopes and as a tool for understanding tropical varieties through their Plücker coordinates. This framework also connects deeply with concepts like tropical discriminants and Schubert calculus, providing insights into how different geometrical structures can be analyzed through the lens of tropical algebra.
Tropical Halfspaces: Tropical halfspaces are geometric constructs in tropical geometry that generalize the concept of halfspaces from classical linear algebra. They are defined using tropical operations, which involve taking the minimum or maximum instead of the usual addition and multiplication, creating a new way to analyze convexity and optimization in this tropical context. Tropical halfspaces play a crucial role in understanding tropical convex sets, leading to insights into discrete convexity and combinatorial properties in various mathematical settings.
Tropical Hyperplane: A tropical hyperplane is a geometric concept defined in tropical geometry, serving as a generalization of traditional hyperplanes in Euclidean space. It is represented by equations of the form $$ ext{max}(a_1 x_1 + b_1, a_2 x_2 + b_2, ext{...}, a_n x_n + b_n) = c$$, where the coefficients $a_i$ and $b_i$ are from the tropical semiring. Tropical hyperplanes are instrumental in understanding tropical halfspaces, polytopes, and various algebraic structures, leading to results like tropical Cramer’s rule and concepts of discrete convexity.
Tropical linear combinations: Tropical linear combinations refer to the process of combining elements in tropical mathematics using the tropical addition and multiplication operations. In this context, tropical addition is defined as taking the minimum of two values, while tropical multiplication is equivalent to standard addition. This unique approach allows for the exploration of geometric structures and properties within tropical discrete convexity, revealing insights into the behavior of sets and functions in a tropical framework.
Tropical Linear Programming: Tropical linear programming is a framework that adapts classical linear programming concepts to the tropical semiring, where the operations of addition and multiplication are replaced by minimum and addition, respectively. This reimagining of linear programming allows for the analysis of optimization problems in various mathematical and applied contexts, including combinatorial optimization and algebraic geometry. By utilizing tropical convex hulls and polytopes, tropical linear programming enables the study of solutions that can be interpreted through geometric structures and combinatorial properties.
Tropical Minimum Spanning Tree: A tropical minimum spanning tree is a concept in tropical geometry that identifies the subset of edges in a weighted graph that connects all vertices with the minimum possible 'tropical weight.' In this context, the tropical weight is determined using the tropical semiring, where addition is replaced by taking the minimum and multiplication is replaced by addition. This redefinition leads to unique properties and applications in discrete geometry and combinatorial optimization.
Tropical network flow: Tropical network flow refers to a mathematical framework used to model and analyze flows within networks, where the standard operations of addition and multiplication are replaced by tropical addition and tropical multiplication. This concept is crucial for understanding the behavior of flows in networks with constraints, as it allows for the study of discrete convexity properties and optimization within tropical geometry.
Tropical objective function: A tropical objective function is a mathematical expression used in tropical geometry that involves operations of maximization or minimization within the framework of tropical arithmetic, which replaces conventional addition with taking the minimum and conventional multiplication with addition. This concept is crucial for understanding optimization problems in tropical geometry, especially when analyzing discrete convexity and piecewise linear functions. Tropical objective functions help in formulating and solving optimization problems by providing a different perspective on classical methods.
Tropical Polyhedral Complex: A tropical polyhedral complex is a collection of tropical polytopes that fit together in a certain way, forming a combinatorial structure that captures geometric and algebraic properties in tropical geometry. This structure allows for the study of tropical varieties, which serve as counterparts to classical algebraic varieties, providing insight into problems like optimization and counting solutions.
Tropical Polytope: A tropical polytope is a geometric object defined in tropical geometry, which is a piecewise-linear analogue of classical polytopes. It is formed by taking the convex hull of a set of points in tropical space, where the operations of addition and multiplication are replaced by minimum and addition, respectively, allowing for a new way to study combinatorial structures and optimization problems.
Tropical Semiring: A tropical semiring is an algebraic structure that consists of the set of real numbers extended with negative infinity, where tropical addition is defined as taking the minimum and tropical multiplication as standard addition. This structure allows for the transformation of classical algebraic problems into a combinatorial framework, connecting various mathematical concepts like optimization, geometry, and algebraic varieties.
Tropical Shortest Path Problem: The tropical shortest path problem involves finding the shortest path between points in a weighted graph using tropical mathematics, where the addition operation is replaced by taking the minimum and the multiplication operation is replaced by standard addition. This unique approach allows for the application of concepts from tropical geometry to combinatorial optimization, particularly in understanding the structure of discrete convex sets.
Walrasian Equilibrium Prices: Walrasian equilibrium prices are the set of prices in a market where supply equals demand for all goods, ensuring that every buyer and seller is satisfied without any excess supply or demand. This concept is crucial in understanding how markets function under perfect competition, and it connects to the analysis of efficient resource allocation and the role of preferences in consumer choice.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide