10:45
11:45

Séminaire de Benjamin Hellouin : « Mélange dans Hom shifts / reconfiguration des chemins dans les graphes ».

Les Hom shifts sont une famille de sous-décalages bidimensionnels simples (règles de coloration de la grille Z^2) qui sont identiques dans toutes les directions, c'est-à-dire invariants par rotation et par symétrie. Cette restriction rompt avec les méthodes classiques d'intégration des calculs dans les sous-décalages, et les problèmes indécidables en général semblent devenir traçables, et peuvent généralement être reformulés en termes de graphes. Cet exposé porte sur la distance de collage dans les décalages de Hom : étant donné deux colorations partielles admissibles n x n, à quelle distance doivent-elles se trouver pour que nous puissions les coller ensemble dans une coloration plus grande ? Il s'avère que le problème peut être reformulé en termes de reconfiguration d'homomorphismes en théorie des graphes, et les preuves s'appuient sur des transformations de chemins dans les graphes qui peuvent être intuitivement considérées comme des homotopies, établissant un lien avec la topologie algébrique dans les graphes. Dans chaque exemple simple, cette distance est constante ou linéaire ; cependant, nous produisons un exemple plus élaboré avec une distance de collage logarithmique. Nous conjecturons que les distances constantes, linéaires et logarithmiques sont les trois seuls comportements possibles, et que cela constitue un argument pour que ces comportements soient "combinatoirement naturels" pour les sous-décalages généraux (en l'absence de calcul).
Ce travail est réalisé en collaboration avec Silvère Gangloff et Piotr Opocha.

Salle 178