Liste des groupes Proposer un groupe Groupes finis

Groupe de Lecture et de Travail de l'équipe AMACC

SFT 1d : a graphical approach

Proposé par :Pascal
Résumé : Vous êtes allergiques aux degrés Turing, à la hiérarchie arithmetique, ou à des distinctions plus fines que décidable/indécidable, mais vous avez quand même envie d'entendre parler de sous-shifts, alors ce GLT est fait pour vous. Les SFTs 1d sont essentiellement des ensembles de chemins dans des graphes, nous parlerons de plusieurs notions de dynamique, ce qu'elles veulent dire sur les graphes et nous finirons par parler du problème de la conjugaison : LA notion d'isomorphisme pour les sous-shifts (mais on l'appelle pas comme ça parce qu'on est snobs), ce problème est décidable si l'on considère les SFTs sur N mais on ne sait pas pour les SFTs sur Z (et bien entendu c'est indécidable sur N^d, Z^d pour d>1).
Objectifs : faire plaisir à Paul et parler de graphes, faire plaisir à Pascal et parler de sous-shifts
Prérequis : Nada
Intéressés : Gaétan (4), Matthieu (5), Pascal (5), Paul (5)

Parameterized complexity

Proposé par :Paul
Résumé : Les problèmes FPT sont les problèmes où la partie exponentielle peut se restreindre à un paramètre k. Est-alors FPT tout problème qui admet un algo en O(f(k)n^(O(1)). Les problèmes ayant un algo en O(n^f(k)) sont eux dans la classe XP. Une hierarchie W existe entre FPT et XP, avec les problèmes de clique max dans W(1), de dominant min dans W(2), etc...
Objectifs : Le but est de consolider la connaissance de FPT/XP et de comprendre un peu une intuition de cette classification W.
Prérequis : Trouver qqn qui s'y connait pour donner l'intuition, parce que moi, je ne l'ai pas encore... (Ou alors, la trouver tous ensemble)
Intéressés : Gaétan (3), Julien D (3), Julieng (5), Pascal (3), Paul (4)

Démystifions les polynômes de Tutte

Proposé par :Julieng
Résumé : Récemment un papier clamait sur arXiv avoir reprouvé le théorème des quatre couleurs en mélangeant le polynôme de Tutte et les séries génératrices. Bon, bien sûr, le papier s'est avéré faux comme le visage d'Isabelle Adjani, mais une interrogation apparut au sein de l'équipe : c'est quoi le polynôme de Tutte au fait ? Il se trouve que pendant ma thèse, j'ai travaillé sur ce polynôme ! Incroyable. Pour la reprise de ce GLT, je vous dirai ce qu'il faut retenir sur ces polynômes, sans trop rentrer dans les détails.
Objectifs : Comprendre le polynôme de Tutte
Prérequis : walou
Intéressés : Julien (2), Julien D (3), Pascal (3), Paul (4)