Séminaire Ernest

Un sous-shift sur un groupe peut être vu comme l’espace des coloriages d’un graphe de Cayley de ce groupe, où l’on "colorie" les éléments du [...]

Les jeux positionnels sont une famille de jeux à deux joueurs incluant le tic-tac-toe, Hex ou encore Sim. Le plateau de jeu est un hypergraphe, i.e. la donnée d'un ensemble de sommets et un ensemble d'(hyper)arêtes qui sont des sous-ensembles de sommets. Tour à tour, Alice et Bob sélectionnent des sommets un par un, avec des objectifs dépendant de la convention choisie. Cet exposé traite de résultats récents sur la convention "Maker-Breaker" : le but d'Alice ("Maker") est de posséder tous les sommets d'une quelconque arête, tandis que le but de Bob ("Breaker") est de l'en empêcher. Comme il n'y a pas de partie nulle possible, seules deux issues sont possibles sur un hypergraphe donné : soit Maker a une stratégie gagnante, soit Breaker a une stratégie gagnante. Déterminer l'issue est un problème algorithmique difficile, qui est PSPACE-complet [Schaefer, 1978] même restreint aux hypergraphes dont toutes les arêtes sont de taille 6 [Rahman & Watson, 2021]. Nous étudions ce problème dans les hypergraphes dont toutes les arêtes sont de taille au plus 3 : nous y obtenons une caractérisation structurelle de l'issue du jeu, dont nous déduisons un algorithme de résolution en temps polynomial. Nous présentons également quelques résultats algorithmiques concernant une nouvelle version de ce jeu, où on ajoute sur l'ensemble des sommets un ordre partiel limitant les coups légaux, à la manière du Puissance-4.

Dans cet exposé, nous découvrirons des variantes de pseudo-métriques en utilisant des distances sur l'ensemble des mots finis, en élargissant les concepts des pseudo-métriques de [...]

Soient N ≥ 1 et χ1, ..., χN des caractères de Dirichlet primitifs, pairs et deux à deux distincts, de conducteur q1, ..., qN, respectivement. [...]

In a first part, we introduce the Markoff numbers, which are fascinating integers related to number theory, Diophantine equation, hyperbolic geometry, continued fractions and Christoffel [...]

Le polynôme de Fekete F_p  est le polynôme de degré p - 1 dont les coefficients (±1) sont les valeurs de du symbole de Legendre [...]