Séminaire du LIM (LIF et LSIS)
Mardi 6 février à 14h - Luminy, Salle 304-306 à l'IML (bât TPR2 3e étage)
Maurice Nivat
Liafa, Jussieu, Paris 7
Suites bidimensionnelles et pavages du plan
On démontre que si le nombre de sous matrices mxn extraites d'une suite bidimensionnelle sur 0,1 est inférieur ou égal au produit mn alors la suite double est invariante par une translation. En fait ou bien cette translation t est inscrite dans les sous matrices extraites ou bien l'ensemble des sous matrices extraites est l'ensemble de toutes les matrices mxn dont un et un seul élément est égal à 1 (resp égal à 0) ; dans ce dernier cas on démontre que l'ensemble des rectangles mxn qui ont un 1 dans leur case 1,1 (en haut à gauche) pave le plan, et l'existence de la translation résulte alors d'un théorème de Beauquier-Nivat sur les pavages du plan par translations d'une pièce. Ce résultat est susceptible de généralisation à des vues d'une suite 2D à travers des fenêtres autres que rectangulaires.
Travail effectué en collaboration avec Laurent Vuillon.
Équipe Algorithmique et Combinatoire du Liafa : http://www.liafa.jussieu.fr/eqalco.html