Doctorat
Equipe : Graphes, Algorithmes et Combinatoire
Classification des groupes P-oligomorphes, conjectures de Cameron et Macpherson
Début le 01/01/1970
Direction : THIÉRY, Nicolas
Ecole doctorale : ED STIC 580
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : l'amphithéâtre DIGITÉO du bâtiment CLAUDE SHANNON
Soutenue le 29/11/2019 devant le jury composé de :
Rapporteurs :
Peter Cameron (Queen Mary Univ. of London & Univ. of Saint Andrews)
Pascal Weil (CNRS, Université de Bordeaux)
Jury :
Peter Cameron (Queen Mary Univ. of London & Univ. of Saint Andrews)
Pascal Weil (CNRS, Université de Bordeaux)
Isabelle Guyon (Université Paris Sud)
Maurice Pouzet (Université Claude Bernard Lyon I)
Christophe Tollu (Université Paris-Nord)
Annick Valibouze (Sorbonne Universités)
Nicolas Thiéry (Université Paris Sud)
Activités de recherche :
Résumé :
Étant donné un groupe de permutation infini G, on définit la fonction qui à
tout entier naturel n associe le nombre d'orbites de sous-ensembles de
cardinal n, pour l'action induite de G sur les sous-ensembles d'éléments.
Cameron a conjecturé que cette fonction de comptage (le profil de G) est
équivalente à un polynôme si elle est bornée par un polynôme.
Une autre conjecture, plus forte, a été émise plus tard par Macpherson.
Elle concerne une certaine structure d'algèbre graduée sur les orbites
de sous-ensembles, créée par Cameron, et suppose que si le profil de G est
polynomial, alors son algèbre des orbites est de type fini.
Le résultat central de la thèse est une classification des groupes de
profil borné par un polynôme (à clôture près), qui apporte une compréhension
profonde de ces groupes et démontre en particulier les deux conjectures.
En fournissant un encodage fini de ces groupes infinis, la classification
en permet aussi une approche algorithmique et un modèle naturel
d'implémentation pour ces groupes.
Les méthodes utilisées impliquent en particulier l'étude du treillis des
systèmes de blocs, l'exploration informatique de certaines parties du
problème, ainsi que des outils de formalisation issus de la théorie des groupes.
