Pavages apériodiques de complexité « pas trop élevée »
Etienne Moutot
I2M, CNRS, Marseille
/user/etienne.moutot/
Date(s) : 03/06/2022 iCal
11h00 - 12h00
La conjecture de Nivat relie la complexité de motifs des pavages (le nombre de motifs rectangulaires de taille m x n y apparaissant) à leur périodicité: elle dit que tout pavage ayant une complexité inférieure à mn pour certains m,n, doit être périodique.
En cherchant à nous approcher de cette conjecture, nous avons réussi avec Jarkko Kari à démontrer que si un jeu de tuile de Wang ne produit que des pavages apériodiques, alors tous ces pavages ont une complexité d’au moins mn+1.
Dans cet exposé je ne vais pas vous parler de ce résultat, mais d’une question naturelle qui en découle: quelle est la complexité minimale que peut atteindre un jeu de tuiles apériodique ?
Je détaillerai une technique permettant d’encoder n’importe quel jeu de tuile de Wang en un autre, ayant une complexité « pas trop élevée ». En particulier, cela permet de construire un jeu de tuile de Wang apériodique ayant une complexité n² + f(n)n pour n’importe quelle fonction f non bornée.
Zoom:https://univ-amu-fr.zoom.us/j/81215649986?pwd=emtzMWw3Sk53cm5vdzFXcExlTUo1UT09
Meeting ID: 812 1564 9986
Passcode: voir mail
Emplacement
Saint-Charles - FRUMAM (2ème étage)
Catégories
