Offre de thèse
Calcul efficace de géodésiques dans les graphes-associaèdra.
Date limite de candidature
01-05-2025
Date de début de contrat
01-10-2025
Directeur de thèse
VALENCIA Mario
Encadrement
Cette thèse sera encadrée par Mario VALENCIA dans l'équipe Gamble (LORIA, Inria). Les modalités d'encadrement sont celles de l'Ecole Doctorale IAEM-Lorraine. Le candidat aura une réunion hebdomadaire pour évaluer l'évolution de son travail et participera dans les séminaires de l'équipe.
Type de contrat
école doctorale
équipe
GAMBLEcontexte
Les objectifs de cette thèse visent à comprendre la structure combinatoire des graphes-associaèdra et à développer des algorithmes (FPT) efficaces pour le calcul de géodésiques dans ces graphes. De manière générale, un polytope convexe possède la propriété dite «non-leaving-face», si toute géodésique entre deux sommets du polytope restent toujours sur la face minimal qui leur contient. L'associèdre a cette propriété [SST88]. Cette propriété est fondamentale pour établir des bornes sur le diamètre de l'associèdre, et dans la conception d'algorithmes FPT pour le calcul des courtes séquences de flips des triangulations d'un polygone convexe [Luc10]. On désire étudier cette propriété et ses conséquences algorithmiques sur les graphes-associèdra.spécialité
Informatiquelaboratoire
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Mots clés
polytopes convexes, associaèdra des graphes, distances, algorithmes FPT
Détail de l'offre
Les graphes-associèdra constituent des représentations naturelles de relations d'adjacence entre des structures combinatoires telles que les permutations, les partitions, les triangulations ou les arbres, engendrées par des opérations réversibles et locales appelées flips. Il est connu que tous les graphes-associaèdra sont le 1-squelette d'un polytope [Dev09]. Ces graphes sont étudiés dans le cadre de nombreuses applications en informatique, par exemple en optimisation [KLS10], dans des systèmes de visualisation hiérarchique [SSV18], de génération de structures aléatoires [DPR20], ainsi que pour l'étude de modèle probabilistes [MUWY18]. La géométrie des graphes-associaèdra et en particulier la mesure des distances, jouent un rôle important dans le cadre de ces applications.
Malgré cela, la géométrie des graphes-associèdra est encore mal comprise. Un des problemes principal dans cette thematique de recherche et la complexité computational du calcul de géodesiques dans l'associaèdre.
Le diamètre d'un des graphes-associaèdra les plus utilisés, l'associaèdre, est connu [Pou14] mais aucun algorithme n'est disponible qui permette de calculer les distances dans ce graphe de manière efficace. Récemment, il a eu des avances dans ce qui concerne le calcul du diamètre et les distances de certains graphes-associaèdra [CPV22, CPV24].
Keywords
Convex polytopes, graph-associahedra, distances, FPT algorithms
Subject details
Graph-associahedra are natural representations of adjacency relations between combinatorial structures such as permutations, partitions, triangulations or trees, generated by reversible, local operations known as flips. It is known that all graph-associahedra are the 1-skeleton of a polytope [Dev09]. These graphs are studied in numerous applications in computer science, for example in optimization [KLS10], in hierarchical visualization systems [SSV18], in the generation of random structures [DPR20], as well as for the study of probabilistic models [MUWY18]. The geometry of graph-associahedra, and in particular the computation of distances, plays an important role in these applications. Despite this, the geometry of graph-associahedra is still poorly understood. A major problem on this area, in which we work, is the complexity of computing geodesics on the associahedra. The diameter of one of the most widely used graph-associahedra, the associahedron graph, is known [Pou14], but no algorithm is available to compute distances in this graph efficiently. Recently, there have been advances in calculating the diameter and distances of some graph-associahedra [CPV22, CPV24]. proposition-proposal-thesis-2025.pdf (26991)
Profil du candidat
Titulaire d'un master 2 ou équivalent en informatique théorique ou mathématiques discrètes.
Solide connaissance en théorie de graphes et combinatoire et, si possible, en géométrie combinatoire.
Candidate profile
Master 2 or equivalent in theoretical computer science or discrete mathematics.
Solid knowledge on graph theory and combinatorics and, if possible, combinatorial geometry.
Référence biblio
[CPV22] J. Cardinal, L. Pournin, M. Valencia-Pabon, Diameter estimates for graph associahedra, Annals of Combinatorics 26(4), 873–902 (2022)
[CPV24] J. Cardinal, L. Pournin, M. Valencia-Pabon, The rotation distance of brooms, European J. of Combinatorics 118, 103877 (2024)
[DPR20] J. David, L. Pournin, R. Rakotonarivo, Elementary moves on lattice polytopes, J. of Combinatorial Theory A 172, 105200 (2020)
[Dev09] S. L. Devadoss, A realization of graph associahedra. Discrete Mathematics, 309(1):271–276, 2009
[KLS10] M. J. van Kreveld, M. Löffler, R. I. Silveira : Optimization for first order Delaunay triangulations. Comput. Geom. 43(4) : 377-394 (2010).
[Luc10] J. M. Lucas, An improved kernel size for rotation distance in binary trees, Information Processing Letters, 110 (2010) 481–484.
[MUWY18] F. Mohammadi, C. Uhler, C. Wang, and J. Yu : Generalized Permutohedra from Probabilistic Graphical Models. SIAM J. Discrete Math., 32(1), 64-93 (2018).
[Pou14] L. Pournin, The diameter of associahedra, Advances in Mathematics 259 :2014, 13–42.
[SSV18] M. Sondag, B. Speckmann, K. Verbeek : Stable Treemaps via Local Moves. IEEE Trans. Vis. Comput. Graph. 24(1) : 729-738 (2018).
[STT88] D. Sleator, R. Tarjan, and W. Thurston. Rotation distance, triangulations, and hyperbolic geometry. J. Amer. Math. Soc., 1(3):647–681, 1988.