Sujet de stage de recherche - Master informatique

  • titre: Fonction Theta des graphes circulants
  • Responsable: Arnaud Pêcher (professeur)
  • Téléphone : 05 40 00 60 78
  • e-mail: pecher@labri.fr
  • Équipe: Combinatoire et Algorithmique
  • Thème : Graphes et applications
  • Equipe INRIA: RealOpt

Présentation du sujet :

La fonction Theta de Lovasz constitue la base de plusieurs résultats majeurs en théorie des graphes. Bien qu'elle soit calculable en temps polynomial pour tout graphe, des formules explicites sont connues pour un nombre très limité de familles de graphes seulement. Nous avons réussi récemment à donner une formule close pour la famille des puissances de cycles, une famille élémentaire de graphes circulants. La preuve exploite des domaines variés des mathématiques (programmation linéaire, méthodes numériques, analyse complexe, théorie algébrique des nombres, etc). L'objet de ce stage est, en s'inspirant de cette preuve, d'essayer de donner des formules closes pour d'autres familles de graphes circulants.

Le stage sera effectué au sein du thème "Graphes et applications" du LaBRI (https://graphesetapplications.labri.fr/) et de l'équipe INRIA RealOpt (https://wiki.bordeaux.inria.fr/realopt/).

Article associé: Bachoc, Pêcher, Thiery, On the theta number of powers of cycle graphs