| [home] - [up] |
Abstract: We make a tour in the beautiful garden of algebraic, enumerative and bijective combinatorics. We start with the Temperley-Lieb algebra introduced in statistical physics in relation with the Potts model. The dimension is the classical Catalan number. A geometric interpretation with threads was given by Kauffman. This algebra is also connected to the theory of knots and braids. Then I shall give three interpretations of a basis of this algebra in terms of certain "heaps of dimers", of skew Ferrers diagrams and the permutations avoiding the pattern 321. This is a chapter of the "bijective Catalan book". The notion of heaps of pieces interprets the algebraic notion of commutation classes of words of the Cartier-Foata monoid.
Following Fomin, I shall introduce a nilpotent variation of the Temperley-Lieb algebra. The dimension and basis are the same as for the classical Temperley- Lieb algebra. The interest is that it can be represented by some operators acting on the Young lattice (partitions of integers or Ferrers diagrams), and thus underlying the relation with symmetric functions.
Then we will finish the tour by showing how the previous constructions can relate two different "geometric" interpretations in the theory of symmetric functions. The first is the interpretation of skew Schur functions in term of non crossing configurations of paths, following the Jacobi-Trudi identity and the Gessel-Viennot lemma. The second is the Fomin-Kirillov interpretation of the stable Schubert polynomials defined by Lascoux and Schuetzenberger (in the case of 321-avoiding permutations). This last construction is based on resolved configurations of threads and follows from a classical geometric interpretation of the Yang-Baxter equation. We are back in statistical physics.
Colloquium - 16:00
Abstract: In recent years path planning of autonomous mobile systems has received a lot of attention in the communities of robotics, computational geometry, and on-line algorithms. This includes basic algorithmic questions like: 1. How to find a target 2. How to create a map by exploring the environment 3. Knowing the map how to determine the current position.
We are interested in competitive on-line strategies, meaning that the robot's path will never exceed in length a constant factor times the length of the optimum path computed off-line. Especially, we address the exploration problem. The robot starts from a given point, s, on the polygon's boundary. It is equipped with a vision system that continuously provides the visibility of the current position. When each point of the polygon has at least once been visible, the robot returns to s. We sketch how to explore simple polygons with a competitive factor of 26.5. The analysis of the algorithm is founded on a novel geometric structure called the angle hull. Let D be a connected region inside a simple polygon, P. The angle hull AH(D) of D is the set of all points in P that can see two points of D at a right angle. We prove that the perimeter of AH(D) is at most twice as long as the perimeter of D. This bound is tight.
This is joint work with Christian Icking, Rolf Klein, and Klaus Kriegel.