Graphes et Polytopes Hypergraphes

Établissement : Université de Lorraine École doctorale : IAEM - INFORMATIQUE - AUTOMATIQUE - ELECTRONIQUE - ELECTROTECHNIQUE - MATHEMATIQUES Laboratoire de recherche : LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications, Ce sujet de thèse propose d'étudier les propriétés structurelles et algorithmiques des polytopes hypergraphiques et de certaines de leurs sous-classes, notamment les associaèdres de graphes et les polytopes associés aux graphes et aux hypergraphes géométriques.

Nous souhaitons explorer comment les propriétés structurelles des hypergraphes sont liées aux propriétés combinatoires de leurs polytopes hypergraphiques, telles que les distances, les diamètres et l'hamiltonicitée. Nous accorderons une attention particulière aux graphes et à leurs associaèdres, ainsi qu'aux graphes et aux hypergraphes géométriques.

L'un des principaux problèmes combinatoires liés aux polytopes à n dimensions consiste à trouver le chemin le plus court entre deux sommets d'un graphe formé par les sommets et les arêtes du polytope, la longueur du chemin étant définie par le nombre de ses arêtes. L'estimation de la longueur de ces chemins fait l'objet de recherches intensives depuis les débuts de la théorie de la programmation linéaire et l'invention par Dantzig, vers 1947, de l'algorithme du simplexe, qui cherche des solutions à un programme linéaire en passant de manière itérative d'une solution viable à une autre, le long des arêtes du polytope. Une classe importante de polytopes convexes sont les polymatroïdes qui sont construits à partir de fonctions sous-modulaires [9]. Les polytopes hypergraphiques et les associaèdre des graphes sont de polymatroïdes. Du point de vue de l'optimisation, il s'agit de polytopes qui généralisent les polytopes de base des matroïdes, tout en conservant la propriété selon laquelle les sommets extrêmes par rapport à une fonction linéaire peuvent être facilement identifiés à l'aide d'un algorithme glouton [9, 5]. Les polymatroïdes constituent donc une classe de programmes linéaires qui peuvent être résolus en temps fortement polynomial.

Récemment, Cardinal et Steiner ont montré que le problème du chemin le plus court sur les polytopes hypergraphiques est APX-difficile et ont fourni un algorithme d'approximation en temps polynomial pour ce problème, où le facteur d'approximation est le degré de code maximal de l'hypergraphe [2]. Une famille spécial des polytopes hypergraphiques sont les associèdra de graphes. Les associahedra de graphes constituent des représentations naturelles des relations d'adjacence entre des structures combinatoires telles que les permutations, les partitions, les triangulations ou les arbres, générées par des opérations réversibles et locales appelées « flips ». Ces polytopes convexes sont étudiés dans de nombreuses applications en informatique, par exemple en optimisation [7], dans les systèmes de visualisation hiérarchique [10], dans la génération de structures aléatoires [4], ainsi que pour l'étude de modèles probabilistes [8]. Un des problèmes plus intéressants est celui du calcul des géodésiques entre sommets de ce polytope. Il a été démontré [6] que le problème de décision correspondant est NP-complet en général, mais qu'il peut être résolu en temps polynomial lorsque le graphe d'entrée est un graphe 'split' complet [1]. Dans un article très récent [3], il est démontré que ce problème est FPT pour tous les associaèdre des graphes.

• Algorithmes d'approximation pour les problèmes de distance dans les (classes de) polytopes hypergraphiques.
• Estimations du diamètre des polytopes hypergraphiques.
• Conditions nécessaires et suffisantes pour déterminer si un associaèdre de graphe ou, plus généralement, un polytope hypergraphique, possède la propriété que toutes ses geodesiques restent toujours sur une face commune.

Titulaire d'un master 2 ou équivalent.Solide connaissance en théorie algorithmique de graphes, combinatoire et géométrie discrète. ","identifier":{"@type":"PropertyValue","name":"Doctorat.Gouv.Fr","value":"b44c7ccd842edaffe23b5400995229b0"},"url":"https://www.hellowork.com/fr-fr/emplois/77476864.html","datePosted":"2026-03-31T20:09:39Z","directApply":false,"educationRequirements":{"@type":"EducationalOccupationalCredential","credentialCategory":"postgraduate degree"},"employmentType":["TEMPORARY","FULL_TIME"],"experienceRequirements":"no requirements","hiringOrganization":{"@type":"Organization","name":"Doctorat.Gouv.Fr"},"industry":"Service public d'état","jobLocation":{"@type":"Place","address":{"@type":"PostalAddress","addressCountry":"FR","addressRegion":"Champagne-Ardenne"}},"qualifications":"Titulaire d'un master 2 ou équivalent. Solide connaissance en théorie algorithmique de graphes, combinatoire et géométrie

Direction de la thèse : Mario VALENCIA Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-08T23:59:59

{"@context":"https://schema.org","@type":"JobPosting","title":"Thèse Proprietes Combinatoires et Algorithmiques des Associaèdra des Graphes et Polytopes Hypergraphes H/F","description":"