Familles d'intersection des ensembles et leur relation avec les graphes-associaèdra

Offre de thèse

Date limite de candidature

16-05-2024

Date de début de contrat

01-10-2024

Directeur de thèse

VALENCIA Mario

Encadrement

Le doctorant aura des reunions hebdomadaires avec son directeur pour verifier le bon avancement de son travail et/ou discuter des éventuels problèmes trouvés (techniques, administratives, etc). Le suivi de la formation et avancement se feront en respectant les consignes de l'école doctorale IAEM de l'Université de Lorraine.

Type de contrat

Concours pour un contrat doctoral

Candidater à cette offre target="_blank"

école doctorale

IAEM - INFORMATIQUE - AUTOMATIQUE - ELECTRONIQUE - ELECTROTECHNIQUE - MATHEMATIQUES

équipe

GAMBLE

contexte

Les graphes de familles d'intersection d'ensembles sont des objets bien étudiés en combinatoire. Un exemple sont les graphes de Kneser ayant par ensemble de sommets tous les sous-ensembles d'une même cardinalité d'un ensemble donné, et où deux sommets sont reliés par une arête si leur intersection est vide. Dans un article très populaire et important, Lovasz [Lov78] résout un problème de nature combinatoire des graphes de Kneser en utilisant des techniques de topologie algébrique en créant ainsi un ponte entre ces théories mathématiques. Les graphes de Schrijver [Sch78] sont de sous-graphes de graphes de Kneser induits par des familles d'ensembles n'ayant pas d'éléments consécutifs (on suppose qu'il s'agit d'ensembles d'entiers positifs). Un autre exemple sont les graphes de Johnson lesquels sont similaires aux graphes de Kneser mais où deux sous-ensembles (i.e. deux sommets) sont reliés entre eux uniquement si la cardinalité de leur différence symétrique est égale à 2. 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. 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].

spécialité

Informatique

laboratoire

LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

Mots clés

familles d'intersection d'ensembles, graphes-associaèdre, polytopes

Détail de l'offre

Les graphes de familles d'intersection d'ensembles sont des objets bien étudiés en combinatoire. Un exemple sont les graphes de Kneser ayant par ensemble de sommets tous les sous-ensembles d'une même cardinalité d'un ensemble donné, et où deux sommets sont reliés par une arête si leur intersection est vide. Dans un article très populaire et important, Lovasz résout un problème de nature combinatoire des graphes de Kneser en utilisant des techniques de topologie algébrique en créant ainsi un ponte entre ces théories mathématiques.
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. Ces graphes sont étudiés dans le cadre de nombreuses applications en informatique, par exemple en optimisation, dans des systèmes de visualisation hiérarchique, de génération de structures aléatoires, ainsi que pour l'étude de modèle probabilistes. 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. Le diamètre d'un des graphes-associaèdra les plus utilisés, l'associaèdre, est connu mais aucun algorithme n'est disponible qui permette de calculer les distances dans ce graphe de manière efficace.
Les objectifs de cette thèse visent à comprendre la structure combinatoire des graphes-associaèdra et leur relation avec des familles d'intersection d'ensembles. En effet, d'une part il n'est pas difficile de construire une certaine famille d'intersections d'ensembles contenant le graphe associaèdre. D'une autre part, le complexe simplicial de voisinages associé à une autre type de famille d'intersection d'ensembles contient le 1-squelette de l'associèdre comme un rétracte déformé. Nous voulons étendre d'avantage de telles relations entre ces deux objects combinatoires.

Keywords

intersecting families of sets, graph-associahedra, polytopes

Subject details

Graphs of intersecting families of sets are well-studied objects in combinatorics. An example are Kneser graphs having by vertex set all subsets of the same cardinality of a given set, and where two vertices are connected by an edge if their intersection is empty. In a very popular and important paper, Lovasz solves a combinatorial problem of Kneser graphs using algebraic topology techniques, thus creating a bridge between these mathematical theories. 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. These graphs are studied in numerous applications in computer science, for example in optimization, in hierarchical visualization systems, in the generation of random structures, as well as for the study of probabilistic models. 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. The diameter of one of the most widely used graph-associahedra, the associahedron graph, is known, but no algorithm is available to compute distances in this graph efficiently. The aim of this thesis is to understand the combinatorial structure of graph-associahedra and their relationship with intersecting families of sets. Indeed, on the one hand it is not difficult to construct an special family of intersection of sets containing the associahedron graph. On the other hand, the neighborhood simplicial complex associated with another special family of intersection of sets contains the 1-skeleton of the associahedron as a deformed retract. We want to extend such relations between these two combinatorial objets.

Profil du candidat

Titulaire d'un master 2 ou équivalent.
Solide connaissance en théorie de graphes et combinatoire et, si possible, en géométrie combinatoire.

Candidate profile

Master 2 or equivalent.
Solid knowledge on graph theory and combinatorics and, if possible, discrete geometry.

Référence biblio

[BL03] A. Björner, M. De Longueville, Neighborhood Complexes of stable Kneser graphs, Combinatorica 23 (1) (2003) 23–34
[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).
[LPVP24] A. Ledezma, A. Pastine, M. Valencia-Pabon. Exact distance Kneser graphs, submitted to a journal,
https://arxiv.org/abs/2403.15578, 2024.
[Lov78] L. Lovasz. Kneser's conjecture, chromatic number and homotopy, J. Combin. Theory Ser. A, 25 (1978) 319-324.
[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.
[Sch78] A. Schrijver: Vertex critical subgraphs of Kneser graphs, Nieuw Arch. Wiskd. 26 (1978), no. III. Ser., 454–461.
[SSV18] M. Sondag, B. Speckmann, K. Verbeek : Stable Treemaps via Local Moves. IEEE Trans. Vis. Comput. Graph. 24(1) : 729-738 (2018).