Habilitation à diriger des recherches

From Jean Fromentin
Jump to: navigation, search

Titre : Combinatoire algébrique expérimentale

Jury

- Shalom Eliahou

- Loïc Foissy

- Eddy Godelle

- Florent Hivert

- Jean-Christophe Novelli

- Luis Paris

- Mathieu Picantin

- Jorge Ramíres Alfonsín

Résumé

L'expérimentation sur machine pour la combinatoire algébrique devient incontournable. Elle permet par exemple de construire des objets mathématiques ayant certaines propriétés souhaitées ou encore de conjecturer certains phénomènes qu'elle seule aura permis de voir émerger. Cette approche est à l'origine des différents travaux présentés ici, portant sur la théorie des tresses et des n\oe uds, la combinatoire additive et la théorie de Ramsey.

La forme normale tournante est définie sur le monoïde de Birman-Ko-Lee et possède de bonnes propriétés vis-à-vis de l'ordre des tresses. Elle permet de sélectionner un unique mot, dit tournant, parmi tous les mots représentant une tresse donnée. Nous montrons alors que l'ensemble des mots tournants forme un langage rationnel.

Depuis les travaux de F.A. Garside, nous savons que toute tresse positive peut être décrite comme une suite finie de permutations. Grâce à la caractérisation locale de telles suites, nous obtenons que leur combinatoire est obtenue à partir d'une certaine matrice d'adjacence. Dans le cas classique, correspondant aux groupes de Coxeter de type A, il a été montré que le polynôme caractéristique de la matrice de rang $n$ divise celui de rang $n+1$. Nous montrons un résultat analogue pour les tresses de type B en utilisant l'algèbre de Hopf des permutations signées.

Le polynôme de Jones est un invariant des entrelacs. Nous savons depuis 2003 qu'il existe une infinité d'entrelacs non triviaux avec au moins deux composantes qui ne sont pas détectés par le polynôme de Jones. Cependant le cas des entrelacs à une seule composante, correspondant aux n\oe uds, est toujours ouvert. Nous montrons qu'il existe une infinité de n\oe uds premiers non triviaux admettant un polynôme de Jones trivial modulo n'importe quelle puissance donnée de~$2$.

Les semigroupes numériques sont des sous-ensembles des entiers naturels stables par addition, contenant $0$ et de complément fini. L'ensemble des semigroupes numériques peut être décrit à l'aide d'un arbre infini. Dans cet arbre les semigroupes numériques à distance $g$ de la racine sont tous les semigroupes de genre $g$, c'est-à-dire ayant un complément de cardinal $g$. En 2008, M. Bras-Amor\'os a formulé trois conjectures sur la suite $n_g$ des semigroupes numériques à distance $g$ de la racine de l'arbre. Nous montrons que l'une de ces conjectures est satisfaite pour les semigroupes numériques \emph{génériques}, dont la proportion parmi les semigroupes numériques de genre $g$ tend vers $1$ avec $g$. Nous décrivons aussi un algorithme exploitant les capacités vectorielles des processeurs modernes afin d'explorer efficacement l'arbre des semigroupes numériques. Nous avons ainsi obtenu que le nombre de semigroupes numériques de genre $70$ est $1\,607\,394\,814\,170\,158$. Une des plus célèbres conjectures sur les semigroupes numériques est sans doute celle de Wilf. Depuis les travaux de S. Eliahou, nous savons que la conjecture de Wilf est satisfaite par les semigroupes génériques, la démonstration revient essentiellement à montrer qu'une certaine quantité $W_0$ est positive pour tous les semigroupes génériques. Nous montrons ici que dans le cas des semigroupes numériques non génériques il est possible d'obtenir une valeur négative de $W_0$ aussi petite que l'on souhaite.

Finalement, nous montrons qu'il n'existe pas de coloriage morphique à deux ou trois couleurs évitant les triplets pythagoriciens monochromatiques et nous montrons comment une exploration arborescente de Monte-Carlo imbriquée nous permet de construire une partition faiblement de Schur en $6$ couleurs de longueur $582$, qui est le record actuel.

Dernière version du mémoire