Robert's Mistakes

Diagram 9: Tropical geometry (tropical curve)

Sep 22, 2013

The tropical algebra is a semiring (that's the same as a ring where addition does not need to have an inverse). To make numbers tropical we replace addition a+b by min(a,b) and multiplication a*b by addition a+b. What you get is a very simplistic version of the numbers.

Legend says that the brazilian Imre Simon, who pioneered much of the subject, was having a hard time convincing his french colleagues to take him seriously - the idea was just too tropical...

But one can do geometry with these "numbers". The main subject in this area are polynomial curves, like f(x,y) = x^2 + y^2 - 1. The picture below on the right shows a cubic curve. It's helpful to add a dimension, just for visualization. You can see what's going on in the other image, i got from here (searching for "tropical hypersurface"):

http://www.dm.unipi.it/~bertrand/amoeb-geotrop/node2.html

This all looks very cute, but actually this setup makes a lot of sense for linear programming problems, where we are looking for maxima in simple linear spaces. Today i learned an application for tropical geometry which does some recursive linear programming to measure similarity of genomes: The Needleman-Wunsch Algorithm. See here for an exellect intro:

http://liorpachter.wordpress.com/2013/09/21/the-needleman-wunsch-algorithm/

The algorithm works on any semiring and the tropical one is fast in implementations and the resulting measures already have interesting interpretations. But there is another interesting semiring for this application i never heard of before: +: convex hull, *: minkowski sum, see here:

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Minkowski_sum_2/Chapter_main.html http://en.wikipedia.org/wiki/Minkowski_addition

But i digress. Bernd Sturmfels is an important figure in tropical geometry, popularizing and helping to get it applied. Here's an introductory video talk by him:

http://archive.org/details/lecture_10285

For more good references look here:

http://ncatlab.org/nlab/show/tropical+geometry

Thanks to +Lior Pachter for making me aware of the Needleman-Wunsch algorithm.