Résumé: 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.