Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 10 mars 2015 à 14h00 en B107, Sébastien Labbé nous parlera de : Une généralisation des mots de Christoffel en dimension d.

Résumé : In this work, we extend the definition of Christoffel words to directed subgraphs of the hypercubic lattice in arbitrary dimension that we call Christoffel graphs. Christoffel graphs when d=2 correspond to well-known Christoffel words. We show that Christoffel graphs have similar properties to those of Christoffel words: symmetry of their central part and conjugation with their reversal. Our main result extends Pirillo's theorem (characterization of Christoffel words which asserts that a word amb is a Christoffel word if and only if it is conjugate to bma) in arbitrary dimension. In the generalization, the map amb\mapsto bma is seen as a flip operation on graphs embedded in Z^d and the conjugation is a translation. We show that a fully periodic subgraph of the hypercubic lattice is a translate of its flip if and only if it is a Christoffel graph. This is joint work with Christophe Reutenauer. Preprint is available at http://arxiv.org/abs/1404.4021.

 [Slides.pdf] [arXiv]


Dernière modification : jeudi 29 janvier 2015 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr