Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Graphs, ALgorithms and Combinatorics
Computing the growth rate of the number of patterns in a tiling
Benjamin Hellouin

22 December 2017, 14:30
Salle/Bat : 455/PCRI-N
Contact :

Activités de recherche : Combinatorics

Résumé :
Les pavages correspondent à des coloriages d'une grille (Z ou Z^d) qui obéissent à des contraintes locales. Compter ou énumérer les coloriages admissibles de sous-ensembles finis est une question combinatoire naturelle, et le taux de croissance de ce nombre correspond à une notion d'entropie qui apparait en systèmes dynamiques, en physique statistique et en théorie de l'information. Peut-on calculer algorithmiquement ce taux de croissance, étant donné en entrée une description des contraintes locales ?

Pour des contraintes en nombre fini et en dimension 1, l'entropie est calculable par une méthode algébrique classique. Le cas de la dimension supérieure s'est révélé beaucoup plus difficile, et beaucoup d'exemples simples restent ouverts. En 2007, il a été prouvé que l'entropie n'est pas calculable en dimension 2. Des travaux plus récents ont montré que l'entropie redevient calculable sous des hypothèses de mélange, une forme d'indépendance des motifs assez éloignés. Où se situe la limite entre les cas calculable et incalculable ?

En introduisant une notion de taux de mélange, nous montrons l'existence d'un seuil où la difficulté du problème passe de calculable à incalculable, sans pouvoir le déterminer exactement. Pour une famille plus large de pavages soumis à un nombre infini de contraintes, nous parvenons à déterminer exactement la position du seuil, et conjecturons que la situation est la même dans le cas fini.

Ces travaux sont en collaboration avec Silvère Gangloff.

Pour en savoir plus :
Séminaires
Some recent results on the integer linear programm
Graph Theory
Friday 30 November 2018 - 00:00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

De la sociologie *avec* des algorithmes à la socio
Friday 09 November 2018 - 14:30
Salle : 445 - PCRI-N
Christpohe Prieur .............................................

Initiation à la programmation GPU
Compilation and code optimization
Monday 05 November 2018 - 09:30
Salle : 455 - PCRI-N
Joël Falcou / Patrick Amar .............................................

Maximum Independent Set in H-free graphs
Graph Theory
Friday 05 October 2018 - 14:30
Salle : 445 - PCRI-N
Edouard BONNET .............................................

A Family of Tractable Graph Distances
Web data management
Wednesday 04 July 2018 - 10:30
Salle : 465 - PCRI-N
Stratis Ioannidis .............................................