Centre International de Mathématiques Pures et Appliquées

Ecole CIMPA-UNESCO-PHILIPPINES

Rapport de Jose Maria Balmaceda

Rapport de Michel Jambu

Objectifs :

Dans les années 70, une contribution fondamentale de Philippe Delsarte a été une méthode de Combinatoire Algébrique qui procure des bornes sur la taille des codes correcteurs de distance minimale donnée comme solutions d’un problème de Programmation Linéaire. La méthode de Delsarte aussi connue sous le nom méthode polynomiale fut développée dans le cadre des Schémas d’association, qui est le cadre le plus général pour traiter les espaces métriques finis. Cette méthode donne aussi des bornes dans des situations plus générales comme des bornes sur la taille des designs (combinatoires ou sphériques). Elle permet de traduire des problèmes d’espaces métriques finis ayant de fortes propriétés de régularité/symétrie (comme le schéma de Hamming pour les codes ou le schéma de Johnson pour les designs) en problèmes spectraux d’algèbre linéaire. Lesdits problèmes peuvent s’approcher par des méthodes de fonctions spéciales en particulier certain des familles de polynômes orthogonaux en une variable discrète (Krawtchouk pour les codes, Hahn pour les designs) et leurs zéros extrémaux. L’algèbre de matrices pertinente dans ce cas est l’algèbre de Bose Mesner. Depuis les années 90 une autre algèbre est a la mode pour les schémas d’association : l’algèbre de Terwilliger. La Programation SemiDéfinie (abrégé SDP) constitue une famille de problèmes d’optimisation qui sont maintenant solvables en temps polynomial. De nouveaux algorithmes fondés sur des méthodes de point intérieur sont d’une efficacité raisonnable en pratique. SDP contient LP comme sous classe. Plus précisément un SDP peut se formuler la manière suivante soient A0,A1, . . . ,An des matrices réelles symétriques et b1, . . . , bn des réels. On cherche le minimum d’une fonction objectif b1x1 +. . .+bnxn sur l’ensemble convexe A0 + x1A1 + . . . + xnAn ≥ 0, o`u la notation A ≥ 0 signifie que les valeurs propres de A sont ≥ 0. L’approche SDP de certains problèmes d’optimisation combinatoire est connue depuis plusieurs décennies. les nouveaux algorithmes ont donné lieu à des relaxations solvables en temps polynomial de problèmes de calculs difficiles d’invariants de graphes comme le nombre de stabilité, la coloration, la coupe maximum.

Dans cette Ecole d’Eté on se concentrera sur les problèmes d’empilement de sphères qui ont bénéficié du passage de LP à SDP. Nous pensons que cette approche se révèlera féconde pour les jeunes chercheurs d’aujourd’hui.

Organisateurs :

Christine Bachoc (Université de Bordeaux I, France), William Martin ( Worcester Polytechnic Institute, USA), Patrick Solé (CNRS, Nice, France)

Organisateur local :

Jose Maria “Joey” Balmaceda (UP, Manille, Philippines)

Langue de travail :

Anglais

Date et lieu :

20-31 juillet 2009, Université des Philippines, Manille, Philippines

Programme scientifique : (résumés de cours)

 Christine Bachoc (Bordeaux I, France) : Applications des polynômes orthogonaux à plusieurs variables
 Eiichi Bannai (Kyushu University, Japon) : Etat de l’art des designs sphériques
 Henry Cohn (Microsoft Research, USA) : Distribution de points sur les sphères
 William Martin (Worcester Polytechnic Institute, USA) : Programmation linéaire et énumérateur des poids double
 Frank Vallentin (CWI, Amsterdam, Pays-Bas) : Applications de programmation semidéfinie

Prérequis :

Maîtrise de Math ou d’Informatique

Date limite d’inscription :

30 avril 2009

Modalité d’inscription et Inscription en ligne uniquement pour les non locaux.

Les inscriptions des candidats des Philippines doivent se faire localement. Personne à contacter : Jose Maria “Joey” Balmaceda (joey@math.upd.edu.ph)

Un forum dédié à cette école est ouvert au bas de la page web suivante : http://www.cimpa-icpam.org/spip.php?article143&lang=en