Tropical Mathematics & its Applications
Supported by the LMS
23rd January 2015
School of Mathematics, University of Manchester
Local Organiser: Marianne Johnson
* Glenn Merlet (Marseille)
* Elizabeth Baldwin (London School of Economics)
* Francoise Tisseur (Manchester)
All talks will talk place in the Frank Adams room of the Alan Turing building in the School of Mathematics, University of Manchester. (See below for advice on how to get here.)
12:00 Early arrivers meet for lunch
13:00 Glenn Merlet Weak CSR expansions and bounds for periodicity in powers of tropical matrices.
The celebrated Cyclicity Theorem states that the sequence of powers of a tropical irreducible matrix is ultimately periodic, up to some simple renormalization. The starting time of the periodic behavior, called transient, has been investigated several times, leading to several incomparable bounds. All those bounds are the maximum of two parts: one that depends on the underlying graph and one that also depends on the values of the matrix. This is obviously necessary, as shown by some simple examples. We call Weak CSR expansion a formula of the form (1) $A^t=CS^tR \oplus B^t$, where S is a periodic matrix conjugated to a boolean one and B is a matrix simpler than A. We propose several choices of B for each A and show that (1) holds for t greater than some well known bounds for the transient of boolean matrices. We thus recover the CSR expansion introduced by Sergeev and Schneider, with several bounds on on its starting time. Then, we show that when A is irreducible $CS^tR \oplus B^t=CS^tR$ for large enough t, thus improving all the known bounds on the transient and giving some new ones. The proofs are based on decompositions and recompositions of optimal walks on the digraph of the matrix. I will explain the main line of the proofs and the most striking way to reduce the length of optimal walks on the digraph. This is based on joint work with Thomas Nowak (ENS) and Sergei Sergeev (Birmingham).
14:00 Elizabeth Baldwin The geometry of auctions and competitive equilibrium with indivisible goods
In order to develop new auctions for related but different indivisible goods, we study how an agent's demand changes as prices change. The set of prices at which demand changes forms a tropical hypersurface. Simple geometric properties translate directly to economic properties, providing a new taxonomy for agents' valuations. Tropical-geometric results provide new results about when competitive equilibrium exists. This is joint work with Paul Klemperer (Oxford University).
15:30 Francoise Tisseur Exploiting Tropical Algebra in Numerical Linear Algebra
We aim to show that tropical algebra can be useful in numerical linear algebra, in particular for problems with large variation in the magnitude of the elements and which are often difficult to solve numerically. We will present diverse applications of tropical algebra to matrix computations.
We plan to go for an early dinner shortly after the last talk, somewhere near to the train station. It would be helpful if you could let Marianne know if you intend to join us for dinner.
There are no registration fees, but it would be helpful if you could confirm your attendance by email (email@example.com). Financial support for UK-based postgraduate students is awarded on a first come first served basis; please give an estimate of your travel costs when confirming your attendance.Lunch
Please note that lunch will not be provided, however, you are most welcome to join us for lunch at one of the university cafeterias in University Place. If you would like to do so, we will meet at 12 on the atrium bridge area on the first floor of the Alan Turing building.
Walking from Manchester Piccadilly to the Alan Turing Building should take around 20 mins. Leave the station by the Fairfield Street exit (head down the escalators or lift from the main concourse) which brings you out at a big road junction. Cross both main roads, and go along a smaller road (Granby Row) to the left of the Bull's Head pub. Keep straight on, as the road becomes a pedestrian walk and then a road again, and at the phoneboxes turn left onto Sackville Street. Go under the railway bridge and continue under a bridge between buildings, and where the road bends off to the right, follow the left-hand pavement which becomes a footpath and goes through an underpass. Afterwards, keep left under the motorway flyover (avoiding a deeper underpass ahead) before bearing right (avoiding yet another underpass to the left). After very carefully crossing the motorway sliproad, you find yourself on Brook Street. Walk down this (away from the flyover). At the intersection with Grosvenor Street, cross both roads and then continue along (now Upper) Brook Street on the opposite side. Cross the next side-road (Booth Street East, carefully again!), continue past the Aquatics Centre car park and then the Alan Turing Building is on your right. To get into the building, go into the walkway after the second "finger" and then the doors are on your right.
Note that a printer-friendly version of these directions (along with a map) can be found here.