Math-Info 2010

Towards new interactions between mathematics and computer science


Invited Seminars

Thematic month

The five weeks

Seminar On The Interaction Between Discrete Geometry And Combinatorics On Words

This seminar is organized by Srecko Brlek.

1.  First seminar: May 17th-19th, 2010.

  • This seminar does not require any specific knowledge or background. It will be rather informal, and will proceed on a slow pace. There will be room to add other talks, according to the audience will.
  • Registration for rooms and meals at CIRM is compulsory (meals are offered to all participants). Please register no later than May 12th. If the registration form does not work, please e-mail
  • Monday, May 17th
    • 9:30 - 10:30 Srecko Brlek: Introduction
      • Basic properties on words; Lyndon factorizations; Fine and Wilf theorem; equations on words; Christoffel words; Coding of discrete figures in the square lattice.
    • 11:00 - 11:45 Luigi Santocanale: On the continuous weak Bruhat order
      • Words on a two letter alphabet can be seen as paths on the plane from the origin to the point (1,1) or as monotone step functions. The pointwise order on functions coincides with the weak Bruhat order on words. A first question arises : we can consider approximations of arbitrary monotone functions by step functions and, on the order theoretic side, the Dedekind-MacNeille completion of the weak Bruhat order (i.e. the usual construction of a complete lattice from a poset); how such a completion relates to monotone arbitrary functions? We can consider next words on more letter and mimic the previous considerations in higher dimensions. We can construct a weak Bruhat order an all these words by an inductive (co)-limit and complete these words by means of Dedekind-MacNeille. We can again interpret these words as paths in higher dimension cubes, yet the induced geometry still has to be understood.
    • 11:45 - 12:30 Thomas Fernique: Chaine de Markov et courbure discrète moyenne
    • 14:00 - 14:30 Gabriele Fici: On some constructions of words having a given Parikh vector
    • 14:30 - 15:30 Xavier Provençal: Discrete convexity (Slides)
      • Detection algorithms. Lyndon + Christoffel = Digitally convex.
    • 15:30 - 16:30 Annemiek Cornelissen
      • Blood vessel branching morphogenesis, growing a tree on a square grid.
  • Tuesday, May 18th
    • 9:30 - 10:30 Srecko Brlek: Words and tilings of the plane
    • 11:00 - 12:00 Xavier Provençal: Algorithmes linéaires pour le problème du pavage par translation (Slides)
    • 14:00 - 15:00 Thomas Fernique: Plans discrets et leur reconnaissance via fractions continues
    • 15:30 - 16:30 Gabriele Fici: Smooth tilings
  • Wednesday, May 19th
    • open problems and free discussion.

2.  Second seminar: June 7th-10th, 2010.

  • Registration for rooms and meals at CIRM is compulsory (meals are offered to all participants). Please register no later than June 3rd. If the registration form does not work, please e-mail
  • Monday, June 7th
    • 10:00 - 11:00 Anders Kock: Synthetic theory of geometric distributions
      • In the context of synthetic differential geometry (which will be explained), a geometric distribution is a reflexive symmetric relation which refines the canonical first-order neighbour relation on a manifold. There is a classical "Frobenius" integrability result giving conditions when such distribution can be glued together into "leaves".
    • 11:00 - 12:00 Luigi Santocanale: On the continuous weak Bruhat order (Suite)
    • 14:00 - 14:45 Christian Mercat: Surfaces de Riemann discrètes
    • 14:45 - 15:30 Damien Jamet: Sur la topologie des hyperplans discrets arithmétiques
    • 15:45 - 16:30 Bertrand Kerautret: Détection du bruit sur un contour discret à partir des segments maximaux
  • Tuesday, June 8th
    • 10:00 - 11:00 Sébastien Labbé: Sur le nombre maximal de façons de paver le plan par translation
      • Nous présenterons la solution d'une conjecture de Brlek, Dulucq, Fédou, Provençal (2007) énonçant qu'une tuile possède au plus deux factorisations en carré, ou autrement dit, qu'elle ne peut paver le plan en plus de deux manières distinctes en ayant quatre voisins. Ce travail est commun avec Alexandre Blondin Massé et Ariane Garon.
    • 11:00 - 12:00 Alexei Belov, Alexander Chernyatiev: Interval exchange transformations and substitutions.
    • 14:00 - 15:00 Frédéric Rieux: Diffusion digitale et estimateur de courbure
    • 15:30 - 16:30 Free spot: To be announced
  • Wednesday, June 9th
    • 10:00 - 11:00 Alexander Chernyatiev: Balanced words and symbolic dynamics
    • open problems and free discussion.
  • Thursday, June 10th
    • 10:00 - 11:00 Alexei Belov: Words obtained from values of polynomials in integer points
    • free discussion

3.  Uploaded slides


For any technical question or comment regarding this wiki, you can contact the wemaster.