*

Calcul efficace de géodésiques dans les graphes-associaèdra.

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

Concours pour un contrat doctoral

école doctorale

IAEM - INFORMATIQUE - AUTOMATIQUE - ELECTRONIQUE - ELECTROTECHNIQUE - MATHEMATIQUES

équipe

GAMBLE

contexte

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é

Informatique

laboratoire

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.