Pascal Vanier

Points apériodiques dans les espaces de pavage bidimensionnels

Salle de séminaire (4B125) - Bâtiment Copernic

Abstract: 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 c r 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.