Réunion ANR Magnum Jeudi 4 Octobre 2012

- 10h exposé Julien David
- 11h discussion sur la plate forme logicielle et des journées sage et programme à venir
- 12h30 buffet
-14h30 exposé Anne Micheli
- 15h30 session ouverte de questions et discussions
—————
“Une étude en moyenne des hypergraphes et de leur transversaux minimaux”
J. David (en collaboration avec L. Lhote, A. Mary, F. Rioult)

Résumé:
“Dans cet exposé, on s’intéressera à certaines propriétés des hypergraphes
et à la complexité moyenne d’algorithmes appliqués aux hypergraphes sous
plusieurs modèles de probabilité.
Notre approche est à la fois théorique et expérimentale puisque notre objectif
est d’obtenir un modèle aléatoire capable de capturer la complexité de données
réelles.

Partant d’un modèle généralisant celui d’Erdös-Renyi, nous avons obtenus
des estimations asymptotiques sur le nombres de transversaux, de minimaux
et de transversaux minimaux d’un hypergraphe aléatoire.
On utilise ces résultats pour obtenir la complexité moyenne des algorithmes
de génération des transversaux minimaux d’un hypergraphe.

Dans un deuxième temps, on complexifie notre modèle aléatoire afin
de s’approcher de données réelles.
Les résultats obtenus sont moins précis mais nous avons pu identifier
des cas où le nombre de transversaux minimaux est au plus polynomial,
quasi-polynomial ou exponentiel.

L’exposé se terminera par des réflexions personnelles et encore
inachevées sur les questions de génération aléatoire et d’analyse
pour des modèles non-uniformes.”

————

Minimiser les tresses à 4 brins
Anne Micheli – LIAFA

Une tresse à n brins correspond à l’idée intuitive que l’on se fait d’une tresse, c’est-à-dire n brins dont les extrémités sont fixes et qui se croisent entre
eux. Les tresses forment un groupe, noté Bn, engendré par n-1 générateurs vérifiant des relations. Une tresse peut être représentée par un diagramme de
tresse, c’est-à-dire une suite de croisements entre les brins de la tresse, chaque générateur correspondant à un croisement de deux brins. Ainsi un
représentant de longueur minimale d’une tresse est un diagramme parmi les diagrammes représentant la tresse, dont le nombre de croisements est minimal. Le
problème de minimisation d’une tresse consiste à exhiber un tel représentant de la tresse ou au moins à calculer sa longueur. Lorsque les tresses sont
positives, on connait leur série génératrice qui est rationnelle. Dans B3, il existe des algorithmes polynomiaux pour résoudre le problème de
minimisation. Mais pour n>3, aucun algorithme polynomial n’est connu à ce jour. On sait par contre que le problème est NP-complet pour n quelconque. Je
présenterai un algorithme polynomial pour résoudre le problème dans B4 dont la correction est prouvée moyennant une conjecture très simplement énonçable.
Ce travail a été effectué en collaboration avec Jean Mairesse (LIAFA) et Dominique Poulalhon (LIX).

This entry was posted in Accueil, Conférences. Bookmark the permalink.

Leave a Reply