Sujet de stage de M2

Titre : Mots 2-équilibrés

Encadrants : Thierry Monteil et Gwénaël Richomme

Parcours : CASAR ou Math-Info ou Mathématiques fondamentales

Description :

On peut approcher une courbe dessinée sur un quadrillage par les cases qu'elle rencontre (c'est par exemple le cas lorsqu'on veut tracer une courbe sur un écran d'ordinateur). La précision augmente lorsque le maillage du quadrillage diminue.

On peut coder cette représentation comme suit : lorsque la courbe croise le quadrillage selon une verticale, on écrit un "0", lorsqu'elle le croise selon une horizontale, on écrit un "1" (on néglige les cas ou la courbe rencontre un coin). On obtient ainsi un mot binaire, qui permet de dessiner la trace de la courbe sur le quadrillage de proche en proche.

Le cas des segments est particulièrement bien connu et on sait caractériser combinatoirement les mots binaires obtenus : ce sont exactement les mots dits 1-équilibrés, c'est-à-dire les mots w tels que si u et v sont deux sous-mots de w de même longueur, alors le nombre de "0" apparaissant dans u et le nombre de "0" apparaissant dans v diffèrent d'au plus 1. On peut comprendre la notion d'équilibre comme la constance de la pente de la courbe (la pente correspond au rapport entre le nombre de "1" et le nombre de "0" apparaissant dans le mot considéré).

Par exemple le segment SegmentGrille.png est codé par le mot "001000100100", et sa pente vaut à peu près 1/3.

On peut généraliser cette notion en définissant les mots c-équilibrés : ce sont les mots w tels que si u et v sont deux sous-mots de w de même longueur, alors le nombre de "0" apparaissant dans u et le nombre de "0" apparaissant dans v diffèrent d'au plus c.

Le but de ce stage est d'étudier plus en détails les mots 2-équilibrés. En particulier, on s'attaquera aux problèmes suivants :

Bibliographie :

L'étudiant-e pourra commencer par une étude bibliographique des propriétés connues d'équilibre sur les mots en commençant par exemple par :

Remarques :

Ce sujet est complémentaire d'un sujet sur les cercles discrets, mais nous ne pourrons encadrer qu'un-e étudiant-e au total.