Jeudi 18 mai 2006, à 14h15.
Orateur : Lucile Denoeud.
Titre : Maximum de la distance de transfert entre deux partitions.
Transparents.

Résumé :
La distance de transfert est définie sur l'ensemble des partitions d'un ensemble fini X. Etant données deux partitions P et Q sur X, cette distance correspond au nombre minimum de transferts d'un élément d'une classe dans une autre (éventuellement vide) nécessaires pour transformer P en Q, ou réciproquement Q en P.
Cette distance fut tout d'abord introduite par S. Régnier en 1965 puis étudiée par Day (1981) qui montra que son calcul revient à la résolution d'un problème de couplage maximum de poids minimum dans un graphe biparti. Cette distance présente l'inconvénient de ne pas être normalisée. C'est en partie dans ce but que nous avons déterminé les valeurs extrémales de la distance de transfert sur différents ensembles de partitions.
Il est trivial de trouver le maximum d_max de la distance de transfert entre deux partitions quelconques de X : d_max = |X|-1 (c'est la distance entre la partition à une classe et la partition à |X| classes). Nous avons tout d'abord déterminé la distance maximum entre deux partitions dont les nombres de classes sont donnés ou majorés. Nous avons ensuite poursuivi cette étude en établissant le maximum de la distance de transfert à une partition P donnée et le maximum de la distance de transfert entre une partition P donnée et une partition dont le nombre de classes est donné ou majoré.
Nous présenterons ces résultats ainsi qu'une partie de leurs preuves.