Séminaire Ernest

La complexité locale finie est la propriété d'un sous-shift de pavages géométriques qui permet d'énumérer les motifs locaux et donc de considérer les problèmes de [...]

In 1980 Montgomery made a conjecture about the true order of the error term in the prime number theorem. In the early 1990's Gonek made [...]

De tout temps, femmes et hommes ont aspiré à des nano-colifichets en ADN. Depuis les années 1990, dans la suite des travaux séminaux de Reif, [...]

Cette présentation offrira un aperçu de résultats explicites en théorie des nombres, en commençant par une série de théorèmes sur les régions sans zéros et [...]

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.