Thème 1 : Mathématiques Discrètes

Le domaine de prédilection des recherches en mathématiques concerne les mathématiques discrètes et plus spécifiquement la théorie des graphes et la géométrie combinatoire. Une problématique de recherche commune à ces domaines est les problèmes d’empilement et de recouvrement dans les graphes. Etant donné un entier r, un r-code couvrant dans un graphe est un sous ensemble C de sommets tel que tout sommet est à distance inférieure ou égale à r d’un élément de C. Autrement dit, c’est un problème de recouvrement par des boules sur la structure discrète, graphe. L’existence d’un tel recouvrement est toujours garantie (il suffit de prendre l’ensemble des sommets pour C). Le problème d’optimisation combinatoire associé à cette notion est donc de déterminer la plus petite cardinalité d’un tel code. Dans le cas r = 1, cette problématique est connue en théorie des graphes sous le vocable d’ensemble dominant.

Une large bibliographie sur le sujet existe, à titre indicatif on peut consulter la monographie de Haynes, Hedetniemi et Slater (Domination in graphs. Advanced topics in Monographs and Textbooks in Pure and Applied Mathematics, 209). Parallèlement, sur des structures régulières telles que l’hypercube et le tore ce problème correspond au dual du problème de détermination d’un plus grand r-code correcteur d’erreur. Ce domaine des mathématiques discrètes est aussi largement étudié. Les outils développés dans ce cadre sont fortement basés sur la structure d’espace vectoriel induite par les métriques de Hamming et de Lee.

Dans le cadre de ce projet, on proposera une approche ”graphiste” sur ce problème. Par exemple, un objectif de ce travail pourrait être d’unifier les résultats concernant des métriques différentes : quels peuvent être les liens entre l’existence de codes couvrants en métrique de Lee et ceux en métrique de Hamming ? D’un point de vue graphe, ces questions qui peuvent paraître saugrenues prennent du sens. En effet, en dimension 1, la métrique de Lee est représentée par le cycle et la métrique de Hamming par le graphe complet. Ces deux graphes peuvent être vus comme des graphes de Cayley de Z/pZ ”extrêmaux”.

Que peut-on dire alors sur les graphes de Cayley intermédiaires ?

 Bien sûr, ce travail demandera un traitement assez systématique des familles de problèmes de recouvrement. On abordera les questions existentielles ainsi qu’algorithmiques. Un point de départ de ces investigations pourrait être le sujet récent introduit en 1998 par Karpovsky, Chakrabarty et Levitin dans [1] ; les codes identifiants. Un code identifiant C est un code couvrant particulier qui a la propriété suivante : pour tout couple de sommets x, y du graphe, on a Br (x) ∩ C ≠ Br (y) ∩ C (où Br (x) désigne la boule centrée en x de rayon r).

A l’origine, ces codes ont été introduits pour détecter des éléments défectueux : supposons qu’un sommet soit ”défaillant”, alors, en interrogeant chaque élément de C sur son voisinage, on peut trouver quel est ce sommet. En ce sens, même s’il ne corrige pas d’erreur, cette notion est proche des codes couvrants et des codes correcteurs. La bibliographie en ligne entretenue par A. Lobstein ([4]) montre que ce concept d’identification est au coeur de préoccupations actuelles dans la recherche en théorie des codes. Une variante récemment introduite est la version adaptative : supposons maintenant que les tests puissent être faits l’un après l’autre. Comment choisir les sommets à tester pour trouver l’élément défaillant le plus efficacement ?

Cette variante est particulièrement intéressante si l’on s’intéresse aux questions algorithmiques. Des premiers résultats ont été obtenus par l’équipe grenobloise ([2], [3]) et donnent des perspectives d’ouverture. La version adaptative des codes identifiants sur des structures ”unificatrices” (graphes de Cayley) semble être un point de départ intéressant pour aborder les problématiques de codes couvrants dans les graphes.

De plus, ces sujets sont au coeur de l’ANR IDEA (2009-2011 [5]) qui rassemble un groupe de chercheurs autour d’un tel projet. Ce thème s’inscrit donc dans un contexte national (et international) de tout premier plan. Il est à noter que la version adaptative des codes identifiants est un cadre qui permet d’étudier des problèmes pouvant inspirés des SR : problème de détection d’une fausse pièce parmi n pièces à l’aide d’une balance Roberval, recherche d’élément dans une structure discrète.

Références

[1] M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a New Class of Codes for Identifying Vertices in Graphs, IEEE Transactions on Information Theory 44(2), (1998), 599– 611.

[2] Y. Ben-Haim, S. Gravier, A. Lobstein, J. Moncel, Adaptive identification in torii in the king lattice, Electronic Journal of Combinatorics 18(1) P116 (2011).

[3] Y. Ben-Haim, S. Gravier, A. Lobstein, J. Moncel, Adaptive Identification in Graphs, J. Combin. Theory, Ser. A., 115 (2008), 1114 – 1126.

[4] http ://www.infres.enst.fr/lobstein/bibLOCDOMetID.html

[5] http ://idea.labri.fr/