Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterization of tropical hemispaces by (P,R)-decompositions
132
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider tropical hemispaces, defined as tropically convex sets whose complements are also tropically convex, and tropical semispaces, defined as maximal tropically convex sets not containing a given point. We introduce the concept of $(P,R)$-decomposition. This yields (to our knowledge) a new kind of representation of tropically convex sets extending the classical idea of representing convex sets by means of extreme points and rays. We characterize tropical hemispaces as tropically convex sets that admit a (P,R)-decomposition of certain kind. In this characterization, with each tropical hemispace we associate a matrix with coefficients in the completed tropical semifield, satisfying an extended rank-one condition. Our proof techniques are based on homogenization (lifting a convex set to a cone), and the relation between tropical hemispaces and semispaces.
rate research
Read More
We study the max-plus or tropical analogue of the notion of polar: the polar of a cone represents the set of linear inequalities satisfied by its elements. We establish an analogue of the bipolar theorem, which characterizes all the inequalities satisfied by the elements of a tropical convex cone. We derive this characterization from a new separation theorem. We also establish variants of these results concerning systems of linear equalities.
In a previous paper, we announced a formula to compute Gromov-Witten and Welschinger invariants of some toric varieties, in terms of combinatorial objects called floor diagrams. We give here detailed proofs in the tropical geometry framework, in the case when the ambient variety is a complex surface, and give some examples of computations using floor diagrams. The focusing on dimension 2 is motivated by the special combinatoric of floor diagrams compared to arbitrary dimension. We treat a general toric surface case in this dimension: the curve is given by an arbitrary lattice polygon and include computation of Welschinger invariants with pairs of conjugate points. See also cite{FM} for combinatorial treatment of floor diagrams in the projective case.
Tropical polyhedra have been recently used to represent disjunctive invariants in static analysis. To handle larger instances, tropical analogues of classical linear programming results need to be developed. This motivation leads us to study the tropical analogue of the classical linear-fractional programming problem. We construct an associated parametric mean payoff game problem, and show that the optimality of a given point, or the unboundedness of the problem, can be certified by exhibiting a strategy for one of the players having certain infinitesimal properties (involving the value of the game and its derivative) that we characterize combinatorially. We use this idea to design a Newton-like algorithm to solve tropical linear-fractional programming problems, by reduction to a sequence of auxiliary mean payoff game problems.
Let $X$, $Y$ be sets and let $Phi$, $Psi$ be mappings with the domains $X^{2}$ and $Y^{2}$ respectively. We say that $Phi$ is combinatorially similar to $Psi$ if there are bijections $f colon Phi(X^2) to Psi(Y^{2})$ and $g colon Y to X$ such that $Psi(x, y) = f(Phi(g(x), g(y)))$ for all $x$, $y in Y$. It is shown that the semigroups of binary relations generated by sets ${Phi^{-1}(a) colon a in Phi(X^{2})}$ and ${Psi^{-1}(b) colon b in Psi(Y^{2})}$ are isomorphic for combinatorially similar $Phi$ and $Psi$. The necessary and sufficient conditions under which a given mapping is combinatorially similar to a pseudometric, or strongly rigid pseudometric, or discrete pseudometric are found. The algebraic structure of semigroups generated by ${d^{-1}(r) colon r in d(X^{2})}$ is completely described for nondiscrete, strongly rigid pseudometrics and, also, for discrete pseudometrics $d colon X^{2} to mathbb{R}$.
In 1945, A. W. Goodman and R. E. Goodman proved the following conjecture by P. ErdH{o}s: Given a family of (round) disks of radii $r_1$, $ldots$, $r_n$ in the plane it is always possible to cover them by a disk of radius $R = sum r_i$, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body $K subset mathbb{R}^d$ with homothety coefficients $tau_1, ldots, tau_n > 0$ it is always possible to cover them by a translate of $frac{d+1}{2}left(sum tau_iright)K$, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
