Journée-séminaire de combinatoire

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

Le 03 mars 2020 à 14h00 en B107, Pascal Vanier nous parlera de : Points apériodiques dans les espaces de pavage bidimensionnels

Résumé : La théorie des espaces de pavages a été profondément façonnée par le résultat historique de Berger : un jeu de tuiles fini peut ne paver le plan que de manière apériodique. Ces points apériodiques sont au coeur de nombreuses directions de recherche du domaine, en mathématiques comme en informatique. Dans cette exposé, nous répondons aux questions suivantes en dimension 2 : 1. Quelle est la complexité calculatoire de déterminer si un jeu de tuiles (espace de type fini) possède un point apériodique ? 2. Comment se comportent les espaces de pavages ne possédant aucun point apériodique ? Nous montrons qu'un espace de pavage 2D sans point apériodique a une structures très forte : il est "équivalent" (presque conjugué) à un espace de pavage 1D, et ce résultat s'applique aux espaces de type fini ou non. Nous en déduisons que le problème de posséder un point apériodique est co-récursivement-énumérable-complet, et que la plupart des propriétés et méthodes propres au cas 1D s'appliquent aux espaces 2D sans point apériodiques. La situation en dimension supérieure semble beaucoup moins claire. Cet exposé est issu d'une collaboration avec Anael Grandjean et Benjamin Hellouin de Menibus.


Dernière modification : Monday 18 March 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr